Bei Anschluss an einen rot-schwarzen Baum Umwandlung, gibt es keinen Grund eine Form über eine andere zu wählen?

Question

Ich habe eine Bibliothek von verknüpften Liste / Binärbaum Methoden für den Einsatz bei Standardcontainer passen nicht - z.B. wenn es verschiedene Typen von Knoten, oder wenn ich von binären Baum konvertieren müssen wieder zur Liste und zurück. Es schließt Rot-Schwarz-Baum Handling.

Eines des Verfahrens wandelt von einer Doppel verknüpften Liste zu einem perfekt ausgewogenen einfachen binären Baum in O(n) Zeit (vorausgesetzt, dass die Anzahl der Elemente im Voraus bekannt ist). Der Algorithmus wird als „Faltung“ bekannt - es ist die zweite Hälfte eines binären Baum Rebalancing Algorithmus, der einmal in Dr. Dobbs' veröffentlicht wurde. Die Schritte sind im Grunde ...

• die Größe des Baumes gegeben, entscheiden über die Größe der linken und rechten Teilbäume

• Recurse für den linken Unterbaum

• Pop einen Knoten aus der Liste als die Wurzel verwenden

• Recurse für den rechten Teilbaum

• Verknüpfen Sie die Teilbäume an der Wurzel

Ich habe auch ein ähnliches Verfahren, das einen rot-schwarz-Baum erstellt. Das Prinzip ist das gleiche, aber die Rekursion verfolgt Knotenhöhe - Höhe Null-Knoten erstellt rot, alle anderen sind schwarz. Die Starthöhe wird berechnet nach dem höchsten Satz Bit in der Baumgröße basiert, und wird getüftelt, so dass ein perfekt ausbalanciertes (2^n)-1 großer Baum nur schwarzen Knoten hat (die Rekursion geht nur bis zu der Höhe eins).

Hier Der Punkt ist, dass ich nur auf der Blattebene roten Knoten haben, und maximal genau die Hälfte der Knoten sind rot.

Die Sache ist, während dies eine einfache Art und Weise ist ein gültigen Rot-Schwarz-Baum zu erzeugen, es ist nicht die einzige Option. Vermeiden Sie alle Blätter mit rot in einem perfekt ausgewogenen Baum war eine willkürliche Wahl. Ich konnte Schichten von roten und schwarzen Knoten haben abwechseln. Oder ich könnte die Anzahl der roten Knoten dramatisch in einigen Fällen reduzieren, indem sie Teilbäume Spek, die perfekt ausbalanciert sind und (wenn es rote Knoten benötigt) machen die Unterstruktur root rot statt all seine Blätter.

Die Frage ist - gibt es einen praktischen Grund eine gültige rot-schwarze Baumform über eine anderen wählen

Das ist reine Neugier - ich weiß, dass ich keinen praktischen Grund habe - aber jemand eine Fachanwendung nicht wissen, wo diese Wahl von Bedeutung ist

Answer 1

In der Standardanalyse der fortgeführten Anschaffungskosten zu modifizieren rot-schwarz Bäume der pysicist Methode verwenden, schwarze Knoten mit entweder null oder zwei roten Kindern ein positives Potential von einem zugewiesen, was bedeutet, dass sie problematische Stellen im Baum darstellen, wo zusätzlichen Arbeit kann getan werden müssen. Rote Knoten und schwarze Knoten mit genau einem roten Kind ein Potential von Null zugeordnet.

So, die Kosten für die Änderungen zu reduzieren, jedem schwarzen Knoten ein rotes Kind geben.

---

Der Grund , warum schwarzer Knoten mit einem roten Kind gesegnet sind am besten durch Analogie erklärt Binärzahlen Redundant. Ich werde zunächst erklären, wie rot-schwarze Bäume in Binärzahlen beziehen und dann werde ich erklären, warum ein rot-Kind-Knoten nützlich ist.

