Pokud chceme, aby se strom, který budujeme, nikdy nezvrhl v seznam, můžeme se uchýlit k vyvažování. Vyvažování je technika, jak zabránit tomu, aby se stromy příliš zhoršily. Budeme zde diskutovat pouze o hlavní myšlence algoritmu a detaily implementace ponecháme na nezávislá cvičení.
Výška stromu je délka jeho nejdelší větve. Strom má kořen, levý podstrom a pravý podstrom. V ideálním stromě je výška h L levého podstromu rovna výšce h R pravého podstromu. Nazvěme strom vyváženým, pokud se výšky levého a pravého podstromu pro každý vrchol neliší o více než jednu.
Vyvážené stromy nejsou tak špatné. Zejména ideální stromy jsou vyvážené (ty nejlepší). Nejhůře vyváženými stromy jsou tzv. Fibonacciho stromy. Příkladem Fibonacciho stromu je binární strom získaný postupným vytvářením vrcholů s informačními poli 8, 5, 11, 3, 7, 10, 12, 2, 4, 6, 7, 9, 1. Podle Adelson-Velského a Landisova věta, výška vyváženého stromu nepřesahuje velikost , tzn. ne více než jedenapůlnásobek výšky ideálního stromu.
Ve třetím případě, když je zapnutý vrchol, je strom rekonstruován.
co se dá dělat? Je vidět, že větve jednoho z podstromů, například levého, příliš klesly. Řešením by mohlo být: zvednout levý podstrom o jednu a současně snížit pravý podstrom o jednu. Tato úprava má za následek změnu kořene. Zvednutím levého podstromu (včetně kořene podstromu) uděláme úroveň kořene podstromu vyšší, než je kořen celého stromu. Proto se kořen levého podstromu stane kořenem celého stromu. Je také nutné změnit některá spojení mezi vrcholy: protože kořeny mění role, jsou také obráceny vztahy „předek-potomek“.
Pro usnadnění další prezentace zavádíme následující zápis: h(t) je výška stromu t; t = vuw je strom skládající se z levého podstromu v, kořene a u pravého podstromu w.
Je jasné, že platí vztah h(t) = 1 + max(h(v), h(w)).
Nechť nastane rovnost h(v) = h(w)+l, než bude nový vrchol zahrnut do levého podstromu. Představme si, že strom má tvar t = (A×B) z R, tj. kořen je z, pravý podstrom R, levý podstrom má kořen x, a naopak se skládá z levého podstromu A a pravý podstrom B. Poměr výšek: h(A)=h(B)=h(R) . Nový vrchol je zahrnut do podstromu A, poté se jeho výška zvýší o jedna. Poměr celkové výšky může být h(v)=h(w)+2.
Převeďme strom t do nového tvaru: (A×B) z R => A×(B z R) .
Výšky podstromů A, B a R se nezměnily, ale výška stromu t klesla o jednu a strom se vyrovnal.
Symetrická situace nastane, pokud je nový vrchol zahrnut do podstromu R stromu t = A×(B z R) . V tomto případě bude vyrovnávací transformace inverzní: A×(B z R) => (A×B) z R.
Pokud je nový vrchol zahrnut do podstromu B, pak tyto transformace nic nedávají (podstrom B se nevyvolá).
Zrušení rovnováhy stromu zahrnutím nového vrcholu do B vyžaduje bližší pohled na strukturu tohoto podstromu. Vyberme v něm kořen, levý a pravý podstrom, B = C y D . Původní strom tedy bude reprezentován jako t=(Ax(CyD))zR. Vrchol zahrnutý v podstromu B a zvyšující výšku stromu t patří do jednoho z podstromů C nebo D. Nezáleží na tom, který. Oba se dají vychovat. Konverze
(A x (C y D)) z R => (A x C) y (D z R)
rozdělí podstromy C nebo D, přiřadí je různým kořenům a sníží výšku stromu t o jednu. Všimněte si, že všechny popsané transformace mění kořen stromu t, což je třeba vzít v úvahu při psaní seznamu formálních parametrů procedur.
Připomeňme, že ve vyváženém stromě musí být pro každý vrchol splněna podmínka, že se výšky levého a pravého podstromu neliší o více než jednu. Proto, když mluvíme výše o stromu t, nemáme na mysli pouze strom jako celek, ale jakýkoli podstrom, ve kterém byla narušena rovnováha.
Více informací o vyvažování stromů naleznete zde.
V dalším kroku se podíváme na optimalizační algoritmy.
