TIN066 Binární vyhledávací stromy

Z ωικι.matfyz.cz
Verze z 20. 1. 2014, 18:14, kterou vytvořil 78.128.169.81 (diskuse) (Vyvažování)

(rozdíl) ← Starší verze | zobrazit aktuální verzi (rozdíl) | Novější verze → (rozdíl)
Přejít na: navigace, hledání
Tato část je neúplná a potřebuje rozšířit. 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[editovat | editovat zdroj]

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í[editovat | editovat zdroj]

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í[editovat | editovat zdroj]

BB-$ \alpha $ stromy[editovat | editovat zdroj]