Wie Sie vielleicht wissen, rot-schwarz Bäume sind ein Weg 2-4 Bäume repräsentieren, in dem jeder einfachen Weg von der Wurzel zu einem Blatt die gleiche Länge hat aber Knoten hat 2, 3 oder 4 Kinder. Der einfachste Algorithmus für das Hinzufügen oder einen Knoten in einem 2-4-Baum zu entfernen, ist den gleichen Algorithmus wie das Hinzufügen oder Subtrahieren von eins von A Redundanzbinärzahl .

Eine redundante binäre Zahl ist eine Zahl, in der die i-te Ziffer steht für 2 ⁱ , wie in einem Standard-Binärzahl, aber die i-te Ziffer kann 0, 1, oder 2 . Sie sind überflüssig bezeichnet, da es mehr Möglichkeiten gibt, eine bestimmte Anzahl zu schreiben. 4 _Dezember kann geschrieben 100 oder 20 oder 12 sein.

ein zu einer redundanten Binärzahl hinzuzufügen, erhöhen Sie die niedrigstwertige Stelle; wenn es 3 ist, setzen Sie ihn auf 1 und die nächste niedrigstwertige Ziffer zu erhöhen, und so weiter. Der Algorithmus stoppt, wenn es eine 0 trifft oder 1 ist.

Um ein Blatt zu einem 2-4-Baum hinzufügen, um ein Kind zu seinen beabsichtigt Eltern hinzuzufügen. Wenn die Eltern, wie fünf Kinder hat, es in zwei Knoten aufgeteilt und sie Kinder ihrer Eltern machen. Weiter, bis Sie einen Knoten erreichen, die nicht Spaltung benötigt. So ist der Weg in der Wurzel anhält, wenn es einen Knoten mit zwei oder drei Kindern begegnet.

Um gebunden die fortgeführten Anschaffungskosten eine redundante Binärzahl erhöht wird, verwenden Sie die Physiker Verfahren und ein Potential von 1 bis jede Ziffer 2 zugeordnet werden. Ein XALL zu erhöhen, die k Ziffern Versionen k-1 Potential berührt, ist es eine fortgeführten Anschaffungskosten von O geben (1).

Diese Analyse ist ähnlich die fortgeführten Anschaffungskosten einen Standard-Binärzahl erhöht wird, sondern eine Standard-Binärzahl kann sowohl Inkrement- und Dekrement in O nicht unterstützen (1) abgeschrieben Zeit: betrachtet 2 ^k - 1. es ist k 1 Ziffern. Increment kostet Θ (k). Wenn das durch eine Abnahme folgt, das Paar kostet Θ (k) und bringt die Zahl wieder in seinen alten Zustand.

Redundanzbinärzahlen ist etwas Besonderes, dass 1 Ziffern die kaskadierende Operationen sowohl Inkrement- und Dekrement stoppen. 2-4 Bäume sind spezielle, dass 3-Knoten, die die Kaskadierung Operationen beide Einsatzes stoppen und löschen.

In rot-schwarzen Bäumen, ein Knoten mit einem roten Kind ist nur eine Darstellung eines 3-Knoten in einem 2-4-Baum. Diese Knoten sind spezielle und robust gegenüber Einsätze oder löscht in ihren Teilbäume, so sollten Sie sie bevorzugen beim Bau von Rot-Schwarz-Bäume, die eine Menge Updates sehen.

Wenn Sie wissen, dass Sie nur Einsätze sehen werden, bevorzugen Knoten mit zwei schwarzen Kindern. Wenn Sie wissen, werden Sie sehen, nur löscht, favorisieren Knoten mit zwei roten Kinder.

Answer 2

Die kurze Antwort lautet: es hängt

.

Grundsätzlich wird jeder gültige Baum ausreichen. Doch in Bezug auf abgeschrieben Analyse - es könnte sehr wahrscheinlich sein, dass Sie die wählen wollen korrekteste Baum, dass auf lange Sicht wird Ihnen das am besten optimierten Verhalten.

z. wenn Sie immer einen gültigen Baum wählen, aber eine, die viele Auswuchtungsarbeiten anfällig ist, werden Sie schlecht amortisierten Leistung. Ein offensichtliches Beispiel ist ein vollständig schwarz Baum, der perfekt gültig ist, noch führt schlecht, wenn geändert.

Es hängt davon ab, da dies in der Regel anwendungsspezifisch sein.