Java-Interview-Rot-Schwarz-Baum

Werfen wir zunächst einen Blick auf die Struktur des rot-schwarzen Baums, wie im Bild gezeigt:

(Teilen von Lernvideos: Java-Lehrvideo)

Die strukturellen Eigenschaften des Roten -schwarzer Baum:

(1) Jeder Knoten ist entweder schwarz oder rot.
(2) Der Wurzelknoten ist schwarz.
(3) Jeder Blattknoten (NIL) ist schwarz. [Hinweis: Der Blattknoten bezieht sich hier auf den Blattknoten, der leer ist (NIL oder NULL)! ]
(4) Wenn ein Knoten rot ist, müssen seine untergeordneten Knoten schwarz sein.
(5) Alle Pfade von einem Knoten zu den Nachkommenknoten des Knotens enthalten die gleiche Anzahl schwarzer Knoten.

Warum rote und schwarze Bäume verwenden?

1. Erstens erfüllen Rot-Schwarz-Bäume nicht die Gleichgewichtsbedingungen von AVL-Bäumen, also binären Suchbäumen, bei denen sich die Höhen des linken Teilbaums und des rechten Teilbaums jedes Knotens um höchstens 1 unterscheiden. Es wird jedoch vorgeschlagen, den Knoten Farben hinzuzufügen, indem ein nicht striktes Gleichgewicht verwendet wird, um die Anzahl der Drehungen beim Hinzufügen oder Löschen von Knoten zu verringern. AVL ist ein strikt ausgeglichener Baum. Wenn also Knoten hinzugefügt oder gelöscht werden, ist die Anzahl der Umdrehungen je nach Situation höher als die des rot-schwarzen Baums. Daher ist die Einfügungseffizienz von rot-schwarzen Bäumen höher

(Empfehlungen für verwandte Interviewfragen: Java-Interviewfragen und -antworten)

2 Rot-schwarze Bäume können mit einer Zeitkomplexität von O(log2 (n.) suchen )), Einfüge- und Löschoperationen

3 Einfach ausgedrückt dient der Rot-Schwarz-Baum dazu, die Mängel des binären Suchbaums zu beheben, da der binäre Suchbaum in einigen Fällen zu einer linearen Struktur degeneriert.

Vergleich und Auswahl von rot-schwarzen Bäumen und ausgeglichenen Bäumen

1 Die ausgeglichene Baumstruktur ist intuitiver und die Leseleistung ist höher als beim rot-schwarzen Baum So gut wie der rot-schwarze Baum
2. Die Leseleistung ist nicht so gut wie die des ausgeglichenen Baums. Die Leistung beim Hinzufügen und Löschen von Knoten zur Wiederherstellung des Gleichgewichts ist schlechter als die des ausgeglichenen Baums Rot-Schwarz-Bäume:

TreeMap, TreeSet und die unterste Ebene von HashMap nach JDK1.8 verwenden alle rot-schwarze Bäume.

Verwandte Empfehlungen:

Java-Einführungs-Tutorial

Das obige ist der detaillierte Inhalt vonJava-Interview-Rot-Schwarz-Baum. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!