Beweis des Satzes 1

Nächste Seite: Der Algorithmus Aufwärts: Rot-Schwarz Baeume Vorherige Seite: Definition und Eigenschaften Inhalt Index

Beweis des Satzes 1

Definition 4.2: Der Rang eines Knotens K in einem Rot-Schwarz Baum gibt die Anzahl von schwarzen Knoten auf einem Pfad von einem Blatt bis zu K an. Den Rang der Wurzel bezeichnen wir als Rang oder schwarze Hoehe des Rot-Schwarz Baumes. Der Rang hat folgende Eigenschaften:

Alle externen Knoten haben den Rang ,,0''
Wenn ein schwarzer Knoten den Rang r hat, so hat sein Elternknoten den Rang r+1
wenn ein roter Knoten den Rang r hat, so hat sein Elternknoten den Rang r

Fuer die folgenden Eigenschaften sei h die Hoehe des Rot-Schwarz Baumes und r der Rang der Wurzel. n sei die Anzahl von Knoten in dem Rot-Schwarz Baum.

Aussage 1: Es gilt: $\frac{h}{2}\leq r\leq h$ .

Beweis: Der Rang der Wurzel ist groesser oder gleich $\frac{h}{2}$ per Definition fuer Hoehe und Rang. Die Hoehe ist die Anzahl der Knoten auf dem laengsten Pfad von einem Blatt zur Wurzel. Der Rang r ist die Anzahl der schwarzen Knoten auf diesem Pfad (da laut Rot-Schwarz Baum Eigenschaft 2 jeder Pfad die gleiche Anzahl von schwarzen Knoten enthaelt). Da jeder rote Knoten laut Eigenschaft 3 eines Rot-Schwarz Baumes ausschliesslich schwarze Nachbarn haben darf, koennen maximal die Haelfte der Knoten eines Pfades rot sein. Die andere Haelfte ist schwarz und entspricht damit r. Deshalb gilt $\frac{h}{2}\leq r$ . Der andere Teil der Ungleichung ist offensichtlich erfuellt. r ist Anzahl von schwarzen Knoten auf dem laengsten Pfad von der Wurzel bis zu einem Blatt, h die Anzahl von Knoten auf diesem Pfad. Es koennen nicht weniger Knoten als schwarze Knoten auf dem Pfad vorhanden sein.

Aussage 2: Ein Knoten vom Rang r hat mindestens 2 $^{r}$ externe Knoten in seinem Unterbaum.

Beweis durch Induktion ueber den Rang:

r=1: Die Wurzel hat 2 $^{1}$ externe Knoten und damit ist die Aussage 2 wahr.
Annahme: Die Aussage 2 ist wahr bis einschliesslich r-1.
Da die Anzahl der externen Knoten in den Unterbaeumen jeweils mindestens 2 $^{r-1}$ betraegt:

$2^{r-1}+2^{r-1}=\frac{2^{r}}{2}+\frac{2^{r}}{2}=2^{r}$ .

Damit ist gezeigt, dass stets mindestens 2 $^{r}$ externe Knoten in dem Unterbaum eines Knoten vom Rang r sind.

Aussage 3: $f(n)=\log _{2}(n+1)$ ist streng monoton steigend fuer alle Werte von $n\geq 0$ .

Beweis: Die erste Ableitung der Funktion lautet $f'(n)=\frac{1}{(n+1)\ln (2)}$ .

$f'(n)>0$ ist fuer alle $n\geq 0$ definiert und gueltig.

Wenn $r>\log _{2}(n+1)$ , dann wuerde der Rot-Schwarz Baum mehr als $2^{log_{2}(n+1)}=n+1$ externe Knoten in einem Unterbaum haben. Laut Definition 2.4 besitzt ein regulaerer binaerer Baum jedoch genau $\frac{n+1}{2}$ Knoten vom Grad eins, also externe Knoten.

Deshalb muss gelten: $n+1\leq \frac{n+1}{2}$ , und deshalb $2n+2\leq n+1$ und schliesslich $n\leq -1$ . Und damit gilt auch folgende Aussage: $r\leq \log _{2}(n+1)\bigwedge n\geq 0$ .

Laut Aussage 1 gilt: $h\leq 2r\leq 2log_{2}(n+1)$

Nächste Seite: Der Algorithmus Aufwärts: Rot-Schwarz Baeume Vorherige Seite: Definition und Eigenschaften Inhalt Index

root 2000-01-25