Vyhledávací stromy

• datový typ pro reprezentaci množiny prvků, nad kterými je definované úplné uspořádání
• podporované operace

Search(T,x) - vyhledá x v T
Minimum(T) - vyhledá minimální prvek v T
Maximum(T) - vyhledá maximální prvek v T
Predecessor(T,x) - vyhledává předchůdce x v T
Successor(T,x) - vyhledá následníka x v T
Insert(T,x) - vloží x do T
Delete(T,x) - odstraní x z T

Binární vyhledávací stromy BST

• kořenový strom, v němž každý uzel má nejvýše 2 následníky
• každý uzel stromu představuje jeden objekt, obsahující
  • klíč key
  • ukazatele left, right a parent na levého syna, na pravého syna a na otce; ukazatel má hodnotu None právě když uzel nemá příslušného syna, resp. otce
  • případně další data
• pro všechny uzly BTS platí: jestliže
  • $y$ je uzel v levém podstromu ulzu $x$, tak $y.key \le x.key$
  • $y$ je uzel pravého podstromu uzlu $x$, tak $y.key \ge x.key$

Procházení stromu

• cílem je projít strom tak, aby každý uzel byl navštíven právě jednou
• využití provedení operace nad každým uzlem, výpis klíčů, kontrola vlastností stromů, …

• strom procházíme rekurzivně
• začíname v kořeni stromu
• (rekurzivně) navštívíme všechny uzly levého podstromu kořene
• (rekurzivně) navštívíme všechny uzly pravého podstromu kořene

Výpis klíču

• preorder : před vypsáním podstromů
• inorder : nejdřív levý podstrom, kořen, pravý podstrom - mezi podstromy
• postorder : po vypsání podstromů

Vyhledávání ve stromu

function Search(x,k)
    if x is None or k == x.key then
        return x
    if k < x.key then
        return Search(x.left,k)
    else
        return Search(x.right,k)

Minimální a maximální klíč

• jestliže hledáme minimální klíč, tak v stromu postupujeme vždy doleva
• jestliže hledáme maximální klíč, tak v stromu postupujeme vždy doprava

Předchůdce a následovník

• předpokládejme, že všechny klíče uložené ve stromě jsou vzájemně různé
• následníkem uzlu $x$ je uzel, který obsahuje nejmenší klíč větší než x.key (successor)
• předchůdcem uzlu $x$ je uzel, který obsahuje největší klíč menší než x.key (predecessor)

Následník uzlu x

• jestliže pravý podstrom uzlu $x$ je neprázdný, tak následníkem $x$ je uzel jeho prvého podstromu s nejmenším klíčem
• jestli pravý podstrom uzlu $x$ je prázdný, tak
  • následníkem $x$ je uzel $y$ takový, že $x.key$ je největším klíčem v levém podstromu uzlu $y$
  • uzel $y$ je prvním uzlem na cestě z $x$ do kořene stromu takový, že $y.key > x.key$ (x patří do levého podstromu uzlu y)

Přidání nového uzlu

• procházíme stejně jako kdybychom klíč nového uzlu vyhledávali
• hledáme uzel, jehož příslušný podstro je prázdný (levý podstrom, je když klíč nového uzlu je menší než klíč uzlu, pravý podstrom když je větší) a nový uzel se stane jeho příslušným synem

Odstranění uzlu

• mohou nastat 3 případy:

1. uzel nemá žádného syna - smažeme
2. uzel z má jediného syna - syna přesuneme na pozici uzlu $z$ tak, že otec uzlu $z$ se stane otcem jeho syna
3. uzel z má dva syny
   • potřebujeme najít uzel $y$ který nahradí uzel $z$
   • vhodným kandidátem je následník uzlu $z$ (symetricky předchůdce z)
   • protože pravý podstrom uzlu z je neprázdný, tak následník $y$ uzlu $z$ je uzel s nejmenším klíčem v pravém podstromě uzlu $z$
   • $y$ nemá levého syna, proto ho můžeme přesunout na pozici $z$
   • $y$ je nahrazen svým pravým synem

function Delete(T,z)
    if z.left is None then
        Transplant(T,z,z.right)
    else
        if z.right is None then
            Transplant(T,z,z.left)
        else
            y = Minimum(z.right)
            if y.parent != z then
                Transplant(T,y,y.right)
                y.right = z.right
                z.right.parent = y
            Transplant(T,z,y)
            y.left = z.left
            z.left.parent = y

Pomocná funkce transplant

• nahradí podstrom s kořenem $u$ podstromem s kořenem $v$
• otcem ulzu $v$ se stane otec uzlu $u$
• otec uzlu $u$ bude mít uzel $v$ jako svého syna

function Transplant(T,u,v)
    if u.parent is None then
        T.root = v
    else
        if u == u.parent.left then
            u.parent.left = v
        else
            u.parent.right = v
    if v is not None then
        v.parent = u.parent

Složitost

• všechny operace nad BST mají složitost úměrnou hloubce stromu, tj. v nejhorším případě $O(n)$, kde $n$ je počet uzlů stromu
• při hledání předchůdce a následníka nemusíme vůbec porovnávat klíče

Vyvážené binární vyhledácí stromy

• hloubka je logaritmická vůči počtů uzlů
• složitost operací nad vyváženým BST je logaritmická

• příklady:
  • AVL stromy
  • 2 - 3 stromy
  • 2 - 3 - 4 stromy
  • B stromy
  • červeno černé stromy

Modifikace datových struktur

• reálné situace, ve kterých potřebujeme datovou strukturu odlišnou od “učebnicových”

Intervalové stromy

• číselný interval $\langle t_1,t_2 \rangle$
• objekt $i$ s atributy $i.low$ a $i.high$
• intervaly $i$ a $i’$ se překrývají když $i.low \le i’.high$ a současně $i’.low \le i.high$

• pomocí BTS
• klíč bude $i.low$