Implementarea unui arbore de căutare binar

2024 Autor: Angel Austin | [email protected]. Modificat ultima dată: 2023-12-17 05:39

Arborele de căutare binar - o bază de date structurată care conține noduri, două link-uri către alte noduri, dreapta și stânga. Nodurile sunt un obiect al clasei care are date, iar NULL este semnul care marchează sfârșitul arborelui.

Se numește adesea BST, care are o proprietate specială: nodurile mai mari decât rădăcina sunt situate în dreapta acesteia, iar cele mai mici la stânga.

Teorie generală și terminologie

Într-un arbore de căutare binar, fiecare nod, excluzând rădăcina, este conectat printr-o margine direcționată de la un nod la altul, care se numește părinte. Fiecare dintre ele poate fi conectat la un număr arbitrar de noduri, numite copii. Nodurile fără „copii” se numesc frunze (noduri exterioare). Elementele care nu sunt frunze se numesc interne. Nodurile cu același părinte sunt frați. Nodul cel mai de sus se numește rădăcină. În BST, atribuiți un element fiecărui nod și asigurați-vă că are o proprietate specială setată pentru el.

Terminologia arborelui:

Adâncimea unui nod este numărul de muchii definite de la rădăcină la acesta.
Înălțimea unui nod este numărul de margini definite de la acesta până la cea mai adâncă frunză.
Înălțimea copacului este determinată de înălțimea rădăcinii.
Arborele de căutare binar este un design special, oferă cel mai bun raport între înălțime și numărul de noduri.
Înălțimea h cu N noduri cel mult O (log N).

Puteți demonstra cu ușurință acest lucru numărând nodurile de la fiecare nivel, începând de la rădăcină, presupunând că acesta conține cel mai mare număr dintre ele: n=1 + 2 + 4 + … + 2 h-1 + 2 h=2 h + 1 - 1 Rezolvând aceasta pentru h rezultă h=O (log n).

Beneficiile lemnului:

Reflectați relațiile structurale ale datelor.
Folosit pentru a reprezenta ierarhiile.
Asigurați o instalare și o căutare eficiente.
Arborii sunt date foarte flexibile, permițându-vă să mutați subarborii cu un efort minim.

Metoda de căutare

În general, pentru a determina dacă o valoare este în BST, porniți un arbore de căutare binar la rădăcină și determinați dacă îndeplinește cerințele:

fii la rădăcină;
să fie în subarborele din stânga al rădăcinii;
în subarborele din dreapta al rădăcinii.

Dacă nu este satisfăcut niciun registru de bază, se efectuează o căutare recursivă în subarborele corespunzător. Există de fapt două opțiuni de bază:

Arborele este gol - returnează fals.
Valoarea este în nodul rădăcină - returnează adevărat.

Trebuie remarcat că un arbore de căutare binar cu o schemă dezvoltată începe întotdeauna să caute de-a lungul căii de la rădăcină la frunză. În cel mai rău caz, merge până la frunză. Prin urmare, cel mai rău timp este proporțional cu lungimea drumului cel mai lung de la rădăcină la frunză, care este înălțimea copacului. În general, acesta este momentul în care trebuie să știți cât timp durează să căutați în funcție de numărul de valori stocate în arbore.

Cu alte cuvinte, există o relație între numărul de noduri dintr-un BST și înălțimea unui copac, în funcție de „forma” acestuia. În cel mai rău caz, nodurile au un singur copil, iar un arbore de căutare binar echilibrat este în esență o listă legată. De exemplu:

Acest arbore are 5 noduri și înălțimea=5. Găsirea valorilor în intervalul 16-19 și 21-29 va necesita următoarea cale de la rădăcină la frunză (nodul care conține valoarea 20), adică, va dura timp proporțional cu numărul de noduri. În cel mai bun caz, toți au 2 copii, iar frunzele sunt situate la aceeași adâncime.

Acest arbore binar de căutare are 7 noduri și înălțimea=3. În general, un arbore ca acesta (arborele întreg) va avea o înălțime de aproximativ log 2 (N), unde N este numărul de noduri din arbore. Valoarea log 2 (N) este numărul de ori (2) în care N poate fi împărțit înainte ca zero să fie atins.

Rezumat: cel mai prost timp necesar pentru a căuta în BST este O (înălțimea copacului). Arborele „liniar” din cel mai rău caz este O(N), unde N este numărul de noduri din arbore. În cel mai bun caz, un arbore „complet” este O(log N).

