====== 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
{{https://upload.wikimedia.org/wikipedia/commons/c/c4/Tree_Rebalancing.gif?800}}
===== Uložení dat =====
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.
===== Vkládání prvků do stromu =====
Nejprve vložíme nový prvek do stromu, tak jako v nevyvážených stromech
[[zalg:strom_add#Vkladani prvku do stromu|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
}
}
==== Levý podstrom je příliš vysoký =====
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 */
}
==== V levém podstromu je levý podstrom vyšší než pravý =====
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ýška nového stromu ===
:?: 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
==== V levém podstromu je pravý podstrom vyšší nebo stejně vysoký =====
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.
===== Celý program =====
#include
#include
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
{{zalg:avltree.png}}