Ich habe viele Artikel auf Red Black Tree, wo es O (log n) Zeit für Operationen. Ich bin nicht ganz klar, wie es funktioniert und wie eigentlich Baumkarte verwendet rot schwarzen Baum-Algorithmus um den Baum im Vergleich zum binären Suchbaum auszugleichen.Wie Baumkarte Rot-Schwarz-Baum-Algorithmus verwendet
Kann jemand bitte mit einem Beispiel erklären, wie der Algorithmus funktioniert.
Ein rot-schwarzer Baum ist ein binärer Suchbaum. Es ist nur eine Variante von BST, die über ausgefeilte Versionen der Operationen insert und delete verfügt, die den Baum so organisieren, wie er läuft, damit der Baum niemals "lang und strähnig" wird. Je länger und streicher ein Baum wird, desto mehr verhält er sich wie eine verkettete Liste. Im Durchschnitt erfordern verkettete Listenoperationen, dass die Hälfte der Liste berührt wird (oder die gesamte Liste im schlimmsten Fall), so dass die Laufzeit linear variiert (O (n) in der Anzahl der Elemente n). Wenn der Baum "buschig" oder fast ausgeglichen ist, sind die Operationen viel billiger (O (log n)). Die Rot-Schwarz-Algorithmen garantieren, dass der Baum buschig bleibt.
Um dies konkret zu machen, hier sind zwei Bäume, die die Schlüssel A bis G speichern. Die linke Seite ist lang und strähnig. Beachten Sie, wie es aussieht wie eine Liste. Im schlimmsten Fall benötigt man 4 Schlüsselvergleiche, um ein Element zu finden. Der Baum rechts ist buschig. Es braucht nur 3. Hier ist der Unterschied gering. Für einen Baum mit 1023 Elementen benötigt der sehnige Baum 512 Vergleiche und der buschige nur 10. Dies ist die Stärke von log n.
B _D_
/\ / \
A D B F
/\ /\ /\
C F A C E G
/\
E G
Der rot-schwarz-Baum ist nicht garantiert perfekt buschig sein (in der richtigen Terminologie „perfekt ausbalanciert“), aber die rot-schwarze Regeln garantieren, dass es so, dass Betriebszeiten in eine mathematisch strengen Weise buschigen genug variieren als der Logarithmus von n statt linear in n.
Das Genie der rot-schwarzen Regeln ist, dass sie "lokal" sind. Während einer Einfügung oder Löschung, die die Regeln bricht, ist es möglich, sie wiederherzustellen, indem nur eine konstante Anzahl von Knoten für jeden von der Operation berührten Knoten eingestellt wird. Daher sind sie billig und relativ einfach zu implementieren.
Doch wenn die Rot-Schwarz-Regeln für den ganzen Baum gelten, ist es möglich, durch einen geschickten mathematischen Beweis zu zeigen, dass es wie oben beschrieben buschig genug ist.
Was ist mit der Baumkarte? Eine Karte ist eine Funktion mit einer Domäne, die Schlüsselsatz K genannt wird, und Bereich, der als Wertsatz V bezeichnet wird. Um eine Baumstruktur zu implementieren, speichert jeder Knoten ein Schlüsselwertpaar <k,v> mit k \in K und v \in V. In den obigen Zeichnungen (und den meisten Präsentationen) sind nur Tasten (Buchstaben A-G) gezeigt. In der Map funktionieren Insertion, Lookup und Deletion an diesen Paaren auf ziemlich offensichtliche Weise. Zum Beispiel sucht die Suche mit dem üblichen BST-Algorithmus nach einem Schlüssel. Wenn der Schlüssel gefunden wird, wird der Wert ebenfalls gefunden, da er sich in demselben Paar befindet. Das ist, was zurückgekehrt ist. In Java heißt das Paar Map.Entry. Sie können dies in der Java source code überprüfen.
Ich werde nicht in die Details gehen, wie die rot-schwarzen Regeln funktionieren, weil ich the Wikipedia page nicht verbessern konnte. Meine Vermutung und Hoffnung ist, dass Sie das "große Bild" vermisst haben, so dass die Diskussion jetzt Sinn ergibt. Die gute Nachricht ist, dass fast alle Sprachen eine gründlich getestete und leistungsoptimierte Baumimplementierung bieten, weshalb es nicht notwendig ist, die obskuren Details von Rotationen zu kennen. Natürlich, wenn Sie neugierig sind und einfach nur wissen wollen, haben Sie es geschafft! Herzliche Glückwünsche!
Für was es wert ist, Top Coder Erklärungen von Algorithmen sind nicht immer am klarsten. Suche nach anderen, bis du für dich "klickst".Die respektierten Lehrbücher in CS werden aus einem bestimmten Grund respektiert: Ihre Erklärungen sind ausgezeichnet. Corman and Rivest ist ein beliebter Favorit.
Zunächst sollten Sie genauer auf Ihre Frage eingehen. Geben Sie an, was Sie wissen, was Sie nicht tun und was Sie versucht haben.
Kommen wir zur Frage, TreeMap und Rot-Schwarz-Bäume sind völlig unterschiedliche Konzepte. Das konzeptionelle Verständnis von beiden ist überhaupt nicht abhängig von dem anderen und ich schlage vor, dass Sie sie nicht verwechseln. Ich werde Ihnen nicht die genaue Antwort geben, sondern vielmehr einen kurzen Überblick über die Konzepte und die Reihenfolge, in der Sie sie lernen müssen (IMO).
Die Karte Datenstrukturen
Die Baumdatenstrukturen
ich Sie kennen das Konzept der Karten und Binary Search Trees gehe davon aus. Wenn nicht, führt eine einfache Suche zu vielen guten Ressourcen.
Jetzt zur tatsächlichen Antwort.
Zuerst sollten Sie wissen, was SortedMap und Self-Balancing BST sind.
Was ist eine SorteMap?
Von Java docs,
Eine Karte, die eine totale Ordnung auf seine Schlüssel liefert weiter. Die Map wird nach der natürlichen Reihenfolge ihrer Schlüssel oder nach einem Comparator angeordnet, der normalerweise zum Zeitpunkt der sortierten Kartenerstellung bereitgestellt wird.
Eine SortedMap wird verwendet, wenn der zugrunde liegende Schlüssel, Wertepaare (nach Schlüssel) sortiert werden sollen. Auf diese Weise wäre es einfacher, die minimalen, maximalen oder bereichsbasierten Operationen abzurufen.
Was ist ein selbstbalancierender binärer Suchbaum?
Von wikipedia,
einem selbstausgleich (oder höhen balanced) binärer Suchbaum ist jeder Knoten basierte binärer Suchbaum, der seine Höhe (maximale Anzahl der Ebenen unter dem Wurzel) automatisch hält kleine angesichts willkürlicher Eintragungen und Löschungen von Elementen.
Wieder rot-schwarzer Baum in einer Implementierung von Self-Balancing BST.Es gibt others wie ALV-Baum, usw. Der schlechteste Fall für irgendeine Operation auf einer normalen BST ist O(n). Der Hauptvorteil der Verwendung von Balanced BST gegenüber normalem/nicht-symmetrischem BST besteht darin, dass der schlechteste Fall aller Operationen auf mit nur einem geringen Overhead reduziert wird, der mit der Neuanordnung der Knoten beim Einfügen/Löschen verbunden ist. Schauen Sie sich this an.
Also, was ist eine TreeMap?
Eine TreeMap ist eine Implementierung von SortedMap.
Wie sind die TreeMap und der rot-schwarze Baum?
Nein, sind sie nicht. Theoretisch können Sie einen der Binärsuchbäume zum Implementieren einer TreeMap verwenden. Um gute Ergebnisse zu erzielen, verwenden wir selbstabgleichende binäre Suchbäume, die eine geringere zeitliche Komplexität für das Einfügen, Löschen und Abrufen von Operationen aufweisen. Im Fall von Java wird Rot-Schwarz-Baum verwendet. Ich kenne den genauen Grund nicht, warum Rot-schwarzer Baum verwendet wird, aber ich glaube, dass es einen gibt.