\input /home/pasky/school/fastex/lib.tex

\chapter{Stromy}{

	\scpart{Dynamické množiny}{
		\shortdef{Dynamická množina}{Množinu prvků, která se mění v čase.}

		\scpart{Prvek dynamické množiny}{
		\list{
		\olistItem{přístup přes ukazatel}
		\olistItem{obsahuje: klíč, ukazatel na další prvky, příp. další data}
		}
		}

		\scpart{Operace na dynamické množině}{

			Nechť $S$ je dynamická množina prvků, $k$ je hodnota
			klíče a $x$ je ukazatel na prvek.

			Slovníkové operace:
			\startRuledTable
			$\mathop{\rm Find}(S, k)$ & \vbox{Vrací ukazatel na prvek v $S$ s klíčem $k$,
						pokud existuje, jinak vrací \nil}\cr
			$\mathop{\rm Insert}(S, x)$ & Do $S$ vloží prvek, na který ukazuje $x$\cr
			$\mathop{\rm Delete}(S, x)$ & Z $S$ odstraní prvek, na který ukazuje $x$\cr
			\endRuledTable

			\startRuledTable
			$\mathop{\rm Min}(S)$ & Vrátí ukazatel na prvek $S$ s minimálním klíčem\cr
			$\mathop{\rm Max}(S)$ & Vrátí ukazatel na prvek $S$ s maximálním klíčem\cr
			$\mathop{\rm Succ}(S, x)$ & \vbox{Vrátí ukazatel na v pořadí další prvek za $x$ v $S$ podle
						uspořádání klíčů (pokud $x$ obsahuje max. klíč, vrátí \nil)}\cr
			$\mathop{\rm Prec}(S, x)$ & \vbox{Vrátí ukazatel na v pořadí předchozí prvek za $x$ v $S$ podle
						uspořádání klíčů}\cr
			\endRuledTable
		}
	}

	\scpart{Binární vyhledávací stromy}{
		Dynamická datová struktura podporující všechny uvedené operace.

		\shortdef{Binární strom}{Každý prvek má tři ukazatele: rodič, levý, pravý.}

		V BVS pak pro každý prvek $x$ platí:
		\list{
		\listItem{Každý prvek v levém podstromu má klíč $\le$ klíč $x$}
		\listItem{Každý prvek v pravém podstromu má klíč $\ge$ klíč $x$}
		}

		\dots implementace operací\dots
	}

	\scpart{Červeno--černé stromy}{
		...definice...

		\lemma{ 1}{
			Nechť $x$ je libovolný uzel. Pak podstrom s kořenem $x$ obsahuje
			alespoň $2^{bh(x)}-1$ interních uzlů.

			\proof{
				Indukcí podle $h(x)$:
				\list{
				\listItem{$h(x) = 0$:

					Podstrom s kořenem $x$ na $2^0-1 = 1-1 = 0$.
				}
				\listItem{Nechť tvrzení platí pro $1,\ldots,h(x)-1$ a $h(x) > 0$.

					$x$ je interní ($h(x) > 0$), tedy $x$ má dva syny $y$ a $z$.
					Pak platí:
					$$\eqalign{h(y) &< h(x) \cr h(z) &< h(x)}$$

					Také platí:
					$$ bh(z) = bh(y) = \cases{bh(x) & pokud $y$ je červený\cr
								  bh(x) - 1 & pokud $y$ je černý} $$

					Z indukčního předpokladu víme, že podstrom s kořenem
					$y$ má alespoň $2^{bh(y)} - 1$ interních uzlů, kterých
					je alespoň $2^{bh(y) - 1} - 1$. Totéž platí pro podstrom
					s~kořenem~$z$.

					Tedy $x$ má alespoň $2^{bh(x)-1}-1 + 2^{bh(x)-1}-1 + 1 = 2^{bh(x)} - 1$.
				}
				}

				\qed
			}
		}

		\lemma{ 2}{
			Nechť $h$ je výška červeno--černého stromu s $n$ interními
			uzly. Pak $h \le 2\log_2(n+1)$.

			\proof{
				Díky vlastnosti 3 na větvi délky 4 musí být alespoň $h/2$
				černých vrcholů (nepočítaje kořen):
				$$ bh({\rm kořen}) \ge h/2 $$
				$$ n \ge 2^{bh({\rm kořen})} - 1 \ge 2^{h/2} - 1 $$
				$$ n + 1 \ge 2^{h/2} $$
				$$ \log_2(n+1) \ge h/2 $$
				\qed
			}
		}
	}

}

\bend