[so] Tema2

[Lucian Adrian Grijincu]

On 11/12/07, Drenea Alex <alexdrenea at yahoo.com> wrote:
>
> Poate cineva sa ma lamureasca si pe mine  in legarura cu stergerea
> nodurilor? Cum adica se sterge SUCCESORUL ?? Nu se sterge nodul care trebuie
> sters? Cine e SUCCESORUL ala? Poate nu am fost eu prea atent la AA:(
>

DACA AM INTELES CORECT e ceva de genul:

cand stergi un nod de o valoare data X, vei cauta "succesorul" lui X
in arbore (cea mai mica valoare >= X. Valoarea asta se gaseste in
subarborele drept, fiind "cea mai din stanga valoare din arborele
acesta".

cazuri pe care trebuie sa le iei in considerare (pastrand notatiile
din tema, cu extensia "? <=> element sau subarbore" ):
X
S1 T1
? ? * ?
In acest caz, T1 e "succesorul" lui X

daca arborele tau e format din noduri de genul:
struct node_t {
  T val;
  struct node_t*st, *dr;
}

Stergerea lui X presupune:
   X.val = T1.val
   X.dr = T1.dr
   DELETE T1 /// stergerea SUCCESORULUI





X
S1 T1
? ? SUB ?

Unde SUB e un subarbore nevid.  "succesorul" lui X e cea mai din
stanga valoare din SUB: succesor  = SUB->st->st->st->...->st



X.val = succesor.val
parintele_succesorului.st = nada
DELETE SUCCESOR  /// stergerea SUCCESORULUI


HTH,
Lucian