Teil 1. Einleitung
Teil 2. Auswuchten und Einsetzen
Dies ist Teil 2 der Reihe „Rot-Schwarz-Baum verstehen“. Wenn Sie den ersten Teil verpasst haben, empfehle ich Ihnen dringend, ihn hier zu lesen . Dort haben wir den Grund für das Erscheinen von cchd herausgefunden und einige seiner Eigenschaften in die Regale gestellt.
In diesem Teil werden wir uns mit dem Einfügen und Auswuchten befassen. Diese Dinge gehen Seite an Seite, ohne den Baum zu balancieren, verlieren ihre Eigenschaften und es wird wenig Sinn daraus machen.
Wenn wir bedenken, dass kchd ein 2-3-Baum ist (manchmal werde ich Sie daran erinnern), werden wir sofort mit seiner Konstruktion beginnen. Einige Klarstellungen sind jedoch noch erforderlich.
Alle eingefügten Knoten mit Ausnahme der Wurzel des Baums werden mit roter Farbe eingefügt. Dies erklärt sich aus der Tatsache, dass wir einem zuerst vorhandenen Knoten immer zuerst einen Wert hinzufügen und erst danach einen Ausgleich durchführen (denken Sie an die Situation mit den resultierenden 4 Knoten).
Im ersten Teil haben wir herausgefunden, dass wir einen linksseitigen rot-schwarzen Baum zerlegen. Daraus folgt, dass rote Knoten nur links liegen können (der umgekehrte Fall erfordert einen Ausgleich).
Lassen Sie uns auch die drei Operationen behandeln, die wir beim Auswuchten benötigen. Ich bitte Sie, jetzt nicht über sie nachzudenken und sich bereits während des Baus des Baumes mit weiteren Einzelheiten zu befassen. Ich werde sie hier beschreiben, damit sie später nicht stören :)
- . , , -. , . - .
, . , .
( )
. .
, parentNode ( parentNode - x, childNode - y) childNode, . ! , , childNode , parentNode , ( , childNode - , , parentColor = RED, ). "" childNode (, tempNode). , . , childNode, parentNode, childNode, , (/) parentNode, parentNode .
( )
, . .
, parentNode . , parentNode - . , .
, ( , ), parentNode! ( ). .
- .
, .
24. . , , .
, , 5. , .
1 5. . , !
, - ( ). . - . , - . \ . , .
. , , , .
, 3 : , , .
1 , . . 5 - , ( ). 24 , , .
. - . , . - 24. .
, . ! . ( 24 , , )
( )! 2-3 .
, 2-3 ("" + ), , :) , , 2-3 , - , , "" .
. 15. 24. .
3. , 1, -1.
, . . + . ( , , ). , .
! .
, - , .
- 8. , . . , , .
+ .
, ( 15) - , . . , - . . !
- - .
, . , , . . .
. , . 2-3 ( 13 16, , ).
- , , \. .
, , .
-
-
- - , . , , . , !
- , . , , . , !
Jetzt können Sie die Konstruktion des Baums erneut durchgehen und analysieren, die Eigenschaften aus dem ersten Artikel überprüfen und die Fragen "Was wäre wenn ...?" Stellen. (Glauben Sie mir, das ist sehr nützlich!). Im Allgemeinen ist dies alles, was ich Ihnen über das Einfügen eines Knotens in einen rot-schwarzen Baum auf der linken Seite sagen wollte.
Ein wenig über die Wertesuchoperation
Der Vorgang des Erhaltens unterscheidet sich nicht von der Suche in einem anderen Binärbaum - die Farbe ist in keiner Weise daran beteiligt.
Fazit
Damit ist unser zweiter Teil über das Einfügen und Auswuchten der CD abgeschlossen. Stellen Sie Ihre Fragen, kritisieren und ergänzen Sie den folgenden Artikel! Im letzten, dritten Teil werde ich über das schwierigste Thema des rot-schwarzen Baums sprechen - das Löschen eines Elements. Bis dann:)