Vyvážené stromy

Kapitola 6.1 ve skriptech
http://cs.wikipedia.org/wiki/AVL-strom
http://en.wikipedia.org/wiki/AVL_tree
Niklaus Wirth: Algoritmy + datové struktury = programy

Binární ohodnocené stromy.

Pro všechny uzly stromu musí platit, že
výšky podstromů se liší nejvýše o 1.

Animace: http://en.wikipedia.org/wiki/Tree_rotation

Obrázek z Wikipedie

Jednotlivé uzly stromu budeme skladovat v datové struktuře Item.

struct Item
{
    int key;      // ulozena hodnota
    int height;   // vyska stromu zacinajiciho timto prvkem
    Item * left;  // levy podstrom s hodnotami < key (nebo nullptr, pokud levy podstrom neexistuje
    Item * right; // pravy podstrom s honotami > key
    Item ();      // konstruktor jednoho prvku
};

Konstruktor struktury / třídy Item.

Item::Item ()     // trida Item a v ni funkce, ktera se jmenuje stejne jako trida 
   :              // nezapomente na dvojtecku pred inicializaci promennych
   key (0), 
   height (1),     // vyska jedoprvkoveho stromu
   left (nullptr), 
   right (nullptr) // levy a pravy podstrom prozatim neexistuje 
{ }                // zde jiz neni co delat

Pomocná funkce h určí výšku podstromu.
Pro prázdý podstrom vrací 0
Jinak vrací uloženou hodnotu height

inline int h (Item * p)
{
    if (p == nullptr)
        return 0;
    else
        return p->height;
}

Funkce h nesmí rekurzivně prohlížet celý podstrom, to by nám zkazilo složitost.
Funkci nemohu umístit do třídy Item jako metodu, pro prázdné podstromy bude volána s nulovým parametrem.
Klíčové slovo inline doporučuje překladači v místě volání podprogramu rozepsat tělo funkce

Značka pro poznámky o složitosti.
Značka pro poznámky, které napoprvé asi vynecháte.

Funkce update nastaví hodnotu height na základě hodnot height v levém a pravém podstromu

void update (Item * p)
{
    int L = h (p->left);  
    int R = h (p->right);
    if (L > R)
        p->height = L + 1; // vyska leveho podstromu + 1 za nas prvek
    else
        p->height = R + 1;
}

Opět nesmíme rekurzivně prohlížet celý podstrom.

Nejprve vložíme nový prvek do stromu, tak jako v nevyvážených stromech funkce insert, vkládání prvku do stromu

void enter (Item * & root, int val)
{
    if (root == nullptr)
    {
        root = new Item;
        root->key = val;
    }
    else if (val < root->key) enter (root->left, val);
    else if (val > root->key) enter (root->right, val);
    else { } // hodnota je již ve stromu uložena
 
    /* v tomto místě se ocitneme po vložení nového prvku do stromu
       a později když se budeme "vynořovat" z předešlých funkcí enter */
}

Po vložení nového prvku a po každém volání funkce enter
musíme zkontrolovat výšky podstromů a případně přeuspořádat prvky.

    update (root);          // nastavíme root->height na základě hodnot v levém a prvém podstromu.
    int L = h(root->left);  // L = výška levého podstromu
    int R = h(root->right);
    Item * a = root;        // do proměnné a uložíme ukazatel na kořen našeho podstromu,
                            // referenční proměnná root se může změnit
 
    if (L > R + 1)
    {
       // levý podstrom je příliš vysoký
    }
    else if (R > L + 1)
    {
       // pravý podstrom je příliš vysoký
    }
    else
    {
       // výšku stromů se liší nejvýše o 1, nebudeme nic upravovat
    }
}

Variantu, kdy levý podstrom je příliš vysoký.
( Varianta s příliš vysokým pravým podstromem je symetrická, nebudeme ji popisovat. )

                  a
                  |
         ---------.
         |
         b
         |
   .----------.
   |          |
   C          D

Prvky a, b určitě existují. Podstromy C a D mohou být prázdné.

Podívejme se výšky podstromů C a D v levém podstromu.
Zde posuzujeme zda výška C je větší než výška D, potom nastane varianta Left Left Case na obrázku z Wikipedie.
V případě, že výška C je menší nebo rovna výšce D, nastane varianta Left Right Case.

        Item * b = a->left;    // b = kořen levého podstromu
        int LL = h (b->left);  // LL = výška levého podstromu v levého podstromu  ( C ) 
        int RR = h (b->right); // RR = výška pravého podstromu v levého podstromu ( D )
        if (LL > RR)
        {
            /* Left Left Case */
        }
        else
        {
            /* Left Right Case */
        }

Zde je můj neumělý náčrtek plánované akce nebo se podívejte na sloupec Left Left Case na obrázku z Wikipedie.

             a                                  b
        ------------                       -----------
        b          s          ---->        c          a
     --------                                      -------
     c      t                                      t     s

Tuto situaci zachycuje animace http://en.wikipedia.org/wiki/Tree_rotation

