Copac AVL - AVL tree

Copac AVL
Copac AVL
Tip	copac
Inventat	1962
Inventat de	Georgy Adelson-Velsky și Evgenii Landis
Complexitatea timpului în notația O mare
Algoritm
Algoritm
Spaţiu
Căutare
Introduce
Șterge

Animație care arată inserarea mai multor elemente într-un arbore AVL. Include rotații stânga, dreapta, stânga-dreapta și dreapta-stânga.

Fig. 1: arbore AVL cu factori de echilibru (verde)

În informatică , un arbore AVL (numit după inventatorii A delson- V elsky și L andis) este un arbore de căutare binar auto-echilibrat . A fost prima astfel de structură de date inventată. Într-un copac AVL, înălțimile celor doi subarburi copii ai oricărui nod diferă cu cel mult unul; dacă în orice moment diferă de mai multe, reechilibrarea se face pentru a restabili această proprietate. Căutarea, inserarea și ștergerea necesită tot timpul $O (log n)$ atât în cazurile medii, cât și în cele mai nefaste, unde este numărul de noduri din arborele anterior operației. Inserările și ștergerile pot necesita reechilibrarea arborelui cu una sau mai multe rotații ale arborelui . ${\ displaystyle n}$

Arborele AVL poartă numele celor doi inventatori sovietici ai săi , Georgy Adelson-Velsky și Evgenii Landis , care l-au publicat în lucrarea din 1962 „Un algoritm pentru organizarea informațiilor”.

Copacii AVL sunt adesea comparați cu copacii roșii-negri, deoarece ambii acceptă același set de operații și necesită timp pentru operațiile de bază. Pentru aplicațiile cu intensitate de căutare, copacii AVL sunt mai rapizi decât copacii roșu-negri, deoarece sunt mai strict echilibrați. Similar cu copacii roșu-negri, copacii AVL sunt echilibrați în înălțime. Ambele sunt, în general, nici echilibrat greutate , nici -balanced pentru orice ; adică nodurile fraților pot avea un număr foarte mare de descendenți. ${\ displaystyle {\ text {O}} (\ log n)}$ ${\ displaystyle \ mu}$ ${\ displaystyle \ mu \ leq {\ tfrac {1} {2}}}$

Definiție

Factorul de echilibru

Într - un arbore binar factorul de echilibru al unui nod X este definit ca fiind diferența de înălțime

{\ displaystyle {\ text {BF}} (X): = {\ text {Height}} ({\ text {RightSubtree}} (X)) - {\ text {Height}} ({\ text {LeftSubtree}} (X))}

din cei doi sub-copaci ai săi. Un arbore binar este definit ca un arbore AVL dacă invariantul

{\ displaystyle {\ text {BF}} (X) \ în {\ {- 1,0,1 \}}}

păstrează pentru fiecare nod X din copac.

Un nod X cu este numit „stânga-greu”, unul cu este numit „dreapta-greu”, iar unul cu este uneori pur și simplu numit „echilibrat”. ${\ displaystyle {\ text {BF}} (X) <0}$ ${\ displaystyle {\ text {BF}} (X)> 0}$ ${\ displaystyle {\ text {BF}} (X) = 0}$

Proprietăți

Factorii de echilibru pot fi actualizați prin cunoașterea factorilor de echilibru anteriori și modificarea înălțimii - nu este necesar să se cunoască înălțimea absolută. Pentru păstrarea informațiilor despre soldul AVL în mod tradițional, sunt suficienți doi biți pe nod. Cu toate acestea, cercetările ulterioare au arătat dacă arborele AVL este implementat ca un arbore echilibrat cu ranguri delta permise de 1 sau 2 - cu semnificația „când mergeți în sus există o creștere suplimentară a înălțimii unuia sau a două”, acest lucru se poate face cu unul pic.

Înălțimea (numărată ca număr maxim de niveluri) a unui arbore AVL cu noduri se află în intervalul: ${\ displaystyle h}$ ${\ displaystyle n}$

{\ displaystyle \ log _ {2} (n + 1) \ leq h <\ log _ {\ varphi} (n + 2) + b}

unde este raportul de aur și Acest lucru se datorează faptului că un copac AVL de înălțime conține cel puțin noduri unde este secvența Fibonacci cu valorile de semințe ${\ displaystyle \ varphi: = {\ tfrac {1 + {\ sqrt {5}}} {2}} \ approx 1.618}$ ${\ displaystyle b: = {\ frac {\ log _ {2} 5} {2 \ log _ {2} \ varphi}} - 2 \ approx \; - 0.3277.}$ ${\ displaystyle h}$ ${\ displaystyle F_ {h + 2} -1}$ ${\ displaystyle \ {F_ {n} \} _ {n \ in \ mathbb {N}}}$ ${\ displaystyle F_ {1} = F_ {2} = 1.}$

Operațiuni

Operațiile de citire numai ale unui arbore AVL implică efectuarea acelorași acțiuni ca și cum ar fi efectuate pe un arbore de căutare binar dezechilibrat , dar modificările trebuie să respecte și să restabilească echilibrul înălțimii subarborilor.

In cautarea

Căutarea unei chei specifice într-un arbore AVL se poate face la fel ca în cazul oricărui arbore de căutare binar echilibrat sau neechilibrat . Pentru ca căutarea să funcționeze eficient, trebuie să utilizeze o funcție de comparație care stabilește o ordine totală (sau cel puțin o precomandă totală ) pe setul de taste. Numărul comparațiilor necesare pentru căutarea cu succes este limitat de înălțimea $h,$ iar pentru căutarea nereușită este foarte aproape de $h$ , deci ambele sunt în $O (jurnal n)$ .

