Eliminarea unui arbore binar de căutare 1

Cartea analizează în detaliu conceptele de bază ale algoritmilor și structurilor de date fundamentale, algoritmi de sortare, căutare, hashing, parsarea, de compresie a datelor, precum și multe alte subiecte care sunt strâns legate de programare a aplicațiilor. Abundenta testate temeinic exemple de cod, accelerează în mare măsură nu numai dezvoltarea algoritmilor fundamentale, dar, de asemenea, contribuie la o abordare mai calificat pentru programarea de zi cu zi.

Deși cartea este destinat în primul rând pentru dezvoltatorii de aplicații profesionale pe Delphi, ar fi programatori utile și novice care demonstrează tehnici și trucuri lor, care sunt atât de populare cu adevărat „pro“. Toate exemplele de codurile menționate în carte, este disponibil pentru descărcare de pe editorii de web-site-ului.

Carte: algoritmi fundamentale și structuri de date în Delphi

Eliminarea unui arbore binar de căutare

Ca și în operațiunea anterioară, cele mai multe dintre problemele pot fi ascunse de către utilizator a unui arbore binar de căutare. Cu toate acestea, arborele trebuie să îndeplinească unele sarcini mai complexe.

Firește, primul pas este de a găsi un element din arbore, folosind un algoritm standard. Dacă găsiți un element nu reușește, va trebui cumva să informeze despre eșec. În cazul în care elementul de detecție, căutarea poate fi încheiată într-un nod al unuia dintre cele trei tipuri, așa cum se întâmplă într-un arbore binar standard de.

Primul tip de nod - nodul fără noduri copil, atât pentru copii ale căror comunicații sunt zero. Cu alte cuvinte, foaia. Pentru a elimina acest tip de nod, doar ne rupe legătura sa cu unitatea de bază și scoateți-l. Această îndepărtare nu încalcă ordinea de noduri în copac - în cele din urmă, site-ul a fost o foaie și nu au avut noduri copil.

Al doilea tip de nod - nodul cu un singur nod copil. În cazul unui arbore binar standard, vă muta doar un singur nivel de nod copil de până pentru a înlocui nodul șters. Este posibil să facă același lucru în acest caz? Luați în considerare nodul părinte al nodului care urmează să fie eliminate. Nodul de la distanță este fie nodul stâng copil (în acest caz, este mai mică decât cheia cheii nodului părinte), sau nodul copil din dreapta (în acest caz, cheie cheie de nod părinte mai mare). Nu numai această unitate, ci și toți copiii, „nepot“, și așa mai departe nodurile gazdă la distanță au aceeași proprietate. Toate acestea sunt fie mai mică decât nodul părinte, sau mai mult. Astfel, atâta timp cât acesta este un nod părinte, în cazul în care nodul care înlocuiește unul dintre nodurile sale copil prin care se dispune de proprietate va fi menținută. Dacă nodul copil are noduri copil, această mișcare nu are nici un efect asupra lor sau la comanda lor. Prin urmare, în cazul unui arbore binar de căutare, putem realiza în continuare această operație simplă.

Un al treilea tip de nod - nodul cu noduri doi copii. În arborele standard de căutare binar, am considerat o încercare de a elimina un nod de acest tip de eroare. Îndepărtarea nu a putut fi îndeplinită, deoarece nu a existat nici o metodă generală pentru efectuarea unei operațiuni de ștergere, care ar avea sens. În cazul unui arbore binar de căutare, nu este în acest caz, puteți utiliza proprietățile arborelui comandat binar de căutare.

Situația este următoarea: trebuie să ștergem un nod specific (adică, elementul de la acel nod), dar are două noduri copil (din care fiecare are propriile sale noduri copil). algoritm de ștergere oarecum complexă, astfel că va fi descrisă inițial verbal, iar apoi se va arăta cum funcționează. În practică, suntem în căutarea pentru nodul care conține cel mai mare element, care este mai mică decât numai cel pe care încercăm să o eliminați. Apoi vom schimba elementele din aceste două noduri. În cele din urmă, vom șterge al doilea nod. El întotdeauna va corespunde unuia dintre cazurile discutate anterior de îndepărtare.

Primul pas este de a găsi cel mai mare element de mai puțin decât elementul încercăm să eliminați. Este clar că este arborele copil stânga (toate elementele arborelui este mai mică decât elementul șters). În plus, el este cel mai mare element al acestui arbore. Cu alte cuvinte, toate celelalte elemente care pot fi prezente în arborele copilului stânga, mai puțin din acest element. De fapt, toate elementele din arborele copilului drept mai mult de cea a elementului selectat (așa cum este mai mică decât elementul care urmează să fie eliminate, iar acest element este, la rândul său, este mai mică decât toate elementele din arborele copilului din dreapta). Prin urmare, se poate înlocui complet elementul detașabil, iar această acțiune nu încalcă ordinea elementelor în copac.

Dar ce putem spune despre site-ul, dintr-o poziție în care acesta a fost mutat, și care doresc acum să ștergeți? În ceea ce privește acest site special, este important să se înțeleagă că el nu are nici un nod copil dreapta. Dacă el are nodul copil din dreapta, un nod copil al unui element ar trebui să fie mai mare decât elementul la care ne-am schimbat locul lui, și, prin urmare, elementul selectat inițial, s-ar putea să nu fie cea mai mare. El poate fi lăsat nodul copil, dar indiferent de faptul că știm cum să eliminați un nod care nu are mai mult de un subsite.

Astfel, rămâne încă problema de a găsi cel mai mare element, care este mai mică decât originalul, destinat să elimine. În esență, efectuăm mișcarea arborelui. Începând cu elementul care urmează să fie eliminate, ne întoarcem la relațiile copilului rămas. Din acest punct vom continua să se deplaseze prin relațiile copilului corecte, atâta timp cât vom ajunge la nodul, care nu are relații de copil dreapta. Acest produs este garantat pentru a conține cel mai mare element, mai mic decât elementul pe care încercăm să o eliminați.

Rețineți, de asemenea, că eliminarea, precum și de inserție, poate duce la crearea unui copac degenerat. Această problemă este rezolvată algoritmi de echilibrare pe care o vom lua în considerare atunci când citiți versiunea roșu și negru a arborelui binar de căutare.

Listarea 8,15. Eliminarea unui arbore binar de căutare

Funcția TtdBinarySearchTree.bstFindNodeToDelete (aItem. pointer)