6 - AVL + B-strom

Přednáška 6 v oddíle Přednášky.

Název je podle autorů (Adelson-Velsky a Landis), nemá význam. AVL udržuje vyváženost stromu a tak zajišťuje logaritmickou složitost operací. Potřeba vyvažovat se zjišťuje z rozdílu hloubek podstromů daného uzlu. Pokud je větší než 1, provádíme rotaci:

• Jednoduché rotace - když je větší hloubka na stejné straně (uzel i jeho potomek na hlubší straně mají hlubší podstrom na stejné straně), nebo mají oba podstromy na hlubší straně stejnou hloubku.
  • R rotace - rotace doprava - levý podstrom je o 2 hlubší než pravý podstrom, a kořen levého podstromu (levý potomek) má taktéž hlubší podstrom u levého potomka, nebo jsou oba jeho podstromy stejně hluboké
  • L rotace - rotace doleva - pravý podstrom je o 2 hlubší než levý podstrom, a kořen pravého podstromu (pravý potomek) má taktéž hlubší podstrom u pravého potomka, nebo jsou oba jeho podstromy stejně hluboké

• Dvojité rotace - když je větší hloubka na jiné straně (uzel a jeho potomek na hlubší straně mají hlubší podstrom na různých stranách)
  • LR rotace - L rotace v levém potomkovi a pak R rotace - levý podstrom je o 2 hlubší než pravý podstrom, a kořen levého podstromu (levý potomek) má hlubší podstrom u pravého potomka
  • RL rotace - R rotace v pravém potomkovi a pak L rotace - pravý podstrom je o 2 hlubší než levý podstrom, a kořen pravého podstromu (pravý potomek) má hlubší podstrom u levého potomka

Kontrolujeme takto každý uzel po cestě zpět do kořene, při vkládání i mazání. Jinak vše probíhá jako u BVS.

Vizualizace AVL s vlastním vkládáním a mazáním, včetně krokování: https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

Speciální strom, který není binární a uzly mohou obsahovat více než jeden klíč. Název také není intuitivní.

Pro B-strom řádu $k$ platí:

• Listy jsou ve stejné hloubce
• Všechny uzly kromě kořene obsahují maximálně $2k$ a minimálně $k$ uspořádaných klíčů
• Každý uzel (kromě listů) má o 1 víc potomků, než má klíčů

Vkládání: Jakmile je uzel přeplněn, jeho $2k + 1$ klíčů se rozdělí na dvakrát $k$ klíčů a prostřední klíč (ten $+1$). Vytvoří se nový uzel hned vedle původního a prostřední klíč se posune o patro výš, kde se doplní napravo od původního ukazatele na uzel, a jako potomka napravo bude mít uzel s pravou polovinou klíčů co jsme rozdělili. Musíme pak zkontrolovat rodiče, protože jsme do něj přidali jeden klíč navíc, takže je možné, že pak bude třeba obsloužit přeplnění rodiče, a možná i prarodiče atd., rekurzivně směrem ke kořeni. Klíče nerotují na rozdíl od mazání.

Mazání: Jakmile je uzel příliš prázdný, jeho $k - 1$ klíčů se doplní z levého nebo pravého sourozence, “rotací” klíčů přes rodiče. Pokud mají oba $k$ prvků (případně jeden z nich neexistuje - jsme na kraji), sloučíme uzel se sousedem na jedné straně a s odpovídajícím klíčem v rodiči. Klíčů v takto vytvořeném uzlu bude $(k-1) + 1 + k$, tedy $2k$. Musíme pak zkontrolovat rodiče, protože jsme z něj odebrali jeden klíč.

Vizualizace B-stromu s vlastním vkládáním a mazáním, včetně krokování: https://www.cs.usfca.edu/~galles/visualization/BTree.html

Poznámka: Někdy se jako řád uvádí maximální počet potomků uzlu, protože to je obecnější (umožňuje to lichá maxima počtu klíčů v uzlu). Minimum klíčů v uzlu (mimo kořen) je pak $\left\lfloor \frac{k}{2} \right\rfloor$.

Řešená úloha 1: Čísla ze zadané posloupnosti postupně vkládejte do prázdného AVL vyhledávacího stromu, který podle potřeby vyvažujete.

13, 11, 10, 15, 5, 21, 8, 4, 24, 17, 6, 18, 7

Jaké se provádí rotace?

Po vkládání (rozbalit)

Poté z něj odstraňte 13, 11, 5, 24, 17 a 18. Při mazání nahrazujte nejmenším klíčem v pravém podstromu.

Po mazání (rozbalit)

Řešená úloha 2: Zdůvodněte pravdivost/nepravdivost tvrzení: Existuje AVL strom, v němž levý podstrom kořene obsahuje 4 uzly a pravý podstrom kořene obsahuje alespoň 12 uzlů.

Řešení (rozbalit)

Řešená úloha 3: Vybudujte B-strom řádu 1 tak, že do nejprve prázdného stromu vložíte postupně v uvedeném pořadí následující klíče:

