Informatyka MIMUW

Drzewa binarne

Poznaliśmy wiele przykładów ciągów liczbowych zadanych równaniami rekurencyjnymi. Teraz poznamy zupełnie inną strukturę zadaną definicją rekurencyjną.

Drzewo binarne to dowolny obiekt powstały zgodnie z regułami:

• \( \perp \) jest drzewem binarnym,

• jeśli \( T_0 \) i \( T_1 \) są drzewami binarnymi to \( T_0\wedge T_1 \) też jest drzewem binarnym.

Zbiór wszystkich drzew binarnych oznaczamy przez \( \mathbb{T} \). Wypisując konkretne drzewo binarne używamy nawiasów aby ujednoznacznic kolejność aplikacji reguł z definicji rekurencyjnej.

Wielkość drzewa binarnego jest wyznaczona funkcją

zdefiniowana rekurencyjnie (z uwagi na budowę drzewa) jako:

• \( \vert\perp\vert=1 \),

• \( \vert T_0\wedge T_1\vert=\vert T_0\vert+\vert T_1\vert+1 \).

Szerokość drzewa binarnego jest wyznaczona funkcją

zdefiniowana rekurencyjnie (z uwagi na budowę drzewa) jako:

• \( \mbox{\sf w}(\perp)=1 \),

• \( \mbox{\sf w}(T_0\wedge T_1)=\mbox{\sf w}(T_0)+\mbox{\sf w}(T_1) \).

Wysokość drzewa binarnego jest wyznaczona funkcją

\( \mathbb{T} \ni T \mapsto \mbox{\sf h}(T) \in \mathbb{N} \)

zdefiniowana rekurencyjnie (z uwagi na budowę drzewa) jako:

• \( \mbox{\sf h}(\perp)=0 \),

• \( \mbox{\sf h}(T_0\wedge T_1)=\max(\mbox{\sf h}(T_0),\mbox{\sf h}(T_1) )+1 \).

Przykład

Obserwacja 2.7

Dla \( T=T_0\wedge T_1 \) mamy

• \( \mbox{\sf h}(T_i) < \mbox{\sf h}(T) \),

• \( \mbox{\sf w}(T_i) < \mbox{\sf w}(T) \),

• \( \vert T_i\vert < \vert T\vert \).

Wniosek 2.8
Drzewo \( \perp \) jest jedynym drzewem o wysokości \( 0 \).

Twierdzenie 2.9 [Zasada Indukcji dla drzew binarnych]

Gdy \( S\subseteq\mathbb{T} \) jest zbiorem drzew binarnych spełniającym warunki:

• \( \perp\in S \),

• jeśli \( T_0,T_1\in S \) to \( T_0\wedge T_1\in S \),

to \( S=\mathbb{T} \).

Dowód

Dla dowodu niewprost załóżmy, że w \( S \) nie ma wszystkich drzew. Zatem zbiór \( S'=\mathbb{T}-S \) jest niepusty. Tym samym niepusty jest też zbiór \( Z={\{ {\mbox{\sf h}(T) : T \in S'} \}\ } \) Na mocy założenia o \( S \) wiemy, że \( \perp\notin S' \), co wraz z Wnioskiem 2.8 implikuje, że \( 0\notin Z \).

Ponieważ \( Z \) jest niepusty, to na podstawie Zasady Minimum ma element najmniejszy, powiedzmy \( z \). Wiemy już, że \( z>0 \). Niech \( T\in S' \) poświadcza fakt, że \( z\in Z \), tzn. \( \mbox{\sf h}(T)=z>0 \). Ponownie z Wniosku 2.8 dostajemy \( T'\neq\perp \), czyli \( T'=T_0\wedge T_1 \) dla pewnych \( T_1,T_2 \). Z Obserwacji 2.7 mamy \( \mbox{\sf h}(T_0) < \mbox{\sf h}(T)=z \) oraz \( \mbox{\sf h}(T_1) < \mbox{\sf h}(T)=z \). Zatem minimalność \( z \) w \( S_0' \) daje \( \mbox{\sf h}(T_0),\mbox{\sf h}(T_1)\notin Z \), czyli \( T_0,T_1\notin S' \) i w konsekwencji \( T_0,T_1\in S \).

Ale wtedy, z założenia o zbiorze \( S \), dostajemy \( T=T_0\wedge T_1=T\in S \). Sprzeczność.

Zasada Indukcji dla drzew binarnych to przykład na to, że w strukturach zdefiniowanych rekurencyjnie można dowodzić przy pomocy zasady analogicznej do Zasady Indukcji. Poniżej przedstawiamy przykład używający tego narzędzia.

Obserwacja 2.10

Dla dowolnego drzewa binarnego \( T\in\mathbb{T} \) mamy:

• \( \mbox{\sf h}(T) \le \mbox{\sf w}(T) \le \vert T\vert \),

• \( \vert T\vert=2\cdot\mbox{\sf w}(T)-1 \).

Dowód

Niech \( S\subseteq\mathbb{T} \) będzie zbiorem drzew binarnych spełniających powyższe własności.

• \( \mbox{\sf h}(\perp)=0 \le 1 =\mbox{\sf w}(\perp)= \vert\perp\vert \), oraz \( \vert\perp\vert=1=2\mbox{\sf w}(\perp)-1 \), czyli \( \perp\in S \).

• W kroku indukcyjnym zakładamy, że \( T=T_0\wedge T_1 \) oraz że drzewa \( T_0,T_1 \) mają już opisane w Obserwacji własności. Wtedy

\( \begin{align*}\vert T_0\wedge T_1\vert & =\vert T_0\vert+\vert T_1\vert+1 =(2\mbox{\sf w}(T_0)-1)+(2\mbox{\sf w}(T_1)-1)+1 \\ & =2(\mbox{\sf w}(T_0)+\mbox{\sf w}(T_1))-1 \\ & =2\mbox{\sf w}(T_0\wedge T_1)-1. \end{align*} \)

Podobnie

\( \begin{align*}\mbox{\sf h}(T_0\wedge T_1) & =\max(\mbox{\sf h}(T_0),\mbox{\sf h}(T_1) )+1 \\ & \leq \max(\mbox{\sf w}(T_0),\mbox{\sf w}(T_1) )+1 \\ & \leq \mbox{\sf w}(T_0)+\mbox{\sf w}(T_1) \\ & =\mbox{\sf w}(T_0\wedge T_1), \end{align*} \)

gdzie ostatnia nierówność wynika bezpośrednio z faktu, że szerokość każdego drzewa wynosi co najmniej \( 1 \).