Traversal

Ca o operațiune numai în citire, traversarea unui arbore AVL funcționează în același mod ca pe orice alt arbore binar. Explorând toate cele $n$ noduri ale arborelui vizitează fiecare legătură exact de două ori: o vizită în jos pentru a intra în subarborele înrădăcinat de acel nod, o altă vizită în sus pentru a părăsi subarborele acelui nod după ce l-ați explorat.

Odată ce un nod a fost găsit într-un arbore AVL, nodul următor sau anterior poate fi accesat în timp constant amortizat . Unele cazuri de explorare a acestor noduri „din apropiere” necesită parcurgerea până la $legături$ $h \propto log (n)$ (în special atunci când navigați de la frunza din dreapta a subarborelui stâng al rădăcinii la rădăcină sau de la rădăcină la frunza din stânga a subarborelui drept al rădăcinii; în arborele AVL din figura 1, navigarea de la nodul P la nodul Q din dreapta urmează 3 pași). Deoarece există $n -1$ legături în orice arbore, costul amortizat este $2 \times (n -1) / n$ , sau aproximativ 2.

Introduce

Când introduceți un nod într-un arbore AVL, urmați inițial același proces ca și inserarea într-un arbore de căutare binară . Dacă arborele este gol, atunci nodul este introdus ca rădăcină a arborelui. În cazul în care arborele nu a fost gol, coborâm în rădăcină și coborâm recursiv în arborele căutând locația pentru a insera noul nod. Această traversare este ghidată de funcția de comparație. În acest caz, nodul înlocuiește întotdeauna o referință NULL (stânga sau dreapta) a unui nod extern din arbore, adică nodul este fie copil stânga, fie drept copil al nodului extern.

După această inserare, dacă un copac devine dezechilibrat, numai strămoșii nodului nou introdus sunt dezechilibrați. Acest lucru se datorează faptului că numai acele noduri au sub-copacii modificați. Deci, este necesar să verificați fiecare dintre strămoșii nodului pentru consistența cu invarianții arborilor AVL: aceasta se numește „retracere”. Acest lucru se realizează luând în considerare factorul de echilibru al fiecărui nod.

Deoarece cu o singură inserție înălțimea unui subarborel AVL nu poate crește cu mai mult de unul, factorul de echilibru temporar al unui nod după o inserție va fi în intervalul [–2, + 2]. Pentru fiecare nod verificat, dacă factorul de echilibru temporar rămâne în intervalul de la –1 la +1, atunci este necesară doar o actualizare a factorului de echilibru și nu este necesară nicio rotație. Cu toate acestea, dacă factorul de echilibru temporar devine mai mic de –1 sau mai mare de +1, subarborele înrădăcinat la acest nod este AVL dezechilibrat și este necesară o rotație. Cu inserția așa cum arată codul de mai jos, rotația adecvată reechilibrează perfect arborele.

În figura 1, prin inserarea noului nod Z ca un copil al nodului X, înălțimea subarborelui Z crește de la 0 la 1.

Invariant al buclei de retracere pentru o inserție

Înălțimea subarborelui înrădăcinat de Z a crescut cu 1. Este deja în formă AVL.

Exemplu de cod pentru o operație de inserare

for (X = parent(Z); X != null; X = parent(Z)) { // Loop (possibly up to the root)
    // BF(X) has to be updated:
    if (Z == right_child(X)) { // The right subtree increases
        if (BF(X) > 0) { // X is right-heavy
            // ==> the temporary BF(X) == +2
            // ==> rebalancing is required.
            G = parent(X); // Save parent of X around rotations
            if (BF(Z) < 0)                  // Right Left Case  (see figure 3)
                N = rotate_RightLeft(X, Z); // Double rotation: Right(Z) then Left(X)
            else                            // Right Right Case (see figure 2)
                N = rotate_Left(X, Z);      // Single rotation Left(X)
            // After rotation adapt parent link
        } else {
            if (BF(X) < 0) {
                BF(X) = 0; // Z’s height increase is absorbed at X.
                break; // Leave the loop
            }
            BF(X) = +1;
            Z = X; // Height(Z) increases by 1
            continue;
        }
    } else { // Z == left_child(X): the left subtree increases
        if (BF(X) < 0) { // X is left-heavy
            // ==> the temporary BF(X) == -2
            // ==> rebalancing is required.
            G = parent(X); // Save parent of X around rotations
            if (BF(Z) > 0)                  // Left Right Case
                N = rotate_LeftRight(X, Z); // Double rotation: Left(Z) then Right(X)
            else                            // Left Left Case
                N = rotate_Right(X, Z);     // Single rotation Right(X)
            // After rotation adapt parent link
        } else {
            if (BF(X) > 0) {
                BF(X) = 0; // Z’s height increase is absorbed at X.
                break; // Leave the loop
            }
            BF(X) = -1;
            Z = X; // Height(Z) increases by 1
            continue;
        }
    }
    // After a rotation adapt parent link:
    // N is the new root of the rotated subtree
    // Height does not change: Height(N) == old Height(X)
    parent(N) = G;
    if (G != null) {
        if (X == left_child(G))
            left_child(G) = N;
        else
            right_child(G) = N;
    } else
        tree->root = N; // N is the new root of the total tree
    break;
    // There is no fall thru, only break; or continue;
}
// Unless loop is left via break, the height of the total tree increases by 1.

