Înainte de a ști despre arborele de căutare binar și diferențele arborelui AVL, ar trebui să știm despre arborele de căutare binar și arborele AVL separat.
Ce este un arbore binar de căutare?
The arbore binar de căutare este o copac arbore binar. După cum știm, acel copac poate avea „n” număr de copii, întrucât; arborele binar poate conține cel mult doi copii. Deci, constrângerea unui arbore binar este urmată și de arborele de căutare binar. Fiecare nod dintr-un arbore de căutare binar ar trebui să aibă maximum doi copii; cu alte cuvinte, putem spune că arborele binar de căutare este o variantă a arborelui binar.
Arborele de căutare binară urmează, de asemenea, proprietățile căutării binare. În căutarea binară, toate elementele dintr-o matrice trebuie să fie în ordine sortată. Calculăm elementul din mijloc în căutarea binară în care partea din stânga a elementului din mijloc conține valoarea mai mică decât valoarea din mijloc, iar partea din dreapta a elementului din mijloc conține valorile mai mari decât valoarea din mijloc.
În Arborele de căutare binar, elementul din mijloc devine nodul rădăcină, partea din dreapta devine subarborele din dreapta, iar partea din stânga devine subarborele din stânga. Prin urmare, putem spune că arborele binar de căutare este o combinație de a arbore binar și căutare binară .
Notă: Arborele de căutare binar poate fi definit ca arborele binar în care toate elementele subarborelui din stânga sunt mai mici decât nodul rădăcină, iar toate elementele subarborelui din dreapta sunt mai mari decât nodul rădăcină.
Complexitatea timpului în arborele de căutare binar
Dacă arborele binar de căutare este aproape un arbore echilibrat, atunci toate operațiunile vor avea o complexitate de timp de O(logn) deoarece căutarea este împărțită fie la stânga, fie la dreapta.
char tostring java
Dacă arborele de căutare binar este fie la stânga, fie la dreapta, atunci toate operațiunile vor avea complexitatea de timp de Pe) pentru că trebuie să traversăm până la cele n elemente.
Ce este arborele AVL?
Un arborele AVL este un arbore de căutare binar cu auto-echilibrare în care diferența dintre înălțimile subarborilor din stânga și din dreapta nu poate fi mai mare de unu. Această diferență este cunoscută ca factor de echilibru. În arborele AVL, valorile factorului de echilibru pot fi fie -1, 0 sau 1.
Cum are loc auto-echilibrarea arborelui de căutare binar?
După cum știm, arborele AVL este un arbore de căutare binar cu auto-echilibrare. Dacă arborele binar de căutare nu este echilibrat, acesta poate fi auto-echilibrat cu unele rearanjamente. Aceste rearanjamente se pot face folosind unele rotații.
Să înțelegem autoechilibrarea printr-un exemplu.
Să presupunem că vrem să inserăm 10, 20, 30 într-un arbore AVL.
Următoarele sunt modalitățile de inserare a 10, 20, 30 într-un arbore AVL:
Pasul 1: Mai întâi, creăm un arbore de căutare binar, așa cum se arată mai jos:
Pasul 2: În figura de mai sus, putem observa că arborele este dezechilibrat deoarece factorul de echilibru al nodului 30 este 2. Pentru a face din acesta un arbore AVL, trebuie să efectuăm câteva rotații. Dacă efectuăm rotația corectă pe nodul 20, atunci nodul 30 se va deplasa în jos, în timp ce nodul 20 se va deplasa în sus, așa cum se arată mai jos:
cum se convertesc int în șir de caractere java
După cum putem observa, arborele final urmează proprietatea arborelui de căutare binar și a unui arbore echilibrat; prin urmare, este un arbore AVL.
În cazul respectiv, copacul era copac lăsat dezechilibrat, deci efectuăm rotația corectă pe nod.
Pasul 1: Mai întâi creăm un arbore de căutare binar, așa cum se arată mai jos:
Pasul 2: În figura de mai sus, putem observa că arborele este dezechilibrat deoarece factorul de echilibru al nodului 10 este -2. Pentru a face din el un arbore AVL, trebuie să efectuăm câteva rotații. Este un arbore dezechilibrat în dreapta, așa că vom efectua rotația la stânga. Dacă efectuăm rotația la stânga pe nodul 20, atunci nodul 20 se va deplasa în sus, iar nodul 10 se va deplasa în jos, așa cum se arată mai jos:
După cum putem observa, arborele final urmează proprietatea lui Arborele de căutare binar si a arbore echilibrat ; prin urmare, este un arbore AVL.
Pasul 1: Mai întâi creăm arborele de căutare binar, așa cum se arată mai jos:
java bool la șir
Pasul 2: În figura de mai sus, putem observa că arborele este dezechilibrat deoarece factorul de echilibru al nodului rădăcină este 2. Pentru a face din acesta un arbore AVL, trebuie să efectuăm câteva rotații. Scenariul de mai sus este dezechilibrat stânga-dreapta, deoarece un nod este la stânga nodului părinte și un altul este la dreapta nodului părinte. Mai întâi, vom efectua rotația la stânga, iar rotația are loc între nodurile 10 și 20. După rotația la stânga, 20 se va deplasa în sus, iar 10 se va deplasa în jos, așa cum se arată mai jos:
Totuși, copacul este dezechilibrat, așa că efectuăm rotația corectă pe copac. Odată ce rotația corectă este efectuată pe arbore, atunci arborele ar dori, după cum se arată mai jos:
După cum putem observa în arborele de mai sus, arborele urmează proprietatea arborelui de căutare binar și a unui arbore echilibrat; prin urmare, este un arbore AVL.
Pasul 1: Mai întâi, creăm arborele de căutare binar, după cum se arată mai jos:
Pasul 2: În figura de mai sus, putem observa că arborele este dezechilibrat deoarece factorul de echilibru al nodului rădăcină este 2. Pentru a face din acesta un arbore AVL, trebuie să efectuăm câteva rotații. Scenariul de mai sus este dezechilibrat dreapta-stânga, deoarece un nod este la dreapta nodului său părinte, iar un alt nod este la stânga nodului său părinte. În primul rând, vom efectua rotația dreaptă care are loc între nodurile 30 și 20. După rotația la dreapta, 20 se va deplasa în sus și 30 se va deplasa în jos, așa cum se arată mai jos:
Totuși, arborele de mai sus este dezechilibrat, așa că trebuie să efectuăm rotația la stânga pe nod. Odată ce este efectuată rotația la stânga, nodul 20 se va deplasa în sus, iar nodul 10 se va deplasa în jos, așa cum se arată mai jos:
După cum putem observa în arborele de mai sus, arborele urmează proprietatea arborelui de căutare binar și a unui arbore echilibrat; prin urmare, este un arbore AVL.
Diferențele dintre arborele de căutare binar și arborele AVL
| Arborele de căutare binar | arborele AVL |
|---|---|
| Fiecare arbore binar de căutare este un arbore binar, deoarece ambii copaci conțin cel mai mult doi copii. | Fiecare arbore AVL este, de asemenea, un arbore binar, deoarece arborele AVL are și cei mai mulți doi copii. |
| În BST, nu există niciun termen, cum ar fi factorul de echilibru. | În arborele AVL, fiecare nod conține un factor de echilibru, iar valoarea factorului de echilibru trebuie să fie fie -1, 0 sau 1. |
| Fiecare arbore de căutare binar nu este un arbore AVL, deoarece BST poate fi fie un arbore echilibrat, fie un arbore dezechilibrat. | Fiecare arbore AVL este un arbore de căutare binar, deoarece arborele AVL urmează proprietatea BST. |
| Fiecare nod din arborele de căutare binar este format din trei câmpuri, adică subarborele din stânga, valoarea nodului și subarborele din dreapta. | Fiecare nod din arborele AVL este format din patru câmpuri, adică subarborele stânga, valoarea nodului, subarborele din dreapta și factorul de echilibru. |
| În cazul arborelui de căutare binară, dacă dorim să inserăm orice nod în arbore atunci comparăm valoarea nodului cu valoarea rădăcină; dacă valoarea nodului este mai mare decât valoarea nodului rădăcină, atunci nodul este inserat în subarborele din dreapta, altfel nodul este inserat în subarborele din stânga. Odată ce nodul este introdus, nu este nevoie de verificarea factorului de echilibrare a înălțimii pentru ca inserția să fie finalizată. | În cazul arborelui AVL, mai întâi, vom găsi locul potrivit pentru a insera nodul. Odată ce nodul este introdus, vom calcula factorul de echilibru al fiecărui nod. Dacă factorul de echilibru al fiecărui nod este satisfăcut, inserția este finalizată. Dacă factorul de echilibru este mai mare de 1, atunci trebuie să efectuăm câteva rotații pentru a echilibra arborele. |
| În arborele de căutare binară, înălțimea sau adâncimea arborelui este O(n) unde n este numărul de noduri din arborele de căutare binar. | În arborele AVL, înălțimea sau adâncimea arborelui este O(logn). |
| Este simplu de implementat deoarece trebuie să urmărim proprietățile Binary Search pentru a insera nodul. | Este complex de implementat deoarece în arborele AVL, trebuie mai întâi să construim arborele AVL, apoi trebuie să verificăm echilibrul înălțimii. Dacă înălțimea este dezechilibrată, atunci trebuie să facem câteva rotații pentru a echilibra copacul. |
| BST nu este un arbore echilibrat deoarece nu urmează conceptul de factor de echilibru. | Arborele AVL este un arbore echilibrat pe înălțime deoarece urmează conceptul factorului de echilibru. |
| Căutarea este ineficientă în BST atunci când există un număr mare de noduri disponibile în arbore deoarece înălțimea nu este echilibrată. | Căutarea este eficientă în arborele AVL chiar și atunci când există un număr mare de noduri în arbore deoarece înălțimea este echilibrată. |