Inserarea în BST pierde nodurile noi: rezultatul apelului recursiv nu e atribuit
Funcția recursivă returnează nodul nou când ajunge la None, dar dacă nu scrii rad.stanga = insereaza(rad.stanga, val), nodul nu e legat de arbore. Atribuie rezultatul la fiecare nivel și la apelul de sus (rad = insereaza(rad, val)).
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Varianta recursivă elegantă a inserării într-un arbore binar de căutare (BST) se bazează pe o regulă: funcția returnează rădăcina subarborelui după inserare. Când ajunge la un loc gol (None), creează nodul și îl returnează; apelul de deasupra trebuie să-l lege: rad.stanga = insereaza(rad.stanga, val).
Dacă scrii doar insereaza(rad.stanga, val), nodul nou e creat și apoi pierdut. Python nu dă eroare. Arborele rămâne cu rădăcina singură sau cu nodurile de la primul nivel.
Aceeași greșeală apare la nivelul de sus: insereaza(rad, 5) cu rad = None returnează nodul nou, dar variabila rad rămâne None. Și la ștergerea din BST se aplică exact același tipar.
De ce apare: cauzele frecvente
1Apelul recursiv nu e atribuit
if val < rad.val:
insereaza(rad.stanga, val)
else:
insereaza(rad.dreapta, val)
return radif val < rad.val:
rad.stanga = insereaza(rad.stanga, val)
else:
rad.dreapta = insereaza(rad.dreapta, val)
return radAtribuirea leagă nodul nou de părintele lui. Pentru subarborii existenți, funcția returnează aceeași rădăcină, deci nu se strică nimic.
2Rădăcina nu e actualizată la apel
rad = None
for v in valori:
insereaza(rad, v)rad = None
for v in valori:
rad = insereaza(rad, v)Primul apel creează rădăcina; fără atribuire, rad rămâne None și fiecare apel creează un arbore nou, pierdut.
3Atribuire la parametru
def insereaza(rad, val):
if rad is None:
rad = Nod(val)
returndef insereaza(rad, val):
if rad is None:
return Nod(val)rad = Nod(val) schimbă doar variabila locală, nu legătura din părinte.
Repară eroarea, direct în pagină
Funcția insereaza(rad, val) adaugă coduri de produs într-un BST, iar inordine le afișează sortate. Testul cu assert pică: în arbore rămâne doar rădăcina. Repară inserarea ca să afișeze [1, 3, 4, 5, 8].
class Nod:
def __init__(self, val):
self.val = val
self.stanga = None
self.dreapta = None
def insereaza(rad, val):
if rad is None:
return Nod(val)
if val < rad.val:
insereaza(rad.stanga, val)
else:
insereaza(rad.dreapta, val)
return rad
def inordine(rad):
if rad is None:
return []
return inordine(rad.stanga) + [rad.val] + inordine(rad.dreapta)
rad = None
for v in [5, 3, 8, 1, 4]:
rad = insereaza(rad, v)
rez = inordine(rad)
assert rez == [1, 3, 4, 5, 8], f'arbore gresit: {rez}'
print(rez)[1, 3, 4, 5, 8]
Indiciu
Rezultatul apelurilor recursive trebuie salvat în rad.stanga și rad.dreapta.
Reparația
class Nod:
def __init__(self, val):
self.val = val
self.stanga = None
self.dreapta = None
def insereaza(rad, val):
if rad is None:
return Nod(val)
if val < rad.val:
rad.stanga = insereaza(rad.stanga, val)
else:
rad.dreapta = insereaza(rad.dreapta, val)
return rad
def inordine(rad):
if rad is None:
return []
return inordine(rad.stanga) + [rad.val] + inordine(rad.dreapta)
rad = None
for v in [5, 3, 8, 1, 4]:
rad = insereaza(rad, v)
rez = inordine(rad)
assert rez == [1, 3, 4, 5, 8], f'arbore gresit: {rez}'
print(rez)De ce merge
Când rad.stanga era None, apelul recursiv crea nodul 3 și îl returna, dar valoarea returnată era aruncată, deci arborele rămânea doar cu rădăcina 5. Cu rad.stanga = insereaza(rad.stanga, val), nodul nou e legat de părinte. Când subarborele există deja, funcția returnează aceeași rădăcină, deci atribuirea nu schimbă nimic acolo.
Alte forme ale mesajului
AttributeError: 'NoneType' object has no attribute 'val'
Cum o eviți pe viitor
Când o funcție recursivă pe arbori „returnează rădăcina subarborelui”, fiecare apel recursiv trebuie să fie în dreapta unei atribuiri. Verifică după construire cu o parcurgere în inordine: pentru un BST corect, rezultatul e lista sortată a tuturor valorilor inserate. Testează cu cel puțin trei niveluri.
Întrebări frecvente
Nu e mai simplu iterativ?
Varianta iterativă coboară până la un copil None și leagă nodul de părinte. E la fel de corectă; recursivă e mai scurtă, dar cere atribuirile.
De ce Python nu modifică arborele prin parametru?
Parametrii sunt nume locale. Poți modifica atributele obiectului primit (rad.stanga = ...), dar dacă atribui parametrului un obiect nou, apelantul nu vede schimbarea.
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. 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. TypeError: unsupported operand type(s) for +: 'int' and 'NoneType' Ai adunat un număr cu rezultatul unei funcții care a returnat None: de obicei o funcție recursivă care, într-o ramură, face apelul recursiv fără return în fața lui. Pune return pe fiecare ramură a funcției. Î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.
