{{TIN066 Skripta}} {{TODO|rozepsat}}
Binární strom s hodnotami v uzlech nazveme Vyhledávací, pokud pro každý uzel s hodnotou s platí: uzly levého podstromu mají hodnoty menší než s a uzly pravého podstromu mají hodnoty větší než s. Na vnitřních uzlech lze vidět "přirozené" lineární uspořádání.
Náš strom bude mít "listy navíc", kdy každý list představuje interval mezi otcem a nejbližším sousedem. Nejlevější list představuje interval (-nekonečno, klič otce), obdobně nejpravější list. Při implementaci se tyto listy vynechávají, avšak v našem výzkumu je budeme uvažovat.
Algoritmy
Vyhledej x : t = kořen; dokud (t není list AND t.key != x) : pokud x<t.key : t = t.levý; jinak t = t.pravý; vrať t;
MEMBER x : v = Vyhledej(x); pokud je v vnitřní uzel, vrátím TRUE, jinak FALSE.
INSERT x : v = Vyhledej(x); pokud je v vnitřní uzel, končím; jinak změním v na vnitřní uzel, nastavím hodnotu x, připojím dva nové listy.
DELETE x
v = Vyhledej(x); pokud je v list, končím;
pokud v.levy je list, přepojím v.pravý na předka v.
jinak najdu maximum v levém podstromě, smažu ho a jeho hodnotu dosadím do v.
ord k : Algoritmus najde k-tý nejmenší prvek stromu (k = 0..n-1). Idea je snadná - když má levý podstrom 4 uzly a hledáme 7. nejmenší, převedeme to na hledání 2. nejmenšího v pravém podstromu (čtvrtý nejmenší je kořen). Je třeba vědět počet uzlů v podstromu v : p(v).
pokud k >= p(kořen) konec;
t = kořen; opakuj:
pokud k < p(t.levý) : t = t.levý;
pokud k > p(t.levý) : t = t.pravý; k = k - p(t.levý) - 1;
jinak konec, vrať t;
Vyvažování
Při úpravě BVS se může strom stát nevyvážený, algoritmy nad ním budou trvat až O(n). Chtěli bychom, aby trvaly O(log n). Definujme si následující operace:
Rotace v, u : v otec u, po rotaci u otec v. Průběh lze vidět z obrázku ve skriptech.
Dvojita-rotace u, v, w : u otec v, v otec w. Průběh lze vidět z obrázku ve skriptech.
Tyto operace jsou použity v dalších vyvažovacích technikách, např. AVL strom nebo Červeno-Černý strom.
Vyvažování
BB-α \alpha
{{Stub}}