Ich habe ziemlich lange mit dem rot-schwarzen Baum ( im Folgenden - kchd ) gekämpft . Alle Informationen, die ich gefunden habe, waren im Sinne von "Die Blätter und Wurzeln des Baumes sind immer schwarz, WEIL", "Top 5 Eigenschaften eines rot-schwarzen Baums" oder "3 Fälle beim Balancieren und 12 Fälle beim Entfernen eines Knotens". Diese Anordnung passte nicht zu mir.
Ich wollte mir keine Baumeigenschaften, Pseudocodes und Ausgleichsoptionen merken, ich wollte wissen warum. Wie helfen Farben beim Ausbalancieren? Warum kann ein roter Knoten kein rotes Kind haben? Warum wird die Tiefe eines Baumes als "schwarze Höhe" gemessen?
Antworten auf diese Fragen erhielt ich erst, als ich einen Link zu einem Vortrag über zwei oder drei Bäume erhielt, mit dem wir beginnen werden.
Dieser Artikel ist in 3 logische Teile unterteilt. Ich empfehle, sie in der angegebenen Reihenfolge zu lesen. Der erste Teil (dieser) zielt auf eine Einführung in ccd und das Kennenlernen ab. Im zweiten Teil werden wir über das Balancieren und Einfügen in ccd sprechen. Im dritten und letzten Teil werden wir den Prozess des Löschens eines Knotens analysieren. Bitte haben Sie etwas Geduld und viel Spaß beim Lesen :)
Haftungsausschluss
In diesem Artikel gibt es keine Informationen über die Vor- und Nachteile des Baums, seine Anwendung usw .: Es gibt viele Informationen über die Asymptotik des Baums und die Arbeit damit im Internet.
Das Material richtet sich an diejenigen, die bereits mit ccd vertraut sind und diese nun verstehen möchten, sowie an diejenigen, die sie gerade erst kennenlernen.
Der Artikel enthält keine Details zur Implementierung der Struktur.
— . .
-
- , -
, , - - , , , . - - .
- - , . - ( , ). 2-, - 3-. : . :
, .
- , - .
- - , .
, , 5. - 5 .
12. 12 (, ), "" ( , ), .. . 5-12.
. 17. . 5-12-17.
- , . ! "" . . 12, 5, - 17.
, , - . : , "" . 3 :
. , ( ).
. ( ).
. , .
.
, . 3. , . , 3 5. 3 5 . 3-5.
, :)
4 3-5. 3-4-5, , , . ? , .. "" 4 .
. , 4 , - , 4. 5. :
5 ? : - , - . 5 4, 5 , .. . 5 , "", 4-12 (, 5 , "" ).
, . :
, , .
, , , .
, , .
, . , , - . , - (, 4-5-12, , 5 4 12). , . , , ( , 7? 9?).
, , , . , , , . .
, , , . , , ( ). - .
-
, - - . - . ?
, 3-. 3- 2- . - , , , ( ), .
, , .
, - . , , ( , ).
-
, - , , 3- ( ). , , . , ( ).
1.
. , , - 3- 2-3 . , 4-, :)
2.
. , : .
3.
null- (, ) - . , . , , .
Da wir Nullknoten berührt haben, sollte gesagt werden, dass alle Knoten im Baum immer zwei Nachkommen haben sollten. Wenn der Verweis auf den Nachkommen Null ist, führt er genau zum Nullknoten. Tatsächlich wirft dies eine Frage bei der Implementierung auf. Es war für mich bequemer, einen Nullknoten hinzuzufügen (weniger Probleme mit Iteratoren, Balancing usw.).
Eigentum 4.
Die Höhe des Baumes wird nur durch schwarze Knoten gemessen und als "schwarze Höhe" bezeichnet. Auch hier wird im Allgemeinen alles offensichtlich: Der rote Knoten ist nur eine Ergänzung zum schwarzen Knoten, er ist ein Teil davon, daher wird angenommen, dass die Höhe auf schwarzen Knoten basiert.
Damit ist die Einführung abgeschlossen. Im nächsten Teil werden wir darüber sprechen, wie Knoten in einen Baum eingefügt und ausgeglichen werden.