Pentru a actualiza factorii de echilibru ai tuturor nodurilor, observați mai întâi că toate nodurile care necesită corecție se află de la copil la părinte de-a lungul căii frunzei inserate. Dacă procedura de mai sus se aplică nodurilor de-a lungul acestei căi, începând de la frunză, atunci fiecare nod din copac va avea din nou un factor de echilibru de -1, 0 sau 1.

Retrasarea se poate opri dacă factorul de echilibru devine 0 ceea ce implică faptul că înălțimea subarborelui respectiv rămâne neschimbată.

Dacă factorul de echilibru devine ± 1, atunci înălțimea subarborelui crește cu unul și retracerea trebuie să continue.

Dacă factorul de echilibru devine temporar ± 2, acesta trebuie reparat printr-o rotație adecvată, după care subarborele are aceeași înălțime ca înainte (iar rădăcina sa este factorul de echilibru 0).

Timpul necesar este $O (log n)$ pentru căutare, plus un maxim de $O (log n)$ retracere niveluri ( $O (1)$ în medie) la întoarcerea la rădăcină, astfel încât operațiunea poate fi finalizată în $O (log n)$ timp.

Șterge

Pașii preliminari pentru ștergerea unui nod sunt descriși în secțiunea Arborele de căutare binar # Ștergere . Acolo, ștergerea efectivă a nodului subiect sau a nodului de înlocuire scade înălțimea arborelui copil corespunzător fie de la 1 la 0, fie de la 2 la 1, dacă acel nod a avut un copil.

Începând de la acest subarbore, este necesar să verificați fiecare dintre strămoși pentru consistența cu invarianții copacilor AVL. Aceasta se numește „retracere”.

Deoarece cu o singură ștergere înălțimea unui subarborel AVL nu poate scădea cu mai mult de unul, factorul de echilibru temporar al unui nod va fi în intervalul de la -2 la +2. Dacă factorul de echilibru rămâne în intervalul de la -1 la +1, acesta poate fi ajustat în conformitate cu regulile AVL. Dacă devine ± 2, subarborele este dezechilibrat și trebuie rotit. (Spre deosebire de inserția în care o rotație echilibrează întotdeauna arborele, după ștergere, poate exista BF (Z) ≠ 0 (vezi figurile 2 și 3), astfel încât, după rotația unică sau dublă corespunzătoare, înălțimea subarborelui reechilibrat scade cu o singură semnificație că arborele trebuie reechilibrat din nou la următorul nivel superior.) Diferitele cazuri de rotații sunt descrise în secțiunea Reechilibrare .

Invariant al buclei de retracere pentru o ștergere

Înălțimea subarborelui înrădăcinat de N a scăzut cu 1. Este deja în formă AVL.

Exemplu de cod pentru o operație de ștergere

for (X = parent(N); X != null; X = G) { // Loop (possibly up to the root)
    G = parent(X); // Save parent of X around rotations
    // BF(X) has not yet been updated!
    if (N == left_child(X)) { // the left subtree decreases
        if (BF(X) > 0) { // X is right-heavy
            // ==> the temporary BF(X) == +2
            // ==> rebalancing is required.
            Z = right_child(X); // Sibling of N (higher by 2)
            b = BF(Z);
            if (b < 0)                      // Right Left Case  (see figure 3)
                N = rotate_RightLeft(X, Z); // Double rotation: Right(Z) then Left(X)
            else                            // Right Right Case (see figure 2)
                N = rotate_Left(X, Z);      // Single rotation Left(X)
            // After rotation adapt parent link
        } else {
            if (BF(X) == 0) {
                BF(X) = +1; // N’s height decrease is absorbed at X.
                break; // Leave the loop
            }
            N = X;
            BF(N) = 0; // Height(N) decreases by 1
            continue;
        }
    } else { // (N == right_child(X)): The right subtree decreases
        if (BF(X) < 0) { // X is left-heavy
            // ==> the temporary BF(X) == -2
            // ==> rebalancing is required.
            Z = left_child(X); // Sibling of N (higher by 2)
            b = BF(Z);
            if (b > 0)                      // Left Right Case
                N = rotate_LeftRight(X, Z); // Double rotation: Left(Z) then Right(X)
            else                            // Left Left Case
                N = rotate_Right(X, Z);     // Single rotation Right(X)
            // After rotation adapt parent link
        } else {
            if (BF(X) == 0) {
                BF(X) = -1; // N’s height decrease is absorbed at X.
                break; // Leave the loop
            }
            N = X;
            BF(N) = 0; // Height(N) decreases by 1
            continue;
        }
    }
    // After a rotation adapt parent link:
    // N is the new root of the rotated subtree
    parent(N) = G;
    if (G != null) {
        if (X == left_child(G))
            left_child(G) = N;
        else
            right_child(G) = N;
    } else
        tree->root = N; // N is the new root of the total tree
 
    if (b == 0)
        break; // Height does not change: Leave the loop
 
    // Height(N) decreases by 1 (== old Height(X)-1)
}
// If (b != 0) the height of the total tree decreases by 1.

Retrasarea se poate opri dacă factorul de echilibru devine ± 1 (trebuie să fi fost 0), ceea ce înseamnă că înălțimea subarborelui respectiv rămâne neschimbată.

