Un arbore binar este echilibrat dacă înălțimea arborelui este O(Log n) unde n este numărul de noduri. De exemplu, arborele AVL menține înălțimea O(Log n) asigurându-vă că diferența dintre înălțimile subarborilor din stânga și din dreapta este de cel mult 1. Arborele roșu-negru mențin înălțimea O(Log n), asigurându-vă că numărul de noduri negre pe fiecare cale de la rădăcină la frunză este aceeași și că nu există noduri roșii adiacente. Arborele de căutare binar echilibrat sunt buni din punct de vedere al performanței, deoarece oferă timp O(log n) pentru căutare, inserare și ștergere.
mylivecricket in for live cricket
Un arbore binar echilibrat este un arbore binar care respectă 3 condiții:
- Înălțimea arborelui din stânga și din dreapta pentru orice nod nu diferă cu mai mult de 1.
- Subarborele din stânga acelui nod este de asemenea echilibrat.
- Subarborele din dreapta al acelui nod este, de asemenea, echilibrat.
Un singur nod este întotdeauna echilibrat. Este denumit și arbore binar echilibrat în funcție de înălțime.
Exemplu :
Arborele binar echilibrat și dezechilibrat
Este un tip de arbore binar în care diferența dintre înălțimea subarborelui din stânga și din dreapta pentru fiecare nod este fie 0, fie 1. În figura de mai sus, nodul rădăcină având valoarea 0 este dezechilibrat cu o adâncime de 2 unități. .
Aplicarea arborelui binar echilibrat:
- Copaci AVL
- Arborele Roșu Negru
- Arborele de căutare binar echilibrat
Avantajele arborelui binar echilibrat:
- Actualizările non-distructive sunt susținute de un arbore binar echilibrat cu aceeași eficacitate asimptotică.
- Interogările de interval și iterația în secvența corectă sunt fezabile de arborele binar echilibrat.