AVL strom je varianta binárního vyhledávacího stormu, kdy vyváženost každého vrcholu v něm je rovna 1, 0 nebo -1. Vyváženost vrcholu x je rozdíl výšky levého podstromu a výšky pravého podstromu vrcholu x. Výšku prázdného podstromu definujeme rovnu -1.
Strom je přípustný, pokud je vyváženost každého vrcholu v něm rovna 1, 0, nebo -1.
Existuje konstanta c > 0 tak, že výška každého přípustného stromu s n vrcholy je menší nebo rovna c lg n.
Pokud bychom nechali operasce insert a delete stejné jako u klasického binárního vyhledávacího stromu, tak by se náš AVL strom mohl stát nepřípustným. Hodnota bf by tedy byla v absolutní hodnotě větší jak 1.
Do struktury node přidáme položku bf pro vyváženost vrcholu, díky níž budeme udržovat strom konzistentní. Odebírání i přidávání prvku budeme provádět stejně jako BVS, ale poté projdeme cestu od místa změny do kořene a upravíme položku bf. Pokud bude někde položka bf nepřípustná, tak situaci opravíme pomocí rotací.
| podstrom | výška se zvětšila | výška se zmenšila |
|---|---|---|
| x.left | bf += 1 | bf -= 1 |
| x.right | bf -= 1 | br += 1 |
Pokud má položka bf hodnotu 2 nebo -2, jedná se o nepovolenou hodnotu a budeme to muset řešit.
Pro uzel s hodnotou bf 2 budeme využívat pravou nebo levo-pravou rotaci. Pro uzel s hodnotou bf -2 budem epoužívat levou nebo pravo-levou rotaci.
Jedná se o kombinaci levé a pravé rotace, jak již název napovídá. První provedeme levou rotace na levý podstrom kořene a následně provedeme pravou rotaci na kořen.
Úkol bude zadán i vypracován na hodině. V případě absence mě kontaktujte.