Validarea unui BST compară doar cu copiii direcți și acceptă arbori greșiți
Într-un arbore binar de căutare, toate valorile din subarborele stâng trebuie să fie mai mici decât nodul, nu doar copilul stâng. Transmite în recursivitate un interval permis (minim, maxim) și verifică fiecare nod față de el.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Definiția unui BST: pentru fiecare nod, toate valorile din subarborele stâng sunt mai mici, iar toate cele din subarborele drept mai mari. Verificarea „copilul stâng < nod < copilul drept”, aplicată recursiv, pare echivalentă, dar nu e: în arborele cu rădăcina 10, copilul stâng 5 și copilul drept al lui 5 egal cu 12, fiecare pereche părinte-copil e corectă, însă 12 se află în stânga lui 10.
Codul returnează True pentru un arbore invalid, iar căutările în el ar rata valori. În „Repară tu” testul cu assert arată rezultatul.
Reparația: fiecare nod moștenește un interval permis. Rădăcina are (-inf, inf); când cobori la stânga, maximul devine valoarea nodului; la dreapta, minimul devine valoarea nodului. Alternativ, parcurgerea în inordine a unui BST trebuie să dea valori strict crescătoare.
De ce apare: cauzele frecvente
1Verificare locală părinte-copil
def e_bst(nod):
if nod is None:
return True
if nod.st and nod.st.val >= nod.val:
return False
if nod.dr and nod.dr.val <= nod.val:
return False
return e_bst(nod.st) and e_bst(nod.dr)def e_bst(nod, mic=float('-inf'), mare=float('inf')):
if nod is None:
return True
if not mic < nod.val < mare:
return False
return e_bst(nod.st, mic, nod.val) and e_bst(nod.dr, nod.val, mare)Intervalul strâns la fiecare coborâre conține toate constrângerile strămoșilor, nu doar a părintelui.
2Inordine fără comparația cu valoarea anterioară
valori = inordine(radacina)
return valori == sorted(valori)valori = inordine(radacina)
return all(a < b for a, b in zip(valori, valori[1:]))sorted acceptă și valori egale. Dacă BST-ul cere valori distincte, verifică ordinea strict crescătoare.
Repară eroarea, direct în pagină
Funcția e_bst(nod) verifică dacă un arbore e arbore binar de căutare, dar acceptă arborele în care 12 apare în stânga lui 10. Testul cu assert pică. Repar-o ca testele să treacă și să afișeze False și True.
class Nod:
def __init__(self, val, st=None, dr=None):
self.val, self.st, self.dr = val, st, dr
def e_bst(nod):
if nod is None:
return True
if nod.st and nod.st.val >= nod.val:
return False
if nod.dr and nod.dr.val <= nod.val:
return False
return e_bst(nod.st) and e_bst(nod.dr)
stricat = Nod(10, Nod(5, Nod(2), Nod(12)), Nod(15))
bun = Nod(10, Nod(5, Nod(2), Nod(7)), Nod(15, None, Nod(20)))
for arbore, corect in [(stricat, False), (bun, True)]:
rez = e_bst(arbore)
assert rez == corect, f'validare gresita: {rez}'
print(rez)False True
Indiciu
Transmite fiecărui apel limitele permise (mic, mare) și strânge-le când cobori la stânga sau la dreapta.
Reparația
class Nod:
def __init__(self, val, st=None, dr=None):
self.val, self.st, self.dr = val, st, dr
def e_bst(nod, mic=float('-inf'), mare=float('inf')):
if nod is None:
return True
if not mic < nod.val < mare:
return False
return e_bst(nod.st, mic, nod.val) and e_bst(nod.dr, nod.val, mare)
stricat = Nod(10, Nod(5, Nod(2), Nod(12)), Nod(15))
bun = Nod(10, Nod(5, Nod(2), Nod(7)), Nod(15, None, Nod(20)))
for arbore, corect in [(stricat, False), (bun, True)]:
rez = e_bst(arbore)
assert rez == corect, f'validare gresita: {rez}'
print(rez)De ce merge
Codul vechi compara 12 doar cu părintele lui, 5, și îl accepta. Dar 12 se află în subarborele stâng al lui 10, deci trebuie să fie mai mic decât 10. Cu intervalul (mic, mare), nodul 5 primește (-inf, 10), iar copilul lui drept primește (5, 10): 12 iese din interval și funcția returnează False. Arborele corect trece, pentru că fiecare valoare se încadrează în limitele moștenite.
Cum o eviți pe viitor
Când verifici o proprietate de arbore, întreabă-te dacă depinde doar de părinte sau de toți strămoșii. Pentru BST, folosește intervalul (min, max) sau inordinea. Testează mereu cu arborele-capcană: un nod adânc care respectă părintele, dar nu bunicul. Hotărăște și ce faci cu valorile egale (de obicei nu sunt permise).
Întrebări frecvente
De ce float('-inf') și float('inf')?
Rădăcina nu are nicio restricție, iar infinitul e mai mic, respectiv mai mare decât orice număr. Așa nu ai nevoie de cazuri speciale pentru None.
Ce complexitate are verificarea cu interval?
O(n) timp, fiecare nod e vizitat o dată, și O(h) memorie pentru recursivitate, unde h e înălțimea arborelui.
Erori înrudite
AttributeError: 'NoneType' object has no attribute 'stanga' Funcția recursivă pe arbore a coborât într-un copil care nu există (None) și a cerut .stanga sau .val. Pune cazul de bază la început: if nod is None: return 0 (sau valoarea potrivită), înainte de orice acces la atributele nodului. RecursionError: maximum recursion depth exceeded Funcția recursivă s-a apelat de prea multe ori fără să se oprească, iar Python a depășit limita de aproximativ 1000 de apeluri imbricate. Adaugă un caz de bază (de exemplu if n <= 1: return 1) și verifică dacă fiecare apel se apropie de el. heapq scoate cel mai mic element, nu cel mai mare (max-heap lipsă) heapq din Python e un min-heap: heappop returnează mereu cel mai mic element. Pentru cel mai mare, pune valorile negate (heappush(h, -x), apoi -heappop(h)), folosește heapq.nlargest, sau, din Python 3.14, heappush_max / heappop_max. Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