Dacă factorul de echilibru devine 0 (trebuie să fi fost ± 1), atunci înălțimea subarborelui scade cu unul și retracerea trebuie să continue.

Dacă factorul de echilibru devine temporar ± 2, acesta trebuie reparat printr-o rotație adecvată. Depinde de factorul de echilibru al fratelui Z (arborele copil superior din figura 2) dacă înălțimea subarborelui scade cu unul - iar retracerea trebuie să continue - sau nu se schimbă (dacă Z are factorul de echilibru 0) și întregul copac are o formă AVL.

Timpul necesar este $O (log n)$ pentru căutare, plus un maxim de $O (log n)$ retracere niveluri ( $O (1)$ în medie) la întoarcerea la rădăcină, astfel încât operațiunea poate fi finalizată în $O (log n)$ timp.

Setați operațiunile și operațiunile în bloc

În plus față de operațiile de inserare, ștergere și căutare cu un singur element, mai multe operații de set au fost definite pe arborii AVL: uniune , intersecție și diferență de set . Apoi, operațiile rapide în bloc pe inserții sau ștergeri pot fi implementate pe baza acestor funcții setate. Aceste operații de set se bazează pe două operații de asistență, Split și Join . Cu noile operațiuni, implementarea arborilor AVL poate fi mai eficientă și foarte paralelizabilă.

Funcția Unire pe doi copaci AVL $t 1$ și $t 2$ și o tastă $k$ va returna un copac care conține toate elementele din $t 1$ , $t 2$ , precum și $k$ . Este necesar ca $k$ să fie mai mare decât toate tastele din $t 1$ și mai mic decât toate tastele din $t 2$ . Dacă cei doi copaci diferă în funcție de înălțime cel mult unul, Alăturați-vă pur și simplu creați un nou nod cu subarborele stâng $t 1$ , rădăcina $k$ și subarborele drept $t 2$ . În caz contrar, să presupunem că $t 1$ este mai mare decât $t 2$ pentru mai mult de unul (celălalt caz este simetric). Unirea urmează coloana vertebrală dreaptă a $t 1$ până la un nod $c$ care este echilibrat cu $t 2$ . În acest moment se creează un nou nod cu copilul stâng $c$ , rădăcina $k$ și copilul drept $t 2$ pentru a înlocui c. Noul nod satisface invariantul AVL, iar înălțimea acestuia este una mai mare decât $c$ . Creșterea înălțimii poate crește înălțimea strămoșilor săi, eventual invalidând invariantul AVL al acestor noduri. Acest lucru poate fi rezolvat fie cu o rotație dublă dacă este invalidă la părinte, fie cu o singură rotație la stânga, dacă este invalidă mai sus în arbore, în ambele cazuri restabilind înălțimea pentru orice alte noduri strămoșești. Prin urmare, îmbinarea va necesita cel mult două rotații. Costul acestei funcții este diferența de înălțimi dintre cei doi arbori de intrare.

Implementarea pseudocodului pentru algoritmul Join

