Invariantas, kurį galima garantuoti

Vienuoliktos pamokos mazgas gauna vieną naują lauką — savo paties aukštį — ir iš to išauga visa garantija.

Balanso koeficientas

balance(n) = aukštis(n.left) − aukštis(n.right)

AVL invariantas: kiekvienam mazgui balance(n) yra −1, 0 arba +1.

Ne „medis atrodo tvarkingai", o tikrinama sąlyga kiekviename mazge. Todėl ją ir galima garantuoti, o ne tikėtis.

Kodėl to užtenka

Kodėl vietinė sąlyga apriboja viso medžio aukštį? Pažiūrėk atvirkščiai: koks mažiausias mazgų skaičius, kuriuo dar galima pastatyti h aukščio AVL medį?

Šaknis turi bent vieną h−1 aukščio pomedį, o antrasis pagal invariantą negali būti žemesnis nei h−2. Vadinasi:

N(h) = 1 + N(h−1) + N(h−2)

Tai Fibonacci. Mazgų skaičius auga eksponentiškai pagal aukštį, taigi aukštis auga logaritmiškai pagal mazgų skaičių. Tiksliai:

h ≤ 1.4405 · log2(n + 2) − 0.3277

Įsidėmėk šitą eilutę: testas tikrina būtent ją, o ne kokį iš akies paimtą skaičių.

Rotacija

Rotacija perstato tris rodykles ir pakeičia aukštį, nepažeisdama BST invarianto. Būtent tai ją ir daro naudinga.

      n                b
     / \              / \
    b   C    =>      A   n
   / \                  / \
  A   x                x   C

Sek raktus. Prieš rotaciją x yra b dešinėje, taigi x > b; ir b pomedyje po n kaire, taigi x < n. Po rotacijos x yra n kairėje — vis dar tarp b ir n. Vienintelė vieta, kur jis gali būti, ir ten jis nukeliauja.

Antra kryptis — veidrodinė.

Keturi atvejai, iš kurių du yra tie patys

Kai mazgas nebeatitinka invarianto, nuokrypis atsirado viename iš keturių jo anūkų. Du „išoriniai" taisomi viena rotacija; du „vidiniai" — pirma paverčiami išoriniais:

rebalance(n):
    fix(n)                                  // perskaičiuok n aukštį
    b ← balance(n)

    jei b > 1  ir balance(n.left) ≥ 0:      // kairė-kairė
        grąžink rotateRight(n)

    jei b > 1:                              // kairė-dešinė
        n.left ← rotateLeft(n.left)         //   paversk kairė-kaire
        grąžink rotateRight(n)

    jei b < −1 ir balance(n.right) ≤ 0:     // dešinė-dešinė
        grąžink rotateLeft(n)

    jei b < −1:                             // dešinė-kairė
        n.right ← rotateRight(n.right)      //   paversk dešinė-dešine
        grąžink rotateLeft(n)

    grąžink n

Vidiniai atvejai nėra nauja mechanika — tai tos pačios dvi rotacijos, pritaikytos du kartus. Užrašyti reikia keturis atvejus; suprasti — vieną veiksmą ir jo veidrodį.

Kur tai iškviečiama

Įterpimas tampa rekursinis, nes taisyti reikia grįžtant atgal:

insert(n, item):
    jei n = nil:                    grąžink naują lapą
    c.Hit()
    jei item.Title < n.key:         n.left  ← insert(n.left, item)
    jei item.Title > n.key:         n.right ← insert(n.right, item)
    kitaip:                         n.item ← item; grąžink n

    grąžink rebalance(n)            // ← visas skirtumas nuo 11 pamokos

Vienuoliktoje pamokoje ta paskutinė eilutė buvo grąžink n. Viskas kita — ta pati funkcija.

Nusileidus keliu iki lapo, grįžtama tuo pačiu keliu ir kiekvienas mazgas jame patikrinamas. Kelio ilgis yra O(log n), tad ir patikrinimų — O(log n). Faktinių rotacijų būna gerokai mažiau; kiek — pamatuosi šeštame žingsnyje.