Bevor Sie das verstehen Rot-Schwarzer Baum und AVL-Baum Unterschiede sollten wir über den Rot-Schwarz-Baum und den AVL-Baum getrennt kennen.
Was ist ein rot-schwarzer Baum?
Der Rot-Schwarz-Baum ist ein selbstausgeglichener Baum binärer Suchbaum Dabei enthält jeder Knoten ein zusätzliches Informationsbit, das die Farbe des Knotens angibt. Die Farbe des Knotens kann je nach den vom Knoten gespeicherten Bitinformationen entweder Rot oder Schwarz sein.
q2 Monate
Eigenschaften
Die folgenden Eigenschaften sind mit einem Rot-Schwarz-Baum verbunden:
- Der Wurzelknoten des Baums sollte Schwarz sein.
- Ein roter Knoten kann nur schwarze Kinder haben. Oder wir können sagen, dass zwei benachbarte Knoten keine rote Farbe haben können.
- Wenn der Knoten kein linkes oder rechtes Kind hat, wird dieser Knoten als Blattknoten bezeichnet. Also platzieren wir die linken und rechten Kinder unterhalb des Blattknotens, der als bekannt ist Null
Die Schwarztiefe oder Schwarzhöhe eines Blattknotens kann als die Anzahl an Schwarz definiert werden, auf die wir stoßen, wenn wir vom Blattknoten zum Wurzelknoten wechseln. Eine der Schlüsseleigenschaften des Rot-Schwarz-Baums besteht darin, dass jeder Blattknoten die gleiche Schwarztiefe haben sollte.
Lassen Sie uns diese Eigenschaft anhand eines Beispiels verstehen.
Im obigen Baum gibt es fünf Knoten, von denen einer rot und die anderen vier Knoten schwarz sind. Im obigen Baum gibt es drei Blattknoten. Jetzt berechnen wir die Schwarztiefe jedes Blattknotens. Wie wir beobachten können, beträgt die Schwarztiefe aller drei Blattknoten 2; daher ist es ein rot-schwarzer Baum.
Wenn der Baum keine der oben genannten drei Eigenschaften erfüllt, handelt es sich nicht um einen Rot-Schwarz-Baum.
Höhe eines rot-schwarzen Baumes
Betrachten Sie h als die Höhe des Baums mit n Knoten. Was wäre der kleinste Wert von n? Der Wert von n ist am kleinsten, wenn alle Knoten schwarz sind. Wenn der Baum alle schwarzen Knoten enthält, wäre der Baum ein vollständiger Binärbaum. Wenn die Höhe eines vollständigen Binärbaums h ist, beträgt die Anzahl der Knoten in einem Baum:
n = 2h -1
Was wäre der größte Wert von n?
Der Wert von n ist am größten, wenn jeder schwarze Knoten zwei rote Kinder hat, der rote Knoten jedoch keine roten Kinder haben kann, sodass er schwarze Kinder haben wird. Auf diese Weise gibt es abwechselnd Schichten aus schwarzen und roten Kindern. Wenn also die Anzahl der schwarzen Schichten h ist, dann ist auch die Anzahl der roten Schichten h; Daher beträgt die Gesamthöhe des Baums 2h. Die Gesamtzahl der Knoten beträgt:
n = 2*2h-1
Was ist der AVL-Baum?
Ein AVL-Baum ist ein selbstausgleichender binärer Suchbaum, wenn wir den folgenden Fall beobachten, bei dem es sich um einen binären Suchbaum und einen ausgeglichenen Baum handelt.
Im obigen Baum beträgt die Zeitkomplexität für die Suche nach einem Element im ungünstigsten Fall O(h), d. h. die Höhe des Baums. Im obigen Fall beträgt die Anzahl der zum Durchsuchen von 17 Elementen durchgeführten Vergleiche 4 und die Höhe des Baums beträgt ebenfalls 4.
Byte-Array zum String-Java
Wenn wir den verzerrten Binärbaum betrachten, wie unten gezeigt:
Im obigen rechtsverzerrten Baum beträgt die Anzahl der Vergleiche, die zum Durchsuchen von 17 Elementen durchgeführt werden, 5, und die Anzahl der im Baum vorhandenen Elemente beträgt ebenfalls 5. Daher können wir sagen, dass die zeitliche Komplexität zunimmt, wenn der Baum ein verzerrter Binärbaum ist wäre O(n).
Jetzt müssen wir diese verzerrten Bäume so ausbalancieren, dass sie die zeitliche Komplexität O(h) haben. Es gibt einen Begriff, der als a bekannt ist Ausgleichsfaktor , das zum Selbstausgleich des binären Suchbaums verwendet wird. Der Ausgleichsfaktor kann wie folgt berechnet werden:
Ausgleichsfaktor = Höhe des linken Teilbaums – Höhe des rechten TeilbaumsDer Wert des Ausgleichsfaktors kann entweder 1, 0 oder -1 sein. Wenn jeder Knoten im Binärbaum einen Wert von 1, 0 oder -1 hat, wird dieser Baum als ausgeglichen bezeichnet Binärbaum oder AVL-Baum.
Der Baum wird als perfekt ausgeglichener Baum bezeichnet, wenn der Ausgleichsfaktor jedes Knotens 0 ist. Der AVL-Baum ist ein nahezu ausgeglichener Baum, da jeder Knoten im Baum den Wert des Ausgleichsfaktors entweder 1, 0 oder -1 hat.
Unterschiede zwischen dem Rot-Schwarz-Baum und dem AVL-Baum.
Im Folgenden sind die Unterschiede zwischen dem Rot-Schwarz-Baum und dem AVL-Baum aufgeführt:
Der Rot-Schwarz-Baum ist ein binärer Suchbaum, und der AVL-Baum ist ebenfalls ein binärer Suchbaum.
Die folgenden Regeln werden in einem Rot-Schwarz-Baum angewendet:
- Der Knoten in einem Rot-Schwarz-Baum ist entweder rot oder schwarz gefärbt.
- Die Farbe des Wurzelknotens sollte schwarz sein.
- Die angrenzenden Knoten sollten nicht rot sein. Mit anderen Worten können wir sagen, dass der rote Knoten keine roten Kinder haben kann, der schwarze Knoten jedoch schwarze Kinder.
- In jedem Pfad sollte die gleiche Anzahl schwarzer Knoten vorhanden sein. dann kann nur ein Baum als rot-schwarzer Baum betrachtet werden.
- Die externen Knoten sind die Nullknoten, die immer schwarz sind.
Regel des AVL-Baums:
Javascript-Operatoren
Jeder Knoten sollte den Ausgleichsfaktor entweder -1, 0 oder 1 haben.
In der obigen Abbildung müssen wir prüfen, ob der Baum ein rot-schwarzer Baum ist oder nicht. Um dies zu überprüfen, müssen wir zunächst prüfen, ob der Baum ein binärer Suchbaum ist oder nicht. Wie wir in der obigen Abbildung sehen können, erfüllt es alle Eigenschaften des binären Suchbaums; Daher handelt es sich um einen binären Suchbaum. Zweitens müssen wir überprüfen, ob es die oben genannten Regeln erfüllt oder nicht. Der obige Baum erfüllt alle oben genannten fünf Regeln; Daher wird der Schluss gezogen, dass es sich bei dem oben genannten Baum um einen Rot-Schwarz-Baum handelt.
In der obigen Abbildung müssen wir prüfen, ob der Baum ein AVL-Baum ist oder nicht. Da jeder Knoten einen Gleichgewichtsfaktorwert von -1, 0 oder 1 hat, handelt es sich um einen AVL-Baum.
Wenn im Fall eines Rot-Schwarz-Baums alle oben genannten Regeln erfüllt sind und es sich bei dem Baum um einen binären Suchbaum handelt, wird der Baum als Rot-Schwarz-Baum bezeichnet.
Wenn im Falle des AVL-Baums der Ausgleichsfaktor -1, 0 oder 1 beträgt, wird der obige Baum als AVL-Baum bezeichnet.
Wenn der Baum nicht ausgeglichen ist, werden zwei Werkzeuge verwendet, um den Baum in einem Rot-Schwarz-Baum auszugleichen:
Wenn der Baum nicht ausgeglichen ist, wird ein Tool zum Ausgleichen des Baums im AVL-Baum verwendet:
Im Fall des Rot-Schwarz-Baums sind die Einfüge- und Löschvorgänge effizient. Wenn der Baum durch die Umfärbung ausgeglichen wird, sind Einfüge- und Löschvorgänge im Rot-Schwarz-Baum effizient.
Im Fall des AVL-Baums ist der Suchvorgang effizient, da nur ein Werkzeug zum Ausbalancieren des Baums erforderlich ist.
Im Fall des Rot-Schwarz-Baums beträgt die Zeitkomplexität für alle Operationen, d. h. Einfügen, Löschen und Suchen, O(logn).
Im Fall des AVL-Baums beträgt die Zeitkomplexität für alle Operationen, d. h. Einfügen, Löschen und Suchen, O(logn).
Ins-Taste
Lassen Sie uns die Unterschiede in der Tabellenform verstehen.
| Parameter | Roter schwarzer Baum | AVL-Baum |
|---|---|---|
| Suchen | Der Rot-Schwarz-Baum bietet keine effiziente Suche, da die Rot-Schwarz-Bäume ungefähr ausgeglichen sind. | AVL-Bäume ermöglichen eine effiziente Suche, da es sich um streng ausgeglichene Bäume handelt. |
| Einfügen und Löschen | Das Einfügen und Löschen ist im Rot-Schwarz-Baum einfacher, da weniger Drehungen erforderlich sind, um den Baum auszugleichen. | Das Einfügen und Löschen ist im AVL-Baum komplex, da mehrere Drehungen erforderlich sind, um den Baum auszugleichen. |
| Farbe des Knotens | Im Rot-Schwarz-Baum ist die Farbe des Knotens entweder Rot oder Schwarz. | Bei AVL-Bäumen gibt es keine Farbe des Knotens. |
| Balancefaktor | Es enthält keinen Ausgleichsfaktor. Es speichert nur ein Informationsbit, das entweder die rote oder die schwarze Farbe des Knotens angibt. | Jeder Knoten hat einen Ausgleichsfaktor im AVL-Baum, dessen Wert 1, 0 oder -1 sein kann. Es erfordert zusätzlichen Speicherplatz, um den Ausgleichsfaktor pro Knoten zu speichern. |
| Streng ausgewogen | Rot-Schwarz-Bäume sind nicht streng ausbalanciert. | AVL-Bäume sind streng ausgeglichen, d. h. die Höhe des linken Teilbaums und die Höhe des rechten Teilbaums unterscheiden sich um höchstens 1. |