Rot-Schwarz-B-Bäume

Question 1

Was sind die fünf eigenschaften eines Rot-Schwarz-Baum?

Answer 1

1. Jeder Knoten ist entweder rot oder schwarz.
2. Die Wurzel ist immer schwarz.
3. Alle Blätter (NULL-Knoten) sind schwarz.
4. Wenn ein Knoten rot ist, dann sind seine Kinderknoten immer schwarz.
5. Jeder Pfad von einem Knoten zu einem seiner Blattknoten enthält die gleiche Anzahl schwarzer Knoten. Dies wird als schwarze Höhe des Baumes bezeichnet.

Question 2

Welche Höhe hat ein RB-Baum und welche Schwaz-Höhe hat er?

Answer 2

• Ein RB-Baum garantiert die höhe O(lg (n) + 1)
• Die Schwarzhöhe ist >= h/2

Question 3

Wie ist die Laufzeit der Operationen Search, Min, Max, Successor und Predecessor?

Answer 3

Dadurch, dass ein Rot-Schwarz Baum immer balanciert ist befinden sich die Operationen immer in O(lg(n))

Question 4

Warum können Knoten im RB-Baum nicht so einfach Hinzugefügt und gelöscht werden?

Answer 4

• Beim einfügen und löschen passiert es sehr schnell, dass die Eigenschaften des RB-Baums verletzt werden.
• Daher muss man nach dem einfügen zwangsläufig den Baum danach “fixen”, was durch umfärben und rotieren passiert

Question 5

Wie funktioniert das linke rotieren in einem RB-Baum?

Answer 5

• Wir wollen um x nach links rotieren
• Das rechte Kind von x nennen wir y
• x wird das linke Kind von y
• Das vorherige linke Kind von y wird das rechte Kind von x
• Laufzeit O(1)

Question 6

Wie funktioniert das rechte rotieren in einem RB-Baum?

Answer 6

• Wir wollen um x nach rechts rotieren
• Das linke Kind von x nennen wir y
• x wird das rechte Kind von y
• Das vorherige rechte kind von y wird das linke Kind von X

Question 7

Welche Fälle gibt es bein Einfügen in einen RB-Baum?

Answer 7

1. Der Baum ist leer
2. Elternknoten von z ist linkes Kind des Großeltern Knoten und Onkel Knoten Rot
   -Es ist egal ob Z linkes oder rechtes Kind ist
3. Elternknoten von z ist linkes Kind des Großeltern Knoten und Onkel Knoten Schwarz
   -Wenn Z linkes Kind ist, muss man in den 3. Fall überführen
4. Elternknoten von Z ist rechtes Kind des Großelternknoten und Onkel Knoten Rot
   -Es ist egal ob Z linkes oder rechtes Kind ist
5. Elternknoten von Z ist echtes Kind des Großelternknoten und Onkel Knoten Schwarz
   -Ist z das rechte Kind, muss man in den 5. Fall überführen
   * Sonderfall: Wenn Eltern von Z schwarz muss nichts gemacht werden

Question 8

Wie fügt man ein, wenn der Baum leer ist

Answer 8

• Z ist die Wurzel
• Z wird umgefärbt

Question 9

Elternknoten von z ist linkes Kind des Großeltern Knoten und Onkel Knoten Rot, wie wird eingefügt?

Answer 9

1. färbe Eltern und onkel schwarz
2. färbe großvater rot
3. g wird zum neuen z

Question 10

Elternknoten von z ist linkes Kind des Großeltern Knoten und Onkel Knoten Schwarz, wie wird eingefügt?

Answer 10

1. Falls z rechtes Kind
   -z wird zum Elternknoten von z
   -Linksrotation um z
2. Färbe großvater und Eltern um
3. rotiere um g
   * Schritt 2 und 3 können vertauscht werden

Question 11

Elternknoten von Z ist rechtes Kind des Großelternknoten und Onkel Knoten Rot, wie wird eingefügt?

Answer 11

1. Färbe Eltern un Onkel schwarz
2. Färbe großvater rot
3. g wird zum neuen z

Question 12

Elternknoten von Z ist echtes Kind des Großelternknoten und Onkel Knoten Schwarz

Answer 12

1. Falls z linkes Kind
   -z wird zum Elternknoten von z
   -Rechtsrotation von z
2. Färbe großvater und Eltern um
3. rotiere um Großvater
   * Schritt 2 und 3 können getauscht werden

Question 13

Weshalb benutzt man B-Bäume und wo benutzt man sie?

Answer 13

• B-Bäume reduzieren die I/O Operationen auf Platten
• Werden daher für große Mengen von Daten genutzt, wie auf Festplatten oder Datenbanken
• Oftmals ist die höhe geringer als bei RB-Bäumen
• Die Anzahl der Kinder wird Verzweigungsgrad genannt
• Passt meistens nicht in den Hauptspeicher
• Die Wurzel ist immer im Hauptspeicher

Question 14

Welche Eigenschaften müssen B-Bäume erfüllen?

Answer 14

• Jeder Knoten hat n Schlüssel
• Jeder Knoten hat n+1 Zeiger auf seine Kinder
• Die Elemente innerhalb der Knoten sind sortiert
• Alle Blätter sind auf der selben Höhe
• Obere und untere Schranke bzgl. der Anzahl der Schlüssel, die ein Knoten enthalten kann bestimmt eine feste Zahl t - der Grad des Baumes t >= 2
• Jeder Knoten (außer der Wurzel) hat mindestens t - 1 Schlüssel und mindestens t Kinder
• Jeder Knoten (außer der Wurzel) hat möchstens 2t - 1 Schlüssel und mindestens 2t Kinder
• Höhe ist <= logt((n+1)/2) und somit O(log n)

Question 15

Wie sucht man in einem B-Baum?

Answer 15

1. Man erstellt eine Zählvariable i
2. Man iteriert durch den Knoten bis man am Ende ist oder bis das Element kleiner ist als der aktuelle Schlüssel
3. Währenddessen macht man bei jedem Durchgang Unterscheidungen
   3.1 Wenn das Element gefunden wurde gib es zurück
   3.1.1 Wenn es nicht gefunden wurde aber ein Blatt ist geb NIL zurück
   3.1.2 Wenn es nicht gefunden wurde und kein Blatt ist rufe rekursiv auf mit dem i-ten Zeiger

Question 16

Wie fügt man in einen B-Baum ein?

Answer 16

• Ist der Knoten, in welchen man Einfügen möchte nicht voll kann man das einfach machen
• Ist der Knoten voll, unterteilt man ihn in 2 teile und packt den Median in den Eltern knoten
• Ist der Eltern Knoten auch voll muss dieser auch aufgeteilt werden, im schlimmsten Fall passiert das bis zur Wurzel
• Um das zu verhindern teilt man “auf dem Weg nach unten” jeden vollen Knoten auf