18, 31, 59, 20, 23, 24, 36, 60, 58, 15

Po vkládání (rozbalit)

Poté v uvedeném pořadí odstraňte klíče 20, 24, 23, 36 a 60. Při mazání taktéž nahrazujte nejmenším vyšším klíčem (nejlevějším v pravém podstromu).

Po mazání (rozbalit)

Úloha 4: Na obrázku je uveden AVL strom. Odstraňte z něj operací delete uzly s klíči 50, 30, 25 v tomto pořadí. Rozhodněte, zda a jaké rotace budou během této úpravy použity.

Výsledek

Úloha 5: Pro tentýž strom jako v zadání úlohy 4 (před mazáním) proveďte operaci insert s klíči 45, 57, 13 v tomto pořadí. Rozhodněte, zda a jaké rotace budou během této úpravy použity.

Výsledek

Úloha 6: Do prázdného AVL stromu postupně vkládáme klíče 23, 11, 24, 31, 17, 20, 30 a 25. Jak bude vypadat strom po vložení všech klíčů?

Výsledek

Úloha 7: Do prázdného AVL stromu postupně vkládáme klíče 25, 30, 20, 17, 31, 24, 11 a 12. Jak bude vypadat strom po vložení všech klíčů?

Výsledek

Úloha 8: Jaký je minimální možný počet uzlů v AVL stromu s hloubkou 4? (Hloubka kořene je vždy 0). Nakreslete příslušný AVL strom.

Pokročilejší varianta: Jaký je minimální možný počet uzlů v AVL stromu s hloubkou D > 0?

Úloha 9: Jednoduchá levá rotace v uzlu $u$ má operační složitost

a) závislou na výšce levého podstromu uzlu $u$
b) mezi $\textrm{O}(1)$ a $\Theta(n)$
c) závislou na hloubce uzlu $u$
d) konstantní

Úloha 10: Kolik jednoduchých rotací se maximálně provede při jedné operaci Insert v AVL stromu s n uzly?

a) $1$
b) $2$
c) $\log n$
d) $n$

Úloha 11: LR rotace v uzlu $u$ má operační složitost

a) závislou na hloubce uzlu $u$
b) $\Theta(\log n)$
c) konstantní
d) lineární

Úloha 11: Nakreslete AVL strom s 8 číselnými klíči tak, aby po vložení klíče s hodnotou 19 bylo nutno provést

a) L rotaci v kořeni,
b) L rotaci v uzlu, který není kořenem,
c) LR rotaci v kořeni,
d) LR rotaci v uzlu, který není kořenem.

Úloha 12: Docent Omylný tvrdí, že vždy, když se AVL strom vyváží některou z rotací (jednoduchou nebo dvojitou) následující po smazání uzlu, sníží se tím také hloubka celého AVL stromu. Najděte k tomuto tvrzení protipříklad.

Úloha 13: Napište proceduru strom leváRotace(strom s). Napřed si namalujte obrázek a rozmyslete si, kterých ukazatelů se změna dotkne.

Úloha 14: Předpokládejme, že každý uzel AVL stromu obsahuje reference (ukazatele, pointry) na oba své potomky a na svého rodiče (reference obsahují NIL, pokud příslušné objekty neexistují).

• Určete, kolik maximálně referencí změní svou hodnotu při jednoduché pravé rotaci v takto reprezentovaném AVL stromu.
• Napište funkci, která provede pravou rotaci v uzlu x. Uzel x bude parametrem funkce. Funkce vrátí ukazatel na uzel, který byl před zahájením rotace levým potomkem x.

Úloha 15: Naimplementujte metodu, která ověří, zda daný binární strom je AVL stromem.

Úloha 16: Do B-stromu znázorněného na obrázku vložíme postupně klíče 14, 10.

Jak bude strom poté vypadat?

Úloha 17: Do B-stromu znázorněného na obrázku vložíme postupně klíče 7, 5.

Jak bude strom poté vypadat?

Úloha 18: Z B-stromu znázorněného na obrázku odebereme postupně klíče 4, 35. Pak bude kořen obsahovat klíč/klíče…

a) 18
b) 18, 28
c) 20
d) 20, 28
e) 28

Jak bude poté vypadat celý strom?

Úloha 19: Z B-stromu znázorněného na obrázku odebereme postupně klíče 18, 2. Pak bude kořen obsahovat klíč/klíče…

a) 8
b) 8, 16
c) 10
d) 10, 12
e) 13

Jak bude poté vypadat celý strom?

Úloha 20: Klíče $1, 2, 3, 4, \ldots, 12$ v tomto pořadí vložte do prázdného B-stromu řádu 2. Jak bude vypadat výsledný strom?

Ověřte si řešení s vizualizačním programem.

Úloha 21: B-strom je řádu 10 a máme do něj umístit 100 000 klíčů. Jaká je maximální a minimální možná hloubka tohoto stromu?

Pokročilé: Jaký je maximální a minimální možný počet uzlů tohoto stromu?