BST inserare binară

Mă întreb unde ar trebui să fienoul nod este situat în BST, trebuie să înțelegeți logica, trebuie să fie plasat acolo unde îl găsește utilizatorul. În plus, trebuie să vă amintiți regulile:

Duplicatele nu sunt permise, încercarea de a insera o valoare duplicat va genera o excepție.
Metoda publică de inserare folosește o metodă recursivă „ajutor” pentru a introduce efectiv.
Un nod care conține o nouă valoare este întotdeauna inserat ca frunză în BST.
Metoda publică de inserare returnează void, dar metoda helper returnează un BSTnode. Face acest lucru pentru a gestiona cazul în care nodul transmis la acesta este nul.

În general, metoda helper indică faptul că dacă arborele de căutare binar original este gol, rezultatul este un arbore cu un singur nod. În caz contrar, rezultatul va fi un pointer către același nod care a fost transmis ca argument.

Ștergere în algoritmul binar

După cum v-ați putea aștepta, ștergerea unui element implică găsirea unui nod care conține valoarea care trebuie eliminată. Există mai multe lucruri în acest cod:

BST folosește o metodă de ștergere de ajutor, supraîncărcată. Dacă elementul pe care îl căutați nu se află în arbore, atunci metoda helper va fi apelată în cele din urmă cu n==null. Aceasta nu este considerată o eroare, arborele pur și simplu nu se schimbă în acest caz. Metoda de ajutor de ștergere returnează o valoare - un pointer către arborele actualizat.
Când o frunză este eliminată, eliminarea din arborele binar de căutare setează indicatorul copil corespunzător al părintelui său la nul sau rădăcina la nul dacă cel care este eliminat estenodul este o rădăcină și nu are copii.
Rețineți că apelul de ștergere trebuie să fie unul dintre următoarele: rădăcină=ștergere (rădăcină, cheie), n.setLeft (ștergere (n.getLeft (), cheie)), n.setRight (ștergere (n. getRight(), cheie)). Astfel, în toate cele trei cazuri este corect ca metoda de ștergere să returneze pur și simplu null.
Când reușește căutarea nodului care conține valoarea de șters, există trei opțiuni: nodul de șters este o frunză (nu are copii), nodul de șters are un copil, are doi copii.
Când nodul care este eliminat are un copil, îl puteți înlocui pur și simplu cu un copil, returnând un pointer către copil.
Dacă nodul de șters are zero sau 1 copii, atunci metoda de ștergere va „urma calea” de la rădăcină la acel nod. Deci, cel mai rău moment este proporțional cu înălțimea arborelui, atât pentru căutare, cât și pentru inserare.

Dacă nodul de eliminat are doi copii, se parcurg următorii pași:

Găsiți nodul de șters, urmând calea de la rădăcină la acesta.
Găsiți cea mai mică valoare a lui v în subarborele din dreapta, continuând pe calea către frunză.
Eliminați recursiv valoarea lui v, urmați aceeași cale ca la pasul 2.
Astfel, în cel mai rău caz, calea de la rădăcină la frunză este efectuată de două ori.

Ordinea traverselor

Traversal este un proces care vizitează toate nodurile dintr-un arbore. Deoarece un arbore de căutare binar C este o structură de date neliniară, nu există o traversare unică. De exemplu, uneori mai mulți algoritmi de traversaregrupate în următoarele două tipuri:

adâncime de traversare;
prima trecere.

Există un singur fel de trecere pe lățime - ocolirea nivelului. Această traversare vizitează nodurile la nivel în jos și stânga, sus și dreapta.

Există trei tipuri diferite de traversări de adâncime:

Trecerea precomenzii - mai întâi vizitați părintele și apoi copilul din stânga și din dreapta.
Passing InOrder - vizitând copilul stâng, apoi părintele și copilul drept.
Trecut PostComandă - vizitarea copilului stâng, apoi a copilului din dreapta, apoi a părintelui.

Exemplu pentru patru traversări ale unui arbore de căutare binar:

Precomandă - 8, 5, 9, 7, 1, 12, 2, 4, 11, 3.
În ordine - 9, 5, 1, 7, 2, 12, 8, 4, 3, 11.
PostComandă - 9, 1, 2, 12, 7, 5, 3, 11, 4, 8.
LevelOrder - 8, 5, 4, 9, 7, 11, 1, 12, 3, 2.

Figura arată ordinea în care sunt vizitate nodurile. Numărul 1 este primul nod dintr-o anumită traversare, iar 7 este ultimul nod.

Aceste traversări generale pot fi reprezentate ca un singur algoritm, presupunând că fiecare nod este vizitat de trei ori. Turul Euler este o plimbare în jurul unui arbore binar în care fiecare margine este tratată ca un perete pe care utilizatorul nu îl poate traversa. În această plimbare, fiecare nod va fi vizitat fie în stânga, fie dedesubt, fie în dreapta. Turul Euler, care vizitează nodurile din stânga, face ca prepoziția să fie ocolită. Când nodurile de mai jos sunt vizitate, acestea sunt traversate în ordine. Și când nodurile din dreapta sunt vizitate - obținețiocolire pas cu pas.

Navigație și depanare

Pentru a facilita navigarea în arbore, creați funcții care verifică mai întâi dacă sunt copilul stâng sau drept. Pentru a schimba poziția unui nod, trebuie să existe acces ușor la indicatorul de la nodul părinte. Implementarea corectă a unui arbore este foarte dificilă, așa că trebuie să cunoașteți și să aplicați procesele de depanare. Un arbore de căutare binar cu o implementare are adesea indicatori care nu indică de fapt direcția de deplasare.

Pentru a înțelege toate acestea, este folosită o funcție care verifică dacă arborele poate fi corect și ajută la găsirea multor erori. De exemplu, verifică dacă nodul părinte este un nod copil. Cu assert(is_wellformed(root)) multe erori pot fi detectate prematur. Folosind câteva puncte de întrerupere date în cadrul acestei funcții, puteți determina exact care indicator este greșit.

Funcția Konsolenausgabe

Această funcție scoate întregul arbore în consolă și, prin urmare, este foarte utilă. Ordinea în care este executat obiectivul de ieșire a arborelui este:

Pentru a face acest lucru, mai întâi trebuie să determinați ce informații vor fi transmise prin nod.
Și, de asemenea, trebuie să știi cât de lat și de în alt este copacul pentru a ține cont de cât spațiu să lași.
Următoarele funcții calculează aceste informații pentru arbore și fiecare subarbor. Deoarece puteți scrie în consolă doar linie cu linie, va trebui să tipăriți arborele linie cu linie.
Acum avem nevoie de o altă modalitate de a ne retrageîntregul copac, nu doar rând cu rând.
Cu ajutorul funcției de descărcare, puteți citi arborele și puteți îmbunătăți semnificativ algoritmul de ieșire, în ceea ce privește viteza.

Cu toate acestea, această funcție va fi dificil de utilizat pe copacii mari.

Copiere constructor și destructor

Deoarece un arbore nu este o structură de date banală, este mai bine să implementați un constructor de copiere, un destructor și un operator de atribuire. Destructorul este ușor de implementat recursiv. Pentru copacii foarte mari, poate gestiona „debordarea grămezilor”. În acest caz, se formulează iterativ. Ideea este de a elimina frunza care reprezintă cea mai mică valoare dintre toate frunzele, deci se află pe partea stângă a copacului. Tăierea primelor frunze creează altele noi, iar copacul se micșorează până când în cele din urmă încetează să mai existe.

Constructorul de copiere poate fi implementat și recursiv, dar aveți grijă dacă se aruncă o excepție. În caz contrar, arborele devine rapid confuz și predispus la erori. De aceea se preferă versiunea iterativă. Ideea este să treci prin arborele vechi și arborele nou, așa cum ai face în destructor, clonând toate nodurile care sunt în arborele vechi, dar nu și pe cele noi.

Cu această metodă, implementarea arborelui de căutare binar este întotdeauna într-o stare sănătoasă și poate fi eliminată de către destructor chiar și într-o stare incompletă. Dacă apare o excepție, tot ce trebuie să faceți este să instruiți destructorul să șterge arborele semifinisat. operator de atribuirepoate fi implementat cu ușurință folosind Copiere și Schimbare.

Crearea unui arbore de căutare binar

Arborii optimi de căutare binare sunt incredibil de eficienți dacă sunt gestionați corespunzător. Câteva reguli pentru arborii binari de căutare:

Un nod părinte are cel mult 2 noduri secundare.
Nodul copil din stânga este întotdeauna mai mic decât nodul părinte.
Un nod copil valid este întotdeauna mai mare sau egal cu nodul părinte.

Matricea care va fi folosită pentru a construi arborele binar de căutare:

O matrice de numere întregi de bază de șapte valori în ordine nesortată.
Prima valoare din matrice este 10, deci primul pas în construirea arborelui este crearea unui nod rădăcină cu 10, așa cum se arată aici.
Cu un set de noduri rădăcină, toate celel alte valori vor fi copii ale acestui nod. Referindu-ne la reguli, primul pas care trebuie făcut pentru a adăuga 7 în arbore este să îl comparați cu nodul rădăcină.
Dacă valoarea 7 este mai mică de 10, va deveni nodul copil din stânga.
Dacă valoarea 7 este mai mare sau egală cu 10, se va deplasa la dreapta. Deoarece se știe că 7 este mai mic de 10, este desemnat ca nod copil stâng.
Efectuați recursiv comparații pentru fiecare element.
Urmând același model, efectuați aceeași comparație cu a 14-a valoare din matrice.
Comparând valoarea 14 cu nodul rădăcină 10, știind că 14 este copilul corect.
Mergând prin matrice,vin la 20.
Începeți prin a compara matricea cu 10, oricare dintre acestea este mai mare. Așa că mutați-vă la dreapta și comparați-l cu 14, el are peste 14 ani și nu are copii în dreapta.
Acum există o valoare de 1. Urmând același model ca și celel alte valori, comparați de la 1 la 10, deplasându-vă la stânga și comparând cu 7 și, în final, cu 1 copil din stânga al celui de-al 7-lea nod.
Dacă valoarea este 5, comparați-o cu 10. Deoarece 5 este mai mic de 10, treceți la stânga și comparați-o cu 7.
Știind că 5 este mai mic de 7, continuați în jos și comparați 5 cu 1 valoare.
Dacă 1 nu are copii și 5 este mai mare decât 1, atunci 5 este un copil valid al unui nod.
În sfârșit, introduceți valoarea 8 în arbore.
Când 8 este mai mic de 10, mutați-l la stânga și comparați-l cu 7, 8 este mai mare decât 7, așa că mutați-l la dreapta și completați arborele, făcând din 8 un copil cu 7 corect.

Obținerea și evaluarea eleganței simple a arborilor de căutare binari optimi. La fel ca multe subiecte din programare, puterea arborilor de căutare binare provine din capacitatea lor de a rezolva datele în componente mici, înrudite. De acum înainte, puteți lucra cu setul complet de date într-un mod organizat.

Probleme potențiale de căutare binară

Arborii de căutare binari sunt grozavi, dar trebuie să țineți cont de câteva avertismente. Ele sunt de obicei eficiente doar dacă sunt echilibrate. Un copac echilibrat este un copac în carediferența dintre înălțimile subarborilor oricărui nod din arbore este de cel mult una. Să ne uităm la un exemplu care ar putea ajuta la clarificarea regulilor. Să ne imaginăm că matricea începe ca sortabil.

Dacă încercați să rulați un algoritm de arbore de căutare binar pe acest arbore, acesta va funcționa exact ca și cum ar fi iterat prin matrice până când este găsită valoarea dorită. Puterea căutării binare constă în capacitatea de a filtra rapid valorile nedorite. Când un copac nu este echilibrat, nu va oferi aceleași beneficii ca un copac echilibrat.

Este foarte important să examinăm datele cu care lucrează utilizatorul atunci când creează un arbore binar de căutare. Puteți integra rutine precum randomizarea matricei înainte de a implementa un arbore de căutare binar pentru numere întregi pentru a-l echilibra.

Exemple de calcul de căutare binară

Trebuie să determinăm ce fel de arbore va rezulta dacă 25 este inserat în următorul arbore de căutare binar:

5 15

/ /

2 12 20

Când inserați x într-un arbore T care nu conține încă x, cheia x este întotdeauna plasată într-o nouă frunză. În legătură cu aceasta, noul arbore va arăta astfel:

5 15

/ /

2 12 20

Ce fel de arbore ați obține dacă ați insera 7 în următorul arbore de căutare binar?

5 15

/ /

2 12 20

Răspuns:

5 15

/ / /

2 7 12 20

Un arbore de căutare binar poate fi folosit pentru a stoca orice obiect. Avantajul utilizării unui arbore de căutare binar în loc de o listă legată este că, dacă arborele este echilibrat în mod rezonabil și mai mult ca un arbore „plin” decât unul „liniar”, inserarea, căutarea și toate operațiunile de ștergere pot fi implementate pentru a rula în O (log N) timp.