RedBlack und AVL-Baum C++

Question

Ich möchte die Implementierung von rot schwarz und AVL-Bäume mit C++ zu verstehen. Ich habe einige Websites über sie überprüft, aber die meisten sind komplex und schwer zu verstehen. Könnten Sie mir bitte einige Ressourcen vorschlagen?

Answer 1

Lesen Sie zuerst die grundlegenden Eigenschaften der beiden Bäume. Sie müssen sich nicht auf eine Programmiersprache beschränken. Wenn Sie diese Eigenschaften verstehen, können Sie sie selbst in jeder Sprache implementieren.

Eigenschaften von Rot Schwarz Baum:

1. Ein Knoten entweder rot oder schwarz ist.
2. Die Wurzel ist schwarz. Diese Regel wird manchmal weggelassen. Da die Wurzel immer von rot nach schwarz geändert werden kann, aber nicht notwendigerweise umgekehrt, hat diese Regel wenig Einfluss auf die Analyse.
3. Alle Blätter (NIL) sind schwarz.
4. Wenn ein Knoten rot ist, sind beide untergeordneten Objekte schwarz.
5. Jeder Pfad von einem gegebenen Knoten zu einem seiner nachfolgenden NIL-Knoten enthält die gleiche Anzahl von schwarzen Knoten. Einige Definitionen: Die Anzahl der schwarzen Knoten von der Wurzel zu einem Knoten ist die schwarze Tiefe des Knotens; Die einheitliche Anzahl von schwarzen Knoten in allen Pfaden von der Wurzel zu den Blättern wird die Schwarzhöhe desRot-Schwarz-Baums genannt.

Red Black Tree C++ Code: http://www.sanfoundry.com/cpp-program-implement-red-black-tree/

AVL-Baum Tutorial: https://www.youtube.com/watch?v=rwzuze_tTwQ

AVL-Baum C++ Code: https://tfetimes.com/c-avl-tree/