{{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-<math>\alpha</math> stromy ==
{{Stub}}