function JoinRightAVL(T_L, k, T_R)
    (l,k',c) = expose(T_L)
    if (Height(c) <= Height(T_R)+1)
       T'=Node(c,k,T_R)
       if (Height(T') <= Height(l)+1) then return Node(l,k',T')
       else return rotateLeft(Node(l,k'rotateRight(T')))
    else 
        T' = JoinRightAVL(c,k,T_R)
        T = Node(l,k',T')
        if (Height(T') <= Height(l)+1) return T
        else return rotateLeft(T)

function JoinLeftAVL(T_L, k, T_R)
  /* symmetric to JoinRightAVL */

function Join(T_L, k, T_R)
    if (Height(T_L)>Height(T_R)+1) return JoinRightAVL(T_L, k, T_R)
    if (Height(T_R)>Height(T_L)+1) return JoinLeftAVL(T_L, k, T_R)
    return Node(T_L,k,T_R)

Aici Înălțimea (v) este înălțimea unui subarboră (nod) $v$ . (l, k, r) = expune (v) extractele $v$ 's stânga copil $l$ , cheia $k$ a $v$ ' root s, și dreptul copilului $r$ . Nod (l, k, r) înseamnă a crea un nod de copil stânga $l$ , cheie $k$ și copil drept dreapta $r$ .

Pentru a împărți un copac AVL în doi copaci mai mici, cei mai mici decât cheia $k$ și cei mai mari decât cheia $k$ , trageți mai întâi o cale de la rădăcină inserând $k$ în AVL. După această inserare, toate valorile mai mici de $k$ vor fi găsite în stânga căii și toate valorile mai mari decât $k$ vor fi găsite în dreapta. Prin aplicarea Alăturați-vă , toți subarborii din partea stângă sunt îmbinați de jos în sus folosind tastele de pe cale ca noduri intermediare de jos în sus pentru a forma arborele din stânga, iar partea dreaptă este asimetrică. Costul împărțirii este $O (log n)$ , ordinea înălțimii arborelui.

Implementarea pseudocodului pentru algoritmul Split

function Split(T,k)
    if (T = nil) return (nil,false,nil)
    (L,m,R) = expose(T)
    if (k = m) return (L,true,R)
    if (k<m) 
       (L',b,R') = split(L,k)
       return (L',b,join(R',m,R))
    if (k>m) 
       (L',b,R') = split(R,k)
       return (join(L,m,L'),b,R'))

Unirea celor doi arbori AVL $t 1$ și $t 2$ seturi reprezentând $A$ și $B$ , este un AVL $t$ , care reprezintă $un \cup B$ .

Implementarea pseudocodului pentru algoritmul Uniunii

function Union(t₁, t₂):
    if t₁ = nil:
        return t₂
    if t₂ = nil:
        return t₁
    t_<, t_> ← split t₂ on t₁.root
    return join(t₁.root,union(left(t₁), t_<),union(right(t₁), t_>))

Aici, se presupune că Split returnează doi copaci: unul ținând tastele mai puțin cheia de intrare, unul ținând tastele mai mari. (Algoritmul este nedistructiv , dar există și o versiune distructivă în loc.)

Algoritmul pentru intersecție sau diferență este similar, dar necesită rutina de asistență Join2 care este aceeași cu Join dar fără cheia de mijloc. Pe baza noilor funcții pentru unire, intersecție sau diferență, fie o tastă sau mai multe taste pot fi inserate sau șterse din arborele AVL. Deoarece Split apelează Join, dar nu se ocupă direct de criteriile de echilibrare ale arborilor AVL, o astfel de implementare este denumită de obicei implementarea „bazată pe join” .

Complexitatea fiecărei uniuni, intersecții și diferențe este pentru arborii AVL de dimensiuni și . Mai important, deoarece apelurile recursive la uniune, intersecție sau diferență sunt independente unele de altele, ele pot fi executate în paralel cu o adâncime paralelă . Când , implementarea bazată pe unire are același DAG de calcul ca inserarea și ștergerea unui singur element. ${\ displaystyle {\ text {O}} \ left (m \ log \ left ({n \ over m} +1 \ right) \ right)}$ ${\ displaystyle m}$ ${\ displaystyle n \; (\ geq m)}$ ${\ displaystyle {\ text {O}} (\ log m \ log n)}$ ${\ displaystyle m = 1}$

Reechilibrarea

Dacă în timpul unei operații de modificare diferența de înălțime între doi subarbori copii se schimbă, aceasta poate, atât timp cât este <2, să se reflecte printr-o adaptare a informațiilor de echilibru la părinte. În timpul operațiilor de inserare și ștergere poate apărea o diferență de înălțime (temporară) de 2, ceea ce înseamnă că subarborele părinte trebuie „reechilibrat”. Instrumentele de reparare date sunt așa-numitele rotații ale copacului , deoarece deplasează tastele doar „vertical”, astfel încât secvența („orizontală”) în ordine a tastelor să fie complet păstrată (ceea ce este esențial pentru un arbore de căutare binară ).

Fie X nodul care are un factor de echilibru (temporar) de -2 sau +2. Subarborele din stânga sau din dreapta a fost modificat. Să fie Z copilul superior (vezi figurile 2 și 3). Rețineți că ambii copii sunt în formă AVL prin ipoteză de inducție .

În caz de inserție, această inserție s-a întâmplat cu unul dintre copiii lui Z într-un mod în care înălțimea lui Z a crescut. În caz de ștergere, această ștergere s-a întâmplat cu fratele t ₁ din Z într-un fel, astfel încât înălțimea lui t ₁ fiind deja mai mică a scăzut. (Acesta este singurul caz în care factorul de echilibru al lui Z poate fi, de asemenea, 0.)

Există patru variante posibile ale încălcării:

Corect corect	==> Z este un drept	copil al părintelui său X și BF (Z) ≥ 0
Stânga Stânga	==> Z este o stânga	copil al părintelui său X și BF (Z) ≤ 0
Dreapta stanga	==> Z este un drept	copil al părintelui său X și BF (Z) <0
Stanga dreapta	==> Z este o stânga	copil al părintelui său X și BF (Z)> 0

Și reechilibrarea se efectuează diferit:

Corect corect	==> X se reechilibrează cu un	simplu	rotație `rotate_Left`	(vezi figura 2)
Stânga Stânga	==> X se reechilibrează cu un	simplu	rotație `rotate_Right`	(imagine oglindă din figura 2)
Dreapta stanga	==> X se reechilibrează cu un	dubla	rotație `rotate_RightLeft`	(vezi figura 3)
Stanga dreapta	==> X se reechilibrează cu un	dubla	rotație `rotate_LeftRight`	(imagine oglindă din figura 3)

Astfel, situațiile sunt notate ca CB , unde C (= direcția copilului) și B (= echilibru) provin din setul { Stânga , Dreapta } cu Dreapta : = - Stânga . Încălcarea echilibrului cazului C == B este reparată printr-o rotație simplă rotate_(- C ), în timp ce cazul C ! = B este reparat printr-o rotație dublă rotate_CB .

Costul unei rotații, fie simplu, fie dublu, este constant.

Rotație simplă

Figura 2 prezintă o situație corectă dreaptă. În jumătatea sa superioară, nodul X are doi copaci copii cu un factor de echilibru de +2 . Mai mult, copilul interior t ₂₃ din Z (adică, copilul stâng când Z este copil drept și copilul drept când Z este copilul stâng) nu este mai mare decât fratele său t ₄ . Acest lucru se poate întâmpla printr-o creștere a înălțimii subarborelui t ₄ sau printr-o scădere a înălțimii subarborelui t ₁ . În acest din urmă caz, poate apărea și situația palidă în care t ₂₃ are aceeași înălțime ca t ₄ .

Rezultatul rotației stânga este prezentat în jumătatea inferioară a figurii. Trebuie actualizate trei verigi (muchii groase din figura 2) și doi factori de echilibru.

Așa cum se arată în figură, înainte de inserare, stratul frunzelor era la nivelul h + 1, temporar la nivelul h + 2 și după rotație din nou la nivelul h + 1. În cazul unei ștergeri, stratul frunzelor a fost la nivelul h + 2, unde este din nou, când t ₂₃ și t ₄ au fost de aceeași înălțime. În caz contrar, stratul frunzelor atinge nivelul h + 1, astfel încât înălțimea arborelui rotit scade.

Fig. 2: Rotire simplă
rotate_Left ( X , Z )

Fragment de cod al unei simple rotații la stânga

Intrare:	X = rădăcina subarborelui care trebuie rotit la stânga
	Z = copilul drept al lui X, Z este drept-greu
	cu înălțime == $Înălțime (StângaSubtree ($ X $)) + 2$
Rezultat:	noua rădăcină a subarborelui reechilibrat

node *rotate_Left(node *X, node *Z) {
    // Z is by 2 higher than its sibling
    t23 = left_child(Z); // Inner child of Z
    right_child(X) = t23;
    if (t23 != null)
        parent(t23) = X;
    left_child(Z) = X;
    parent(X) = Z;
    // 1st case, BF(Z) == 0,
    //   only happens with deletion, not insertion:
    if (BF(Z) == 0) { // t23 has been of same height as t4
        BF(X) = +1;   // t23 now higher
        BF(Z) = –1;   // t4 now lower than X
    } else
    { // 2nd case happens with insertion or deletion:
        BF(X) = 0;
        BF(Z) = 0;
    }
    return Z; // return new root of rotated subtree
}

Rotație dublă

Figura 3 prezintă o situație din stânga dreapta. În treimea superioară, nodul X are doi copaci copii cu un factor de echilibru de +2 . Dar, spre deosebire de figura 2, copilul interior Y al lui Z este mai mare decât fratele său t ₄ . Acest lucru se poate întâmpla prin inserarea lui Y în sine sau o creștere a înălțimii unuia dintre subarborii săi t ₂ sau t ₃ (cu consecința că sunt de înălțime diferită) sau printr-o scădere a înălțimii subarborelui t ₁ . În acest din urmă caz, se poate întâmpla și ca t ₂ și t ₃ să aibă aceeași înălțime.

Rezultatul primei rotații din dreapta este prezentat în treimea mijlocie a figurii. (În ceea ce privește factorii de echilibru, această rotație nu este de același tip ca și celelalte rotații AVL, deoarece diferența de înălțime între Y și t ₄ este doar 1.) Rezultatul rotației finale stânga este prezentat în treimea inferioară a figurii. Cinci legături (muchii groase din figura 3) și trei factori de echilibru trebuie actualizați.

Așa cum se arată în figură, înainte de inserare, stratul frunzelor era la nivelul h + 1, temporar la nivelul h + 2 și după dubla rotație din nou la nivelul h + 1. În cazul unei ștergeri, stratul frunzelor a fost la nivelul h + 2 și după dubla rotație este la nivelul h + 1, astfel încât înălțimea arborelui rotit scade.

Fig. 3: Rotire dublă rotate_RightLeft ( X , Z )
= rotate_Right în jurul valorii de Z urmată de
rotate_Left în jurul valorii de X

Fragment de cod al unei rotiri duble dreapta-stânga

Intrare:	X = rădăcina subarborelui de rotit
	Z = copilul său drept, greu la stânga
	cu înălțime == $Înălțime (StângaSubtree ($ X $)) + 2$
Rezultat:	noua rădăcină a subarborelui reechilibrat

node *rotate_RightLeft(node *X, node *Z) {
    // Z is by 2 higher than its sibling
    Y = left_child(Z); // Inner child of Z
    // Y is by 1 higher than sibling
    t3 = right_child(Y);
    left_child(Z) = t3;
    if (t3 != null)
        parent(t3) = Z;
    right_child(Y) = Z;
    parent(Z) = Y;
    t2 = left_child(Y);
    right_child(X) = t2;
    if (t2 != null)
        parent(t2) = X;
    left_child(Y) = X;
    parent(X) = Y;
    // 1st case, BF(Y) == 0,
    //   only happens with deletion, not insertion:
    if (BF(Y) == 0) {
        BF(X) = 0;
        BF(Z) = 0;
    } else
    // other cases happen with insertion or deletion:
        if (BF(Y) > 0) { // t3 was higher
            BF(X) = –1;  // t1 now higher
            BF(Z) = 0;
        } else {
            // t2 was higher
            BF(X) = 0;
            BF(Z) = +1;  // t4 now higher
        }
    BF(Y) = 0;
    return Y; // return new root of rotated subtree
}

Comparație cu alte structuri

Atât arborii AVL, cât și arborii roșu-negru (RB) sunt arbori binați de căutare auto-echilibrați și sunt corelați matematic. Într-adevăr, fiecare copac AVL poate fi colorat roșu-negru, dar există arbori RB care nu sunt echilibrați AVL. Pentru menținerea resp. AVL Invarianții arborelui RB, rotațiile joacă un rol important. În cel mai rău caz, chiar și fără rotații, inserțiile sau ștergerile AVL sau RB necesită inspecții $O (log n)$ și / sau actualizări ale factorilor de echilibru AVL resp. Culori RB. Inserțiile și ștergerile RB și inserțiile AVL necesită de la zero la trei rotații recursive în coadă și rulează în timp amortizat $O (1)$ , deci la fel de constant în medie. Ștergerile AVL care necesită rotații $O (log n)$ în cel mai rău caz sunt, de asemenea, $O (1)$ în medie. Arborii RB necesită stocarea unui bit de informații (culoarea) în fiecare nod, în timp ce arborii AVL folosesc în cea mai mare parte doi biți pentru factorul de echilibru, deși, atunci când sunt păstrați la copii, este suficient un bit cu semnificația „mai mic decât fratele”. Diferența mai mare între cele două structuri de date este limita lor de înălțime.

Pentru un copac de dimensiuni $n \geq 1$

înălțimea unui copac AVL este cel mult
${\ displaystyle {\ begin {array} {ll} h & \ leqq \; c \ log _ {2} (n + d) + b \\ & <\; c \ log _ {2} (n + 2) + b \ end {array}}}$

unde raportul de aur , și .

{\ displaystyle \ varphi: = {\ tfrac {1 + {\ sqrt {5}}} {2}} \ approx 1.618}

{\ displaystyle c: = {\ tfrac {1} {\ log _ {2} \ varphi}} \ aproximativ 1.440,}

{\ displaystyle b: = {\ tfrac {c} {2}} \ log _ {2} 5-2 \ approx \; - 0.328,}

{\ displaystyle d: = 1 + {\ tfrac {1} {\ varphi ^ {4} {\ sqrt {5}}}} \ approx 1.065}

înălțimea unui copac RB este cel mult
${\ displaystyle {\ begin {array} {ll} h & \ leqq \; 2 \ log _ {2} (n + 1) \ end {array}}}$ .

Arborii AVL sunt mai echilibrați rigid decât arborii RB cu o relație asimptotică AVL / RB ≈0.720 a înălțimilor maxime. Pentru inserții și ștergeri, Ben Pfaff arată în 79 de măsurători o relație de AVL / RB între 0,667 și 1,077 cu mediana ≈0,947 și medie geometrică ≈0,910.

Vezi si

Referințe

^ ^a ^b ^c ^d ^e ^f Eric Alexander. „Copaci AVL” . Arhivat din original la 31 iulie 2019.CS1 maint: URL inadecvat ( link )
^ Sedgewick, Robert (1983). „Copaci echilibrați” . Algoritmi . Addison-Wesley. p. 199 . ISBN 0-201-06672-6.
^ Adelson-Velsky, Georgy; Landis, Evgenii (1962). „Un algoritm pentru organizarea informațiilor”. Lucrările Academiei de Științe a URSS (în rusă). 146 : 263–266. Traducere în limba engleză de Myron J. Ricci în matematica sovietică - Doklady , 3: 1259–1263, 1962.
^ ^a ^b Pfaff, Ben (iunie 2004). „Analiza performanței BST-urilor în software-ul sistemului” (PDF) . Universitatea Stanford .
^ Arborii AVL nu sunt echilibrați în greutate? (adică: copacii AVL nu sunt echilibrați în μ?)
Prin urmare: Un arbore binar se numește -echilibrat , cu, dacă pentru fiecare nod, inegalitatea ${\ displaystyle \ mu}$ ${\ displaystyle 0 \ leq \ mu \ leq {\ tfrac {1} {2}}}$ ${\ displaystyle N}$
${\ displaystyle {\ tfrac {1} {2}} - \ mu \ leq {\ tfrac {| N_ {l} |} {| N | +1}} \ leq {\ tfrac {1} {2}} + \ mu}$
deține și este minim cu această proprietate. este numărul de noduri sub copac cu rădăcină (inclusiv rădăcina) și este nodul copil stâng al . ${\ displaystyle \ mu}$ ${\ displaystyle | N |}$ ${\ displaystyle N}$ ${\ displaystyle N_ {l}}$ ${\ displaystyle N}$
^ ^a ^b ^c ^d Knuth, Donald E. (2000). Sortare și căutare (2. ed., 6. tipărire, recent actualizată și ed. Rev.). Boston [ua]: Addison-Wesley. ISBN 0-201-89685-0.
^ Rajinikanth. "Arborele AVL: Structuri de date" . btechsmartclass.com . Adus 09-03-2018 .
^ Dixit, JB (2010). Stăpânirea structurilor de date prin limbajul „C” . New Delhi, India: University Science Press, o amprentă a Laxmi Publications Pvt. Ltd. ISBN 9789380386720. OCLC 939446542 .
^ ^a ^b ^c Brass, Peter (2008). Structuri avansate de date . Cambridge: Cambridge University Press. ISBN 9780511438202. OCLC 312435417 .
^ Hubbard, John Rast (2000). Schița teoriei lui Schaum și problemele structurilor de date cu Java . New York: McGraw-Hill. ISBN 0071378707. OCLC 48139308 .
^ ^a ^b ^c Pfaff, Ben (2004). Introducere în copacii de căutare binari și copacii echilibrați . Free Software Foundation, Inc.
^ Weiss, Mark Allen. (2006). Structuri de date și analiza algoritmului în C ++ (ediția a 3-a). Boston: Pearson Addison-Wesley. p. 145. ISBN 0-321-37531-9. OCLC 61278554 .CS1 maint: data și anul ( link )
^ ^a ^b Blelloch, Guy E .; Ferizovic, Daniel; Sun, Yihan (2016), „Doar alăturați-vă pentru seturi ordonate în paralel”, Simpozion pe algoritmi și arhitecturi paralele , ACM, pp. 253–264, arXiv : 1602.02120 , doi : 10.1145 / 2935764.2935768 , ISBN 978-1-4503-4210-0, S2CID 2897793.
^ Paul E. Black (13.04.2015). „Arborele AVL” . Dicționar de algoritmi și structuri de date . Institutul Național de Standarde și Tehnologie . Adus 02/07/2016 .
^ Mehlhorn & Sanders 2008 , pp. 165, 158
^ Dinesh P. Mehta, Sartaj Sahni (Ed.) Manual de structuri și aplicații de date 10.4.2
^ Arborele roșu-negru # Dovada limitelor asimptotice

Lecturi suplimentare

Donald Knuth . The Art of Computer Programming , Volumul 3: Sortare și căutare , ediția a treia. Addison-Wesley, 1997. ISBN 0-201-89685-0 . Pagini 458–475 din secțiunea 6.2.3: Copaci echilibrați.

linkuri externe

Acest articol încorporează material din domeniul public din documentul NIST : Black, Paul E. „AVL Tree” . Dicționar de algoritmi și structuri de date .

[wiscurl-1] ^ ^a ^b ^c ^d ^e ^f Eric Alexander. „Copaci AVL” . Arhivat din original la 31 iulie 2019.CS1 maint: URL inadecvat ( link )

[2] Sedgewick, Robert (1983). „Copaci echilibrați” . Algoritmi . Addison-Wesley. p. 199 . ISBN 0-201-06672-6.

[3] Adelson-Velsky, Georgy; Landis, Evgenii (1962). „Un algoritm pentru organizarea informațiilor”. Lucrările Academiei de Științe a URSS (în rusă). 146 : 263–266. Traducere în limba engleză de Myron J. Ricci în matematica sovietică - Doklady , 3: 1259–1263, 1962.

[Pfaff1-4] Pfaff, Ben (iunie 2004). „Analiza performanței BST-urilor în software-ul sistemului” (PDF) . Universitatea Stanford .

[5] Arborii AVL nu sunt echilibrați în greutate? (adică: copacii AVL nu sunt echilibrați în μ?)
Prin urmare: Un arbore binar se numește -echilibrat , cu, dacă pentru fiecare nod, inegalitatea ${\ displaystyle \ mu}$ ${\ displaystyle 0 \ leq \ mu \ leq {\ tfrac {1} {2}}}$ ${\ displaystyle N}$
${\ displaystyle {\ tfrac {1} {2}} - \ mu \ leq {\ tfrac {| N_ {l} |} {| N | +1}} \ leq {\ tfrac {1} {2}} + \ mu}$
deține și este minim cu această proprietate. este numărul de noduri sub copac cu rădăcină (inclusiv rădăcina) și este nodul copil stâng al . ${\ displaystyle \ mu}$ ${\ displaystyle | N |}$ ${\ displaystyle N}$ ${\ displaystyle N_ {l}}$ ${\ displaystyle N}$

[Knuth-6] Knuth, Donald E. (2000). Sortare și căutare (2. ed., 6. tipărire, recent actualizată și ed. Rev.). Boston [ua]: Addison-Wesley. ISBN 0-201-89685-0.

[7] Rajinikanth. "Arborele AVL: Structuri de date" . btechsmartclass.com . Adus 09-03-2018 .

[dixit-mastering-data-structures-8] Dixit, JB (2010). Stăpânirea structurilor de date prin limbajul „C” . New Delhi, India: University Science Press, o amprentă a Laxmi Publications Pvt. Ltd. ISBN 9789380386720. OCLC 939446542 .

[brass-advanced-data-structures-9] Brass, Peter (2008). Structuri avansate de date . Cambridge: Cambridge University Press. ISBN 9780511438202. OCLC 312435417 .

[hubbard-outline-theory-problems-10] Hubbard, John Rast (2000). Schița teoriei lui Schaum și problemele structurilor de date cu Java . New York: McGraw-Hill. ISBN 0071378707. OCLC 48139308 .

[Pfaff-11] Pfaff, Ben (2004). Introducere în copacii de căutare binari și copacii echilibrați . Free Software Foundation, Inc.

[12] Weiss, Mark Allen. (2006). Structuri de date și analiza algoritmului în C ++ (ediția a 3-a). Boston: Pearson Addison-Wesley. p. 145. ISBN 0-321-37531-9. OCLC 61278554 .CS1 maint: data și anul ( link )

[join-based-13] Blelloch, Guy E .; Ferizovic, Daniel; Sun, Yihan (2016), „Doar alăturați-vă pentru seturi ordonate în paralel”, Simpozion pe algoritmi și arhitecturi paralele , ACM, pp. 253–264, arXiv : 1602.02120 , doi : 10.1145 / 2935764.2935768 , ISBN 978-1-4503-4210-0, S2CID 2897793.

[14] Paul E. Black (13.04.2015). „Arborele AVL” . Dicționar de algoritmi și structuri de date . Institutul Național de Standarde și Tehnologie . Adus 02/07/2016 .

[15] Mehlhorn & Sanders 2008 , pp. 165, 158

[Dinesh-16] Dinesh P. Mehta, Sartaj Sahni (Ed.) Manual de structuri și aplicații de date 10.4.2

[17] Arborele roșu-negru # Dovada limitelor asimptotice

Languages

In other projects