Prvek b se stane novým kořenem našeho podstromu.
Prvek c ponecháme vlevo pod b.
Prvek a spolu s jeho pravým podstromem s umístíme vpravo pod b.
Podstrom t který byl vpravo od b umístíme vlevo pod a (Ukazatel na t si schováme dříve, než na předchozím řádku připojíme a.

            Item * c = b->left; 
            //     a
            //   b
            // c
            Item * t = b->right; // podstrom
            root = b; // novy koren
            //     b
            //  c     a
            b->right = a;
            a->left = t;
            update (a); // vyska stromu se zmenila
            update (b); // az nakonec

V literatuře můžete najít zdůvodnění, proč strom s novým kořenem bude vyhovovat našemu požadavky na výšky podstromů.
Nebo si napište relace, které známe (včetně předpokladů, že podstromy na nižších úrovních náš požaddavek splňují) a
můžete se pokusit se dokázat, že výsledný strom také požadavek splňuje.

označíme si výšky v původním stromu: va = h(a), vb = h(b), atd.
v nově vzniklém stromu označíme na výšku podstromu s kořenem a, nb = h(b)

levý podstrom porušuje pravidlo: vb > vs+1
ale o patro níže bylo vše v pořádku: |vc - vt| < = 1

v levém podstromu je levý podstrom vyšší než pravý: vc > vt
tedy vb určeno hodnotou vc: vb = vc+1
z toho také plyne: vc > vs

v novém stromu uzel a má podstromy výšky vs a vt, vs < vc, vt < vc,
uzel a přidává sám jedno patro: na < = vc

celý nový strom b má podstromy výšky vc, na
a platí na ⇐ vc

Sloupec Left Right Case na obrázku z Wikipedie.

             a                                  c
        ------------                       -----------
        b          s          ---->        b          a
     --------                            -----      -----
     r      c                            r   t      u   s 
          -----
          t   u                                      

Tuto situaci zachycuje animace http://en.wikipedia.org/wiki/Tree_rotation

Prvek c se stane novým kořenem našeho podstromu.
Pod prvek c umístíme b a a.
Vpravo pod b připojíme t. Vlevo pod a připojíme u. Podstromy r a s zůstávají připojené stejně.

            Item * c = b->right; 
            //         a
            //   b
            //      c
            Item * t = c->left; // podstrom
            Item * u = c->right; // podstrom
            root = c; // novy koren
            //     c
            //  b     a
            c->left = b;
            c->right = a;
            b->right = t;
            a->left = u;
            update(a);
            update(b);
            update(c); // jako posledni

Obě pravé varianty jsou symentrické s levými.
Zbývá funkce print pro zobrazení stromu a funkce check pro kontrolu rostoucí posloupnosti hodnot.

#include <string>
#include <iostream>
using namespace std;
 
struct Item
{
    int key;
    int height;
    Item * left;
    Item * right;
    Item () : key (0), height(1), left (nullptr), right (nullptr) { }
};
 
inline int h (Item * p)
{
    if (p == nullptr)
        return 0;
    else
        return p->height;
}
 
void update (Item * p)
{
    int L = h (p->left);
    int R = h (p->right);
    if (L > R)
        p->height = L + 1;
    else
        p->height = R + 1;
}
 
void enter (Item * & root, int val)
{
    if (root == nullptr)
    {
        root = new Item;
        root->key = val;
    }
    else if (val < root->key) enter (root->left, val);
    else if (val > root->key) enter (root->right, val);
    else { }
 
    update (root);
    int L = h(root->left);
    int R = h(root->right);
    Item * a = root;
    if (L > R + 1)
    {
        Item * b = a->left;
        int LL = h(b->left);
        int RR = h(b->right);
        if (LL > RR)
        {
            Item * c = b->left;
            //     a
            //   b
            // c
            Item * t = b->right; // podstrom
            root = b; // novy koren
            //     b
            //  c     a
            b->right = a;
            a->left = t;
            update (a);
            update (b); // jako posledni
        }
        else
        {
            Item * c = b->right;
            //         a
            //   b
            //      c
            Item * t = c->left; // podstrom
            Item * u = c->right; // podstrom
            root = c; // novy koren
            //     c
            //  b     a
            c->left = b;
            c->right = a;
            b->right = t;
            a->left = u;
            update(a);
            update(b);
            update(c); // jako posledni
        }
    }
    else if (R > L + 1)
    {
        Item * b = a->right;
        int LL = h(b->right);
        int RR = h(b->left);
        if (LL > RR)
        {
            Item * c = b->right;
            //  a
            //     b
            //        c
            Item * t = b->left; // podstrom
            root = b; // novy koren
            //     b
            //  a     c
            b->left = a;
            a->right = t;
            update(a);
            update(b); // jako posledni
        }
        else
        {
            Item * c = b->left;
            //  a
            //        b
            //     c      
            Item * t = c->right; // podstrom
            Item * u = c->left; // podstrom
            root = c; // novy koren
            //     c
            //  a     b
            c->right = b;
            c->left = a;
            b->left = t;
            a->right = u;
            update(a);
            update(b);
            update(c); // jako posledni
        }
    }
}
 
void print (Item * branch, int level = 0)
{
    if (branch != nullptr) 
    {
        for (int i = 0; i < level; i++) 
            cout << "-";
 
        cout << branch->key << " (" << branch->height << ")" << endl;
 
        print (branch->left, level+1);
        print (branch->right, level+1);
    }
}
 
bool ok;
bool first;
int  last_value;
 
void checkBranch (Item * branch)
{
    if (branch != nullptr)
    {
        checkBranch (branch->left);
 
        if (! first)
           if (last_value >= branch->key)
           {
               cout << "CHYBA" << endl;
               ok = false;
           }
 
        last_value = branch->key;
        first = false;
        checkBranch (branch->right);
    }
}
 
void check (Item * root)
{
   ok = true;
   first = true;
   checkBranch (root);
   if (ok) cout << "O.K." << endl;
}
 
int main()
{
    Item * root = nullptr;
 
    const int N = 32;
    // const int N = 16*1024;
 
    for (int k = 1; k <= N; k++)
       enter (root, k);
 
    if (N <= 1000)
       print (root);
 
    cout << "Vyska stromu " << h(root) << endl;
    check (root);
}

Případně varianta pro Qt http://gitlab.fjfi.cvut.cz/culikzde/zalg/-/tree/master/avltree-qt