TIN066 Binární vyhledávací stromy

Wiki-skripta pro Datové struktury I
Obsah
Základní metody hashování Univerzální a perfektní hashování (a,b) stromy Binární vyhledávací stromy AVL stromy Červeno-černé stromy Splay stromy Vyhledávání v setříděné posloupnosti Vyhledávání k-tého nejmenšího Základní haldy Binomické a Fibonacciho haldy Základní metody třídění Přihrádkové třídě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

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.