Înainte de a înțelege Arborele roșu-negru și arborele AVL diferențe, ar trebui să știm despre arborele roșu-negru și arborele AVL separat.
Ce este un copac roșu-negru?
Arborele roșu-negru este un autoechilibrat arbore binar de căutare în care fiecare nod conține un bit în plus de informație care denotă culoarea nodului. Culoarea nodului poate fi roșu sau negru, în funcție de informațiile de biți stocate de nod.
Proprietăți
Următoarele sunt proprietățile asociate cu un arbore roșu-negru:
- Nodul rădăcină al arborelui ar trebui să fie Negru.
- Un nod roșu poate avea doar copii negri. Sau, putem spune că două noduri adiacente nu pot fi de culoare roșie.
- Dacă nodul nu are un copil stâng sau drept, atunci se spune că acel nod este un nod frunză. Deci, punem copiii din stânga și din dreapta sub nodul frunzei cunoscut sub numele zero
Adâncimea neagră sau înălțimea neagră a unui nod frunză poate fi definită ca numărul de negru pe care îl întâlnim atunci când trecem de la nodul frunză la nodul rădăcină. Una dintre proprietățile cheie ale arborelui roșu-negru este că fiecare nod al frunzei ar trebui să aibă aceeași adâncime neagră.
Să înțelegem această proprietate printr-un exemplu.
În arborele de mai sus, există cinci noduri, în care unul este roșu, iar celelalte patru noduri sunt negre. Există trei noduri de frunze în arborele de mai sus. Acum calculăm adâncimea neagră a fiecărui nod al frunzei. După cum putem observa că adâncimea neagră a tuturor celor trei noduri de frunze este 2; prin urmare, este un copac roșu-negru.
Dacă arborele nu se supune nici uneia dintre cele trei proprietăți de mai sus, atunci nu este un copac roșu-negru.
Înălțimea unui copac roșu-negru
Considerați h ca înălțimea arborelui având n noduri. Care ar fi cea mai mică valoare a lui n?. Valoarea lui n este cea mai mică atunci când toate nodurile sunt negre. Dacă arborele conține toate nodurile negre, atunci arborele ar fi un arbore binar complet. Dacă înălțimea unui arbore binar complet este h, atunci numărul de noduri dintr-un arbore este:
n = 2h -1
subșir în java
Care ar fi cea mai mare valoare a lui n?
Valoarea lui n este cea mai mare atunci când fiecare nod negru are doi copii roșii, dar nodul roșu nu poate avea copii roșii, astfel încât va avea copii negri. În acest fel, există straturi alternative de copii negri și roșii. Deci, dacă numărul de straturi negre este h, atunci și numărul de straturi roșii este h; prin urmare, înălțimea totală a copacului devine 2h. Numărul total de noduri este:
n = 2*2h-1
Ce este arborele AVL?
Un arborele AVL este un arbore de căutare binar cu auto-echilibrare dacă observăm cazul de mai jos, care este un arbore de căutare binar și un arbore echilibrat.
În arborele de mai sus, complexitatea de timp în cel mai rău caz pentru căutarea unui element este O(h), adică înălțimea arborelui. În cazul de mai sus, numărul de comparații făcute pentru a căuta elementul 17 este 4, iar înălțimea arborelui este de asemenea 4.
Dacă luăm în considerare arborele binar deformat, așa cum se arată mai jos:
În arborele înclinat din dreapta de mai sus, numărul de comparații făcute pentru a căuta elementul 17 este 5, iar numărul de elemente prezente în arbore este de asemenea 5. Prin urmare, putem spune că dacă arborele este un arbore binar deformat, atunci complexitatea timpului ar fi O(n).
Acum, trebuie să echilibrăm acești copaci deformați, astfel încât să aibă complexitatea temporală O(h). Există un termen cunoscut sub numele de a factor de echilibru , care este folosit pentru a autoechilibra arborele binar de căutare. Factorul de echilibru poate fi calculat ca:
Factorul de echilibru = înălțimea subarborelui din stânga-înălțimea subarborelui din dreaptaValoarea factorului de echilibru poate fi fie 1, 0 sau -1. Dacă fiecare nod din arborele binar are o valoare de 1, 0 sau -1, atunci se spune că acel arbore este echilibrat. arbore binar sau arborele AVL.
Arborele este cunoscut ca un arbore perfect echilibrat dacă factorul de echilibru al fiecărui nod este 0. Arborele AVL este un arbore aproape echilibrat deoarece fiecare nod din arbore are valoarea factorului de echilibru fie 1, 0 sau -1.
Diferențele dintre arborele roșu-negru și arborele AVL.
Următoarele sunt diferențele dintre arborele roșu-negru și arborele AVL:
Arborele Roșu-Negru este un arbore de căutare binar, iar arborele AVL este, de asemenea, un arbore de căutare binar.
Următoarele reguli sunt aplicate într-un arbore roșu-negru:
- Nodul dintr-un arbore roșu-negru este fie roșu, fie negru.
- Culoarea nodului rădăcină ar trebui să fie neagră.
- Nodurile adiacente nu trebuie să fie roșii. Cu alte cuvinte, putem spune că nodul roșu nu poate avea copii roșii, dar nodul negru poate avea copii negri.
- Ar trebui să existe același număr de noduri negre în fiecare cale; atunci, doar un copac poate fi considerat un copac roșu-negru.
- Nodurile externe sunt nodurile zero, care sunt întotdeauna de culoare neagră.
Regula arborelui AVL:
traversarea copacilor
Fiecare nod ar trebui să aibă factorul de echilibru fie ca -1, 0 sau 1.
În figura de mai sus, trebuie să verificăm dacă arborele este un copac roșu-negru sau nu. Pentru a verifica acest lucru, mai întâi, trebuie să verificăm dacă arborele este un arbore de căutare binar sau nu. După cum putem observa în figura de mai sus că satisface toate proprietățile arborelui binar de căutare; prin urmare, este un arbore de căutare binar. În al doilea rând, trebuie să verificăm dacă respectă sau nu regulile de mai sus. Arborele de mai sus îndeplinește toate cele cinci reguli de mai sus; prin urmare, concluzionează că arborele de mai sus este un arbore roșu-negru.
În figura de mai sus, trebuie să verificăm dacă arborele este un arbore AVL sau nu. Deoarece fiecare nod are o valoare a factorului de echilibru fie ca -1, 0 sau 1, deci este un arbore AVL.
În cazul unui arbore roșu-negru, dacă toate regulile de mai sus sunt îndeplinite, cu condiția ca un arbore să fie un arbore de căutare binar, atunci arborele se spune că este un arbore roșu-negru.
În cazul arborelui AVL, dacă factorul de echilibru este -1, 0 sau 1, atunci arborele de mai sus se spune că este un arbore AVL.
Dacă copacul nu este echilibrat, atunci se folosesc două instrumente pentru echilibrarea copacului într-un copac roșu-negru:
Dacă arborele nu este echilibrat, atunci se folosește un instrument pentru echilibrarea arborelui în arborele AVL:
În cazul arborelui Roșu-Negru, operațiunile de inserare și ștergere sunt eficiente. Dacă arborele se echilibrează prin recolorare, atunci operațiunile de inserare și ștergere sunt eficiente în arborele Roșu-Negru.
În cazul arborelui AVL, operația de căutare este eficientă deoarece necesită un singur instrument pentru a echilibra arborele.
În cazul arborelui roșu-negru, complexitatea timpului pentru toate operațiunile, adică inserarea, ștergerea și căutarea este O(logn).
În cazul arborelui AVL, complexitatea timpului pentru toate operațiunile, adică inserarea, ștergerea și căutarea este O(logn).
Să înțelegem diferențele în forma tabelară.
| Parametru | Arborele Roșu Negru | Arborele AVL |
|---|---|---|
| In cautarea | Red Black Tree nu oferă o căutare eficientă, deoarece Red Black Tree sunt aproximativ echilibrați. | Arborii AVL oferă o căutare eficientă, deoarece este un arbore strict echilibrat. |
| Inserare și ștergere | Inserarea și ștergerea sunt mai ușoare în arborele roșu negru, deoarece necesită mai puține rotații pentru a echilibra arborele. | Inserarea și ștergerea sunt complexe în arborele AVL, deoarece necesită mai multe rotații pentru a echilibra arborele. |
| Culoarea nodului | În arborele Roșu-Negru, culoarea nodului este fie Roșu, fie Negru. | În cazul arborilor AVL, nu există culoarea nodului. |
| Factorul de echilibru | Nu conține niciun factor de echilibru. Stochează un singur bit de informații care denotă fie culoarea roșie, fie neagră a nodului. | Fiecare nod are un factor de echilibru în arborele AVL a cărui valoare poate fi 1, 0 sau -1. Este nevoie de spațiu suplimentar pentru a stoca factorul de echilibru pe nod. |
| Strict echilibrat | Copacii roșu-negri nu sunt strict echilibrați. | Arborii AVL sunt strict echilibrați, adică înălțimea subarborelui din stânga și înălțimea subarborelui din dreapta diferă cu cel mult 1. |