3.5 Binární vyhledávací strom

Definice 3.8 (binární vyhledávací strom)

Binární vyhledávací strom (BVS) je binární strom, v jehož každém vrcholu $v$ je uložen unikátní klíč $k(v)$ a pro jehož každý vrchol v platí:

Pokud $a \in L(v)$, pak $k(a) < k(v)$.
Pokud $b \in R(v)$, pak $k(b) > k(v)$.

`BVSShow`($v$)	$O(n)$	Vypiš vzestupně uspořádanou posloupnost klíčů všech vrcholů $T(v)$
`BVSMin`($v$), `BVSMax`($v$)	$O(\log n)$	Vrať vrchol obsahující minimální (maximální) klíč v $T(v)$
`BVSPred`($v, w$), `BVSSucc`($v, w$)	$O(\log n)$	Vrať předchůdce (následníka) vrcholu $w$ v $T(v)$
`BVSFind`($v, x$)	$O(\log n)$	Vrať vrchol v $T(v)$ s klíčem $x$, pokud takový existuje
`BVSInsert`($v, x$)	$O(\log n)$	Vlož do $T(v)$ nový vrchol s klíčem $x$, pokud v něm ještě neexistuje
`BVSDelete`($v, x$)	$O(\log n)$	Odstraň z $T(v)$ vrchol s klíčem $x$, pokud takový existuje

Tabulka 3.2: průměrné složitosti operací na BVS

Definice 3.9 (`BVSShow`)

Vstup: Ukazatel na kořen v nějakého BVS $T(v)$.

Výstup: Vzestupně uspořádaná posloupnost klíčů všech vrcholů v $T(v)$.

\begin{algorithm}
\begin{algorithmic}
\STATE BVSShow(ukazatel na vrchol $v$)
\IF {$v = \emptyset$}
    \RETURN // $T(v)$ je prázdný
\ENDIF
\STATE Zavoláme BVSShow($l(v)$)
\STATE Vypíšeme $k(v)$
\STATE Zavoláme BVSShow($r(v)$)\end{algorithmic}
\end{algorithm}

Algoritmus 3.1: Algoritmus BVSShow(v)

Z definice BVS a z definice InOrder průchodu binárním stromem plyne:

Pozorování 3.2

BVSShow($v$) vypíše vzestupně uspořádané klíče vrcholů BVS $T(v)$ v čase $O(|T(v)|)$.

Definice 3.10 (BVSMin)

Vstup: Ukazatel na kořen v nějakého BVS $T(v)$.

Výstup: Ukazatel na vrchol obsahující nejmenší klíč v $T(v)$.

\begin{algorithm}
\begin{algorithmic}
\STATE BVSMin(ukazatel na vrchol $v$)
\IF { $l(v) = \emptyset$ }
    \RETURN ukazatel na vrchol $v$
\ELSE
    \RETURN BVSMin($l(v)$)
\ENDIF\end{algorithmic}
\end{algorithm}

Algoritmus 3.2: Algoritmus BVSMin(v)

Pozorování 3.3

Nejmenší klíč je první v posloupnosti vzestupně uspořádaných klíčů vygenerovaných v předchozím algoritmu InOrder průchodem a tudíž vrchol s nejmenším klíčem je v daném BVS ten nejvíce vlevo.

Je to tudíž buď list nebo vrchol s jedním synem.

Definice 3.11 (BVSPred)

Vstup: Ukazatel na kořen $v$ nějakého BVS $T(v)$ a na nějaký jeho vrchol $w$.

Výstup: Ukazatel na předchůdce $w$ v $T(v)$.

\begin{algorithm}
\begin{algorithmic}
\STATE BVSPred(ukazatel na vrchol vrcholy $v$, $w$)
\IF { $w \neq $ BVSFind($v$, $k(w)$) }
  \RETURN $\emptyset$
\ENDIF
\IF { $l(w) \neq \emptyset$ }
  \RETURN BVSMax($l(w)$)
\ENDIF
\STATE $z$ := $p(w)$
\WHILE { $z \neq \emptyset$ a $w = l(z)$ }
  \STATE $w$ := $z$
  \STATE $z$ := $p(z)$
\ENDWHILE
\RETURN ukazatel na vrchol $z$\end{algorithmic}
\end{algorithm}

Algoritmus 3.3: Algoritmus BVSPred($v$, $w$)

Pozorování 3.4

Klíč předchůdce prvku $w$ v $T(v)$ je ve vzestupném výpisu klíčů algoritmem BVSShow levým sousedem $k(w)$.
Pokud má $w$ v $T(v)$ levý podstrom $L(w)$, pak je předchůdce $w$ jeho maximem.
V opačném případě je předchůdcem $w$ první předek, do kterého vstoupíme zprava při průchodu nahoru.
Evidentně, prvek s nejmenším klíčem předchůdce nemá, neboť nesplňuje ani jednu podmínku.

Otázka 3.1

Pro $w$ = BVSMin($v$) najděte, co vrací BVSPred($w$)

Zobrazit řešení

Algoritmus vrací $\emptyset$.

Definice 3.12 (BVSFind)

Vstup: Ukazatel na kořen $v$ nějakého BVS $T(v)$ a klíč $x$.

Výstup: Ukazatel na vrchol $s$ klíčem $x$, pokud takový v $T(v)$ existuje, jinak $\emptyset$.

\begin{algorithm}
\begin{algorithmic}
\STATE BVSFind(ukazatel na vrchol $v$, klíč $x$)
\IF { $v = \emptyset$ }
  \RETURN $\emptyset$
\ENDIF
\IF { $x = k(v)$ }
  \RETURN ukazatel na $v$
\ENDIF
\IF { $x < k(v)$ }
  \RETURN BVSFind($l(v), x$)
\ENDIF
\IF { $x > k(v)$ }
  \RETURN BVSFind($r(v), x$)
\ENDIF\end{algorithmic}
\end{algorithm}

Algoritmus 3.4: Algoritmus BVSFind($v$, $x$)

Pozorování 3.5

Korektnost plyne okamžitě z definice BVS:

V libovolném vrcholu $u$ platí, že všechny klíče v $L(u)$ jsou menší než $k(u)$ a všechny klíče v $R(u)$ jsou větší než $k(u)$.

Definice 3.13 (BVSInsert)

Vstup: Ukazatel na kořen $v$ nějakého BVS $T(v)$ a klíč $x$.

Výstup: Ukazatel na kořen $v$ BVS s prvkem s klíčem $x$.

\begin{algorithm}
\begin{algorithmic}
\FUNCTION {BVSInsert}{ukazatel na vrchol $v$, klíč $x$}
    \IF { $v = \emptyset$ }
        \STATE vytvoř nový vrchol $v$ s klíčem $x$
        \RETURN ukazatel na $v$ a skončíme
    \ENDIF
    \IF { $x = k(v)$ }
        \STATE nic //vrchol s klíčem $x$ v $T(v)$ již existuje
    \ENDIF
    \IF { $x < k(v)$ }
        \STATE $l(v)$ := BVSInsert($l(v), x$)
    \ENDIF
    \IF { $x > k(v)$ }
        \STATE $r(v)$ := BVSInsert($r(v), x$)
    \ENDIF
    \RETURN ukazatel na $v$
\ENDFUNCTION\end{algorithmic}
\end{algorithm}

Algoritmus 3.5: Algoritmus BVSInsert(v, x)

Pozorování 3.6

Operaci BVSInsert lze chápat jako hledání daného klíče a pokud klíč nenajdeme, vložíme ho na jednoznačně určenou pozici jako nový list (předpokládáme unikátní klíče).

Důsledek 3.2

Z dosud uvedeného vyplývá, že danou množinu klíčů bude existovat více korektních BVS lišících se tvarem, protože výsledný tvar BVS závisí nejen na hodnotách klíčů, ale i na pořadí, v jakém jsou do BVS vkládány.

Poznámka 3.2

Operace BVSShow vrátí pro všechny možné BVS nad stejnou množinou klíčů stejnou uspořádanou posloupnost klíčů.

Definice 3.14 (Odstranění vrcholu s daným klíčem z BVS)

Nejdříve nalezneme vrchol, který obsahuje klíč, který chceme smazat.
Při mazání vrcholu může nastat několik různých případů.
1. Pokud takový vrchol neexistuje, necháme strom beze změny.
2. Jinak, pokud je nalezený vrchol listem, odtrhneme ho od stromu.
3. Má-li nalezený vrchol jednoho syna, nahradíme ho tímto synem.
4. - Pokud má nalezený vrchol, nazveme ho $u$, dva syny, pak $u$ nemůžeme odstranit přímo, protože by nebylo kam připojit jeho syny.
  - Využijeme ale faktu, že vrchol $u$ má v BVS následníka $w$ = BVSMin($r(u)$).
  - A ten má nejvýše jednoho syna, viz Slajd 8.
  - Klíč vrcholu u nahradíme klíčem vrcholu w.
  - Aplikací postupu z případu 2) nebo 3) pak odstraníme z BVS vrchol w.

Definice 3.15 (BVSDelete)

Vstup: Ukazatel na kořen $v$ nějakého BVS a klíč $x$.

Výstup: Ukazatel na kořen BVS, ze kterého byl odstraněn vrchol s klíčem $x$, pokud takový vrchol existoval.

\begin{algorithm}
\begin{algorithmic}
\FUNCTION {BVSDelete}{ukazatel na vrchol $v$, klíč $x$}
    \IF { $v = \emptyset$ }
        \RETURN $\emptyset$
    \ENDIF
    \IF { $x < k(v)$ }
        \STATE $l(v)$ := BVSDelete($l(v), x$)
    \ENDIF
    \IF { $x > k(v)$ }
        \STATE $r(v)$ := BVSDelete($r(v), x$)
    \ENDIF
    \IF { $x = k(v)$ }
        \IF { $l(v)= r(v)= \emptyset$}
            \RETURN $\emptyset$
        \ENDIF
        \IF { $l(v)= \emptyset$ }
            \RETURN $r(v)$
        \ENDIF
        \IF { $r(v)= \emptyset$ }
            \RETURN $l(v)$
        \ENDIF
        \STATE $w$ := BVSMin($r(v)$) // v má oba syny, w následník
        \STATE $k(v)$ := $k(w)$
        \STATE $r(v)$ := BVSDelete($r(v), k(w)$)
    \ENDIF
    \RETURN ukazatel na $v$
\ENDFUNCTION\end{algorithmic}
\end{algorithm}

Algoritmus 3.6: Algoritmus BVSFDelete(v, x)

Pozorování 3.7 (Vyváženost BVS)

Časová složitost operací BVSFind, BVSMin, BVSInsert a BVSDelete nad BVS T($v$) je $O(h(T (v)))$.

Definice 3.16 (Dokonale vyvážený BVS)

BVS nazveme dokonale vyvážený, pokud pro každý jeho vrchol $v$ platí $|L(v)| − |R(v)| ≤ 1$.

Pozorování 3.8

Dokonale vyvážený BVS o velikosti $n$ má $1 + ⌊\log n⌋$ hladin a operace BVSFind, BVSMin, BVSInsert a BVSDelete na něm tedy mají časovou složitost $O(log n)$.

Věta 3.4

Pokud má BVS zůstávat po provedení operací BVSInsert a BVSDelete dokonale vyvážený, potom ať použijeme jakoukoli implementaci zmíněných operací, bude časová složitost aspoň jedné z nich $\Omega(n)$ pro nekonečně mnoho různých $n$.

Zobrazit důkaz

Uvažujme dokonale vyvážený BVS s klíči 1, 2, . . . , $n$, kde $n = 2k − 1$.

Ten pak vypadá nutně takto: (BVS se všema hladinama plně zaplněnýma)

TODO obrázek Přednáška 6 slajd 20

Kořen stromu je vždy prostřední z klíčů.
Všechna lichá čísla jsou v listech stromu.
Levý a pravý podstrom mají právě $2k−1 − 1$ vrcholů a jsou tedy opět určeny jednoznačně.
Nyní provedeme následující posloupnost dvojic operací:
\begin{equation*} \text{Insert}(n + 1), \text{Delete}(1), \text{Insert}(n + 2), \text{Delete}(2), ... \end{equation*}
Po provedení $i$-té dvojice operací bude strom obsahovat hodnoty $i + 1, . . . , i + n$.
Podle toho, zda je $i$ sudé nebo liché, se budou v listech nacházet buď všechna sudá, nebo všechna lichá čísla.
Pokaždé se proto všem vrcholům změní, zda jsou listy, což ale nutně znamená upravit $\Omega(n)$ ukazatelů.
Tedy aspoň jedna z operací BVSInsert a BVSDelete trvá $\Omega(n)$.

$\square$