Binární vyhledávací stromy

Definice: O stromu řekneme, že je binární, pokud je zakořeněný a každý vrchol má nejvýše dva syny, u nichž rozlišujeme, který je levý a který pravý.

Značení:

1. $T(v)$ - podstrom obsahující vrchol $v$ jako kořen a všechny jeho potomky
2. $l(v),r(v)$ - jsou levý a pravý syn vrcholu $v$
3. $L(v),R(v)$ - jsou $T(l(v))$ a $T(r(v))$
4. $h(v)$ - hloubka stromu $T(v)$, tedy nejdelší z cest z $v$ do listů Nemá-li vrchol syna tak funkce $l(v)$, či $r(v)$, podle toho jaký chybí je $\varnothing$ a hloubka $h(\varnothing )=-1.$

Definice: Binární vyhledávací strom (BVS) je binární strom, jehož každému vrcholu $v$ přiřadíme unikátní klíč $k(v)$ z univerza. Přitom musí platit

1. $a\in L(v)⟹k(a)<k(v)$
2. $b\in R(v)⟹k(b)>k(v)$

Na takových stromech můžeme definovat několik operací

$$\begin{array}{rl}& \text{BvsShow - vyˊpis BVS}\\ & \text{Vstup: Korˇen BVS }v\\ & \text{1. Pokud }v=\varnothing \text{ pak skoncˇıˊme}\\ & \text{2. BvsShow}(L(v))\\ & \text{3. Vypıˊsˇeme }k(v)\\ & \text{4. BvsShow}(R(v))\end{array}$$ $$\begin{array}{rl}& \text{BvsFind - hledaˊnıˊ klıˊcˇe v BVS}\\ & \text{Vstup: Korˇen BVS }v\text{, hledanyˊ klıˊcˇ }x\\ & \text{Vyˊstup: Vrchol }v\text{ s klıˊcˇem }x\text{, nebo }\varnothing \\ & \text{1. Pokud }v=\varnothing \text{ vraˊtıˊme }\varnothing \text{.}\\ & \text{2. Pokud }x=k(v)\text{, vraˊtıˊme }v\text{.}\\ & \text{3. Pokud }x<k(v)\text{, vraˊtıˊme BvsFind}(L(v))\text{.}\\ & \text{4. Pokud }x>k(v)\text{, vraˊtıˊme BvsFind}(R(v))\text{.}\end{array}$$ $$\begin{array}{rl}& \text{BvsMin - hledaˊnıˊ minima}\\ & \text{Vstup: Korˇen BVS }v\\ & \text{Vyˊstup: Vrchol }v\text{ s nejmensˇıˊm klıˊcˇem }x\\ & \text{1. Pokud }l(v)=\varnothing \text{ vraˊtıˊme }v\text{.}\\ & \text{2. Jinak}\text{ vraˊtıˊme BvsMin}(l(v))\text{.}\end{array}$$ $$\begin{array}{rl}& \text{BvsInsert - vklaˊdaˊnıˊ do BVS}\\ & \text{Vstup: Korˇen BVS }v\text{, vklaˊdanyˊ klıˊcˇ }x\\ & \text{Vyˊstup: Novyˊ korˇen }v\\ & \text{1. Pokud }v=\varnothing \text{ vytvorˇıˊme novyˊ vrchol }v\text{ s klıˊcˇem }x\text{ a skoncˇıˊme.}\\ & \text{2. Pokud }x=k(v)\text{ klıˊcˇ jizˇ ve stromu je a nenıˊ nic potrˇeba}\text{.}\\ & \text{3. Pokud }x<k(v)\text{, polozˇıˊme }l(v)\leftarrow \text{BvsInsert}(l(v),x)\text{.}\\ & \text{4. Pokud }x>k(v)\text{, polozˇıˊme }r(v)\leftarrow \text{BvsInsert}(r(v),x)\text{.}\end{array}$$

Mazání má problém v tom že mažeme-li ne-list, tak mohou nastat dvě situace, vrchol má jednoho syna a tedy jen náš mazaný $v$ nahradíme jeho synem. Pokud mazaný vrchol má oba syny, tak určíme nejlevější vrchol pravého podstromu jako další v řadě, ten vystřihneme a nahradí náš vrchol $v$ a sám měl maximálně jednoho syna a tedy jen ho přepojíme.

$$\begin{array}{rl}& \text{BvsDelete}\\ & \text{Vstup: Korˇen BVS }v\text{, mazanyˊ klıˊcˇ }x\\ & \text{Vyˊstup: Novyˊ korˇen }v\\ & \text{1. Pokud }v=\varnothing \text{ tak x ve stromu nebyl a vraˊtıˊme }\varnothing \text{.}\\ & \text{2. Pokud }x<k(v)\text{, polozˇıˊme }l(v)\leftarrow \text{BvsDelete}(l(v),x)\text{.}\\ & \text{3. Pokud }x>k(v)\text{, polozˇıˊme }r(v)\leftarrow \text{BvsDelete}(r(v),x)\text{.}\\ & \text{4. Pokud }x=k(v):\\ & \text{5. }\text{Pokud }l(v)=r(v)=\varnothing \text{ vraˊtıˊme }\varnothing \text{.}\\ & \text{6. }\text{Pokud }l(v)=\varnothing \text{ vraˊtıˊme }r(v)\text{.}\\ & \text{7. }\text{Pokud }r(v)=\varnothing \text{ vraˊtıˊme }l(v)\text{.}\\ & \text{8. }s\leftarrow \text{BvsMin}(r(v))\\ & \text{9. }k(v)\leftarrow k(s)\\ & \text{10. }r(v)\leftarrow \text{BvsDelete}(r(v),s)\\ & \text{11. }\text{Vraˊtıˊme }v\text{.}\end{array}$$

---

AVL stromy

Definice: Binární vyhledávací strom je hloubkově vyvážený pokud pro každý jeho vrchol $v$ platí

$$|h(l(v))-h(r(v))|\le 1.$$

Stromy splňující tuto podmínku jsou zvané AVL stromy.

Tvrzení: AVL strom na $n$ vrcholech má hloubku $\Theta (\log n)$.