\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
