36 Ștergerea unui element într-un copac 2-3

36 Ștergerea unui element într-un copac 2-3

36 Ștergerea unui element într-un copac 2-3.

Când eliminați o cheie dintr-un nod, există trei opțiuni.

1) Dacă, după eliminarea cheii din nod, există două chei, iar după ștergere nimic nu se schimbă.







2) Dacă cheia are încă un element rămas după eliminare, atunci verificăm numărul de copii ai celui de-al doilea copil al nodului al cărui copil este nodul cu cheia care este șters. Dacă are doi copii, îi atribuim unuia dintre ele. Vârful, lăsat fără copii, este șters în mod recursiv.







3) În caz contrar, are trei copii. Apoi atribuim una din aceste chei unui nod cu o cheie, obținând astfel două noduri cu două chei.

1. Găsiți poziția elementului de șters prin tasta K

2. dacă elementul nu este o foaie atunci

3. Schimbați-l cu următoarea valoare

5. Scoateți un element din foaie

6. dacă foaia este goală, apoi fixați (foaia);

1. dacă (n-rădăcină) atunci

4. Setați p la nodul părinte

5. dacă fratele are două chei atunci

6. Redistribuiți elemente între frate, părinte și foaia.

7. dacă (n este nodul intern) atunci

8. Mutați unul dintre fii de la frate la nod n.

10. Setați S la fratele nodului n.

11. Mutați cheia de la p la S

12. dacă (n-nod intern) atunci

13. Atașați nodul copil al nodului n la S

14. ștergeți nodul n

15. dacă (p este gol), apoi fixați (p)







Articole similare

Pagina anterioară

Pagina următoare

Trimiteți-le prietenilor: