Un arbore binar echilibrat este cunoscut și sub denumirea de arbore echilibrat pe înălțime. Este definit ca arbore binar atunci când diferența dintre înălțimea subarborelui din stânga și a subarborelui din dreapta nu este mai mare de m, unde m este de obicei egal cu 1. Înălțimea unui arbore este numărul de muchii de pe calea cea mai lungă dintre nodul rădăcină și nodul frunză.

nick pulos fulger negru

Arborele de mai sus este a arbore binar de căutare . Un arbore de căutare binar este un arbore în care fiecare nod din partea stângă are o valoare mai mică decât nodul său părinte, iar nodul din partea dreaptă are o valoare mai mare decât nodul său părinte. În arborele de mai sus, n1 este un nod rădăcină, iar n4, n6, n7 sunt nodurile frunzelor. Nodul n7 este cel mai îndepărtat nod de nodul rădăcină. N4 și n6 conțin 2 muchii și există trei muchii între nodul rădăcină și nodul n7. Deoarece n7 este cel mai îndepărtat de nodul rădăcină; prin urmare, înălțimea copacului de mai sus este de 3.

Acum vom vedea dacă arborele de mai sus este echilibrat sau nu. Subarborele din stânga conține nodurile n2, n4, n5 și n7, în timp ce subarborele din dreapta conține nodurile n3 și n6. Subarborele din stânga are două noduri de frunze, adică n4 și n7. Există o singură muchie între nodurile n2 și n4 și două muchii între nodurile n7 și n2; prin urmare, nodul n7 este cel mai îndepărtat de nodul rădăcină. Înălțimea subarborelui din stânga este 2. Subarborele din dreapta conține un singur nod frunză, adică n6, și are o singură margine; prin urmare, înălțimea subarborelui din dreapta este 1. Diferența dintre înălțimile subarborelui din stânga și al subarborelui din dreapta este 1. Deoarece am obținut valoarea 1, putem spune că arborele de mai sus este un arbore echilibrat pe înălțime. Acest proces de calculare a diferenței dintre înălțimi ar trebui efectuat pentru fiecare nod, cum ar fi n2, n3, n4, n5, n6 și n7. Când procesăm fiecare nod, atunci vom descoperi că valoarea lui k nu este mai mare de 1, deci putem spune că arborele de mai sus este un echilibrat. arbore binar .

În arborele de mai sus, n6, n4 și n3 sunt nodurile frunzelor, unde n6 este cel mai îndepărtat nod de nodul rădăcină. Există trei margini între nodul rădăcină și nodul frunză; prin urmare, înălțimea arborelui de mai sus este 3. Când considerăm n1 ca nod rădăcină, atunci subarborele din stânga conține nodurile n2, n4, n5 și n6, în timp ce subarborele conține nodul n3. În subarborele din stânga, n2 este un nod rădăcină, iar n4 și n6 sunt noduri frunze. Dintre nodurile n4 și n6, n6 este cel mai îndepărtat nod de nodul său rădăcină, iar n6 are două muchii; prin urmare, înălțimea subarborelui din stânga este 2. Subarborele din dreapta are orice copil în stânga și în dreapta; prin urmare, înălțimea subarborelui din dreapta este 0. Deoarece înălțimea subarborelui din stânga este 2, iar subarborele din dreapta este 0, deci diferența dintre înălțimea subarborelui din stânga și a subarborelui din dreapta este 2. Conform definiției, diferența între înălțimea arborelui secundar din stânga și arborelui secundar din dreapta nu trebuie să fie mai mare de 1. În acest caz, diferența ajunge să fie 2, care este mai mare decât 1; prin urmare, arborele binar de mai sus este un arbore de căutare binar dezechilibrat.

De ce avem nevoie de un arbore binar echilibrat?

Să înțelegem necesitatea unui arbore binar echilibrat printr-un exemplu.

Arborele de mai sus este un arbore de căutare binar, deoarece toate nodurile din subarborele din stânga sunt mai mici decât nodul său părinte și toate nodurile din subarborele din dreapta sunt mai mari decât nodul său părinte. Să presupunem că vrem să găsim valoarea 79 în arborele de mai sus. Mai întâi, comparăm valoarea nodului n1 cu 79; deoarece valoarea lui 79 nu este egală cu 35 și este mai mare decât 35, deci trecem la nodul n3, adică 48. Deoarece valoarea 79 nu este egală cu 48 și 79 este mai mare decât 48, deci ne deplasăm la dreapta copil de 48. Valoarea copilului drept al nodului 48 este 79 care este egală cu valoarea de căutat. Numărul de hop necesare pentru a căuta un element 79 este 2, iar numărul maxim de hop necesare pentru a căuta orice element este 2. Cazul mediu pentru căutarea unui element este O(logn).

Arborele de mai sus este, de asemenea, un arbore de căutare binar, deoarece toate nodurile subarborelui din stânga sunt mai mici decât nodul său părinte și toate nodurile din arborele secundar din dreapta sunt mai mari decât nodul său părinte. Să presupunem că vrem să găsim valoarea 79 în arborele de mai sus. În primul rând, comparăm valoarea 79 cu un nod n4, adică 13. Deoarece valoarea 79 este mai mare decât 13, trecem la copilul din dreapta al nodului 13, adică n2 (21). Valoarea nodului n2 este 21, care este mai mică decât 79, așa că ne deplasăm din nou la dreapta nodului 21. Valoarea copilului drept al nodului 21 este 29. Deoarece valoarea 79 este mai mare decât 29, ne deplasăm la dreapta. fiul nodului 29. Valoarea copilului drept al nodului 29 este 35, care este mai mică decât 79, așa că trecem la copilul drept al nodului 35, adică 48. Valoarea 79 este mai mare decât 48, deci trecem la copilul drept. a nodului 48. Valoarea nodului secundar drept al lui 48 este 79 care este egală cu valoarea de căutat. În acest caz, numărul de hop necesare pentru a căuta un element este 5. În acest caz, cel mai rău caz este O(n).

Dacă numărul de noduri crește, formula folosită în diagrama arborescentă1 este mai eficientă decât formula utilizată în diagrama arborescentă2. Să presupunem că numărul de noduri disponibile în ambii arbori de mai sus este de 100.000. Pentru a căuta orice element într-o diagramă arborescentă2, timpul necesar este de 100.000 µs, în timp ce timpul necesar pentru a căuta un element într-o diagramă arborescentă este log(100.000), care este egal cu 16,6 µs. Putem observa diferența enormă de timp dintre cei doi copaci de deasupra. Prin urmare, concluzionăm că arborele binar de echilibru oferă o căutare mai rapidă decât structura de date a arborelui liniar.

exemplu de arbore binar de căutare