Red Black Tree

Red-Black-Tree.md

Testkonzept und durchführung

Für den Rot-Schwarz-Baum haben wir uns entschlossen, eine neue statische Methode test innerhalb der Klasse RedBlackTree zu entwerfen. Diese überprüft mithilfe verschiedener vordefinierten Bäumen alle Funktionen auf Richtigkeit.

Diese Überprüfungen sind unterteilt in:

• Überprüfen ob die Schlüssel an der richtigen Stelle eingefügt werden
• Überprüfen ob die Rotationen korrekt implementiert sind
• Überprüfen der Eigenschaften eines Rot-Schwarz-Baumes.

Dazu wird innerhalb der statischen Methode zuerst ein neuer Baum speziell für die Linksrotation erzeugt, und die oben dargestellten Nodes - mit einem String als Data zum einfachen Debuggen - eingefügt:

static bool test() {
                RedBlackTree testLeftRotation = RedBlackTree();

		testLeftRotation.insertKey(7, "bin root");
		testLeftRotation.insertKey(4, "bin links von root");
		testLeftRotation.insertKey(11, "bin rechts von root");
                etc.
}

Nachdem der Baum erstellt wurde, überprüfen wir, ob die Knoten alle an den richtigen Stellen eingefügt wurden:

		assert(testLeftRotation.root->key == 7);
		assert(testLeftRotation.root->left->key == 4);
		assert(testLeftRotation.root->right->key == 11);
		assert(testLeftRotation.root->right->right->key == 18);
		assert(testLeftRotation.root->right->left->key == 9);
		assert(testLeftRotation.root->right->right->left->key == 14);
		assert(testLeftRotation.root->right->right->right->key == 19);

Anschließend führen wir eine Linksrotation auf den ersten rechten Knoten der Wurzel (11) aus:

testLeftRotation.leftRotate(testLeftRotation.root->right);

Danach erwarten wir, dass unser Baum wie folgt aussieht:

Dies überprüfen wir mithilfe weiterer Asserts:

		assert(testLeftRotation.root->key == 7);
		assert(testLeftRotation.root->left->key == 4);
		assert(testLeftRotation.root->right->left->key == 11);
		assert(testLeftRotation.root->right->key == 18);
		assert(testLeftRotation.root->right->left->left->key == 9);
		assert(testLeftRotation.root->right->left->right->key == 14);
		assert(testLeftRotation.root->right->right->key == 19);

Für die Rechtsrotation verwenden wir einen anderen Baum:

Hier führen wir die RightRotation an dem Knoten 12 durch.

Anschließend prüfen wir das Ergebnis auf richtigkeit, analog zur Linksrotation erhalten wir folgenden Baum:

Auch hier werden Anschließend die erwarteten Werte mithilfe von Asserts überprüft.

Nach dem Überprüfen der Rotationen gehen wir nachfolgend die Eigenschaften aus Cormen et al "Algorithmen – Eine Einführung" (Seite 311) ein, welche im Gegensatz zu unsere Rotationschecks auch die Farben überprüfen:

1. Jeder Knoten ist entweder rot oder schwarz.
2. Die Wurzel ist schwarz.
3. Jedes Blatt (nil) ist schwarz.
4. Wenn ein Knoten rot ist, dann sind seine beiden Kinder schwarz.
5. Für jeden Knoten enthalten alle einfachen Pfade, die an diesem Knoten starten

Hierfür erstellt unsere statische Methode test einen weiteren Rot-Schwarz-Baum x.

Da wir in unserer insertKey-Implementation sicherstellen, dass wir bei einem Node die Eigenschaft ìsRed auf 0 oder 1 setzen, können wir die Prüfung auf einen einfachen not NULL-Check beschränken:

assert(x->isRed == 0 || x->isRed == 1);	

Für die zweite Bedingung rufen wir innerhalb unserer Haupttestmethode ebenfalls ein einfaches Assert auf die Wurzel auf:

assert(root);

Da wir unsere Überprüfungsmethode Rekursiv gestaltet haben, überprüfen wir die restlichen Eigenschaften durch Aufrufe von der validation-Methode auf sich selbst:

bool validation(Node* x, int* leftCounter, int* rightCounter)

Um 3) zu überprüfen, überprüfen wir einfach ob das aktuelle Node ein Blatt ist und überprüfen ob es Schwarz ist. Da wir einen Wächter benutzen (Wächter bedeutet in diesem Fall dass die Children Nullpointer sind), ist diese Überprüfung ebenfalls ein kurzer Zweizeiler:

	if (x->left == nullptr && x->right == nullptr && x->isRed == 0)
		assert(x->isRed == 0);

Um die vierte Eigenschaft zu prüfen, schauen wir einfach ob das aktuelle Node Rot ist, und falls es Kinder hat, überprüfen wir ob diese Schwarz sind. Falls es keine Kinder hat, sind diese Kinder implizit Schwarz durch den Nullpointer-Wächter:

	if (x->isRed) {
		if (x->left) {
			assert(x->left->isRed == 0);
		}
		if (x->right) {
			assert(x->right->isRed == 0);
		}
	}

Zuletzt überprüfen wir die letzte und kniffligste Eigenschaft. Diese Eigenschaft ist der Hauptgrund, weshalb diese Testfunktion überhaupt rekursiv ist. Durch die Möglichkeit der Rekursion können wir einfach einen Pointer zu einem Counter mitgeben und für Linke und Rechte Child Nodes inkrementieren. Dann können wir einfach rekursiv unsere Funktion mit den Kindern aufrufen, und so den gesamten Subtree traversieren:

	if (!x->isRed && x->left)
		*leftCounter = *leftCounter + 1;

	if (!x->isRed && x->right)
		*rightCounter = *rightCounter + 1;


	// go down to the decending nodes
	if (x->left)
		validation(x->left, leftCounter, rightCounter);
	if (x->right)
		validation(x->right, leftCounter, rightCounter);