{{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}}