Viele Algorithmen geben an, dass Duplikate ausgeschlossen sind. Beispielsweise enthalten die Beispielalgorithmen im MIT-Algorithmus-Buch normalerweise Beispiele ohne Duplikate. Es ist ziemlich trivial, Duplikate zu implementieren (entweder als Liste am Knoten oder in einer bestimmten Richtung).
Die meisten (die ich gesehen habe) geben linke Kinder als <= und rechte Kinder als> an. In der Praxis erfordert eine BST, bei der entweder das rechte oder das linke Kind dem Stammknoten entspricht, zusätzliche Rechenschritte, um eine Suche abzuschließen, bei der doppelte Knoten zulässig sind.
Es ist am besten, eine Liste am Knoten zum Speichern von Duplikaten zu verwenden, da zum Einfügen eines '=' - Werts auf einer Seite eines Knotens der Baum auf dieser Seite neu geschrieben werden muss, um den Knoten als untergeordnetes Element zu platzieren, oder wenn der Knoten als Grand platziert wird -Kind, irgendwann unten, wodurch ein Teil der Sucheffizienz beseitigt wird.
Sie müssen sich daran erinnern, dass die meisten Beispiele im Klassenzimmer vereinfacht sind, um das Konzept darzustellen und zu liefern. In vielen realen Situationen sind sie es nicht wert, in die Hocke zu gehen. Die Aussage "Jedes Element hat einen Schlüssel und keine zwei Elemente haben den gleichen Schlüssel" wird jedoch nicht durch die Verwendung einer Liste am Elementknoten verletzt.
Gehen Sie also zu dem, was in Ihrem Datenstrukturbuch steht!
Bearbeiten:
Die universelle Definition eines binären Suchbaums umfasst das Speichern und Suchen eines Schlüssels basierend auf dem Durchlaufen einer Datenstruktur in eine von zwei Richtungen. Im pragmatischen Sinne bedeutet dies, dass Sie bei einem Wert von <> die Datenstruktur in eine von zwei 'Richtungen' durchlaufen. In diesem Sinne ergeben doppelte Werte überhaupt keinen Sinn.
Dies unterscheidet sich von BSP oder der binären Suchpartition, ist aber nicht allzu unterschiedlich. Der zu suchende Algorithmus hat eine von zwei Richtungen für "Reisen" oder er wird durchgeführt (erfolgreich oder nicht). Ich entschuldige mich, dass meine ursprüngliche Antwort nicht das Konzept einer "universellen Definition" angesprochen hat, da Duplikate wirklich unterschiedlich sind Thema (etwas, mit dem Sie sich nach einer erfolgreichen Suche befassen, nicht als Teil der binären Suche.)
Wenn Ihr binärer Suchbaum ein rot-schwarzer Baum ist oder Sie beabsichtigen, eine "Baumrotation" durchzuführen, verursachen doppelte Knoten Probleme. Stellen Sie sich vor, Ihre Baumregel lautet wie folgt:
left <root <= right
Stellen Sie sich nun einen einfachen Baum vor, dessen Wurzel 5 ist, dessen linkes Kind Null ist und dessen rechtes Kind 5 ist. Wenn Sie die Wurzel nach links drehen, erhalten Sie eine 5 im linken Kind und eine 5 in der Wurzel mit dem rechten Kind Null sein. Jetzt ist etwas im linken Baum gleich der Wurzel, aber Ihre obige Regel hat links <Wurzel angenommen.
Ich habe stundenlang versucht herauszufinden, warum meine rot / schwarzen Bäume gelegentlich nicht in Ordnung sind. Das Problem war das, was ich oben beschrieben habe. Hoffentlich liest jemand dies und erspart sich in Zukunft stundenlanges Debuggen!
quelle
left <= node <= right
oder erst vor dem ersten Auftreten eines Werts einzufügen .Alle drei Definitionen sind akzeptabel und korrekt. Sie definieren verschiedene Variationen einer BST.
Das Buch Ihrer College-Datenstruktur konnte nicht klarstellen, dass seine Definition nicht die einzig mögliche war.
Das Zulassen von Duplikaten erhöht natürlich die Komplexität. Wenn Sie die Definition "left <= root <right" verwenden und einen Baum haben wie:
Wenn Sie diesem Baum dann einen doppelten Schlüssel "3" hinzufügen, erhalten Sie Folgendes:
Beachten Sie, dass sich die Duplikate nicht in zusammenhängenden Ebenen befinden.
Dies ist ein großes Problem, wenn Duplikate in einer BST-Darstellung wie oben zugelassen werden: Duplikate können durch eine beliebige Anzahl von Ebenen getrennt werden. Daher ist die Überprüfung der Existenz von Duplikaten nicht so einfach wie die Überprüfung auf unmittelbare untergeordnete Elemente eines Knotens.
Eine Option, um dieses Problem zu vermeiden, besteht darin, Duplikate nicht strukturell (als separate Knoten) darzustellen, sondern stattdessen einen Zähler zu verwenden, der die Anzahl der Vorkommen des Schlüssels zählt. Das vorherige Beispiel hätte dann einen Baum wie:
und nach dem Einfügen des doppelten Schlüssels "3" wird es:
Dies vereinfacht Such-, Entfernungs- und Einfügevorgänge auf Kosten einiger zusätzlicher Bytes und Zähleroperationen.
quelle
In einer BST sind alle Werte, die auf der linken Seite eines Knotens absteigen, kleiner als (oder gleich, siehe später) der Knoten selbst. In ähnlicher Weise sind alle Werte, die auf der rechten Seite eines Knotens absteigen, größer (oder gleich) dem Knotenwert (a) .
Einige BSTs lassen möglicherweise doppelte Werte zu, daher die oben genannten Qualifikationsmerkmale "oder gleich".
Das folgende Beispiel kann klarstellen:
Dies zeigt eine BST, die Duplikate zulässt. Sie können sehen, dass Sie zum Suchen eines Werts am Stammknoten beginnen und den linken oder rechten Teilbaum nach unten gehen, je nachdem, ob Ihr Suchwert kleiner oder größer als der Knotenwert ist.
Dies kann rekursiv erfolgen mit:
und nenne es mit:
Duplikate erhöhen die Komplexität, da Sie möglicherweise weiter suchen müssen, sobald Sie Ihren Wert für andere Knoten mit demselben Wert gefunden haben.
(a) Sie können sie tatsächlich in die entgegengesetzte Richtung sortieren, wenn Sie dies wünschen, vorausgesetzt, Sie passen an, wie Sie nach einem bestimmten Schlüssel suchen. Eine BST muss nur eine sortierte Reihenfolge beibehalten, unabhängig davon, ob diese aufsteigend oder absteigend ist, ist nicht relevant.
quelle
In dem Buch "Einführung in Algorithmen", dritte Ausgabe, von Cormen, Leiserson, Rivest und Stein, wird ein binärer Suchbaum (BST) explizit so definiert, dass Duplikate zulässig sind . Dies ist in Abbildung 12.1 und den folgenden Abschnitten (Seite 287) zu sehen:
Außerdem wird auf Seite 308 ein rot-schwarzer Baum definiert als:
Daher unterstützen in diesem Buch definierte rot-schwarze Bäume Duplikate.
quelle
Jede Definition ist gültig. Solange Sie in Ihrer Implementierung konsistent sind (setzen Sie immer gleiche Knoten nach rechts, setzen Sie sie immer nach links oder lassen Sie sie niemals zu), geht es Ihnen gut. Ich denke, es ist am häufigsten, sie nicht zuzulassen, aber es ist immer noch eine BST, wenn sie erlaubt sind und entweder links oder rechts platzieren.
quelle
Bei der Arbeit an einer Rot-Schwarz-Baum-Implementierung hatte ich Probleme beim Validieren des Baums mit mehreren Schlüsseln, bis mir klar wurde, dass Sie mit der Rot-Schwarz-Insert-Drehung die Einschränkung auf lockern müssen
left <= root <= right
Da in keiner der von mir betrachteten Dokumentationen doppelte Schlüssel zulässig waren und ich die Rotationsmethoden nicht neu schreiben wollte, um dies zu berücksichtigen, habe ich mich nur entschlossen, meine Knoten so zu ändern, dass mehrere Werte innerhalb des Knotens und keine doppelten Schlüssel berücksichtigt werden der Baum.
quelle
Diese drei Dinge, die Sie gesagt haben, sind alle wahr.
Ich nehme an, Sie könnten Ihren Baum umkehren und die kleineren Schlüssel rechts platzieren, aber das Konzept "links" und "rechts" ist genau das: ein visuelles Konzept, das uns hilft, über eine Datenstruktur nachzudenken, die eigentlich keine linke hat oder richtig, also spielt es keine Rolle.
quelle
Ich muss vielleicht meine Algorithmusbücher ausgraben, aber oben auf meinem Kopf (3) befindet sich die kanonische Form.
(1) oder (2) treten erst auf, wenn Sie doppelte Knoten zulassen und doppelte Knoten in den Baum selbst einfügen (und nicht den Knoten, der eine Liste enthält).
quelle
>=
. Das Ideal hängt von Ihren Anforderungen ab. Wenn Sie jedoch viele doppelte Werte haben und zulassen, dass die doppelten Werte in der Struktur vorhanden sind, kann Ihre bst linear sein - dh O (n).Doppelte Schlüssel • Was passiert, wenn mehr als ein Datenelement mit demselben Schlüssel vorhanden ist? - Dies ist ein kleines Problem bei rot-schwarzen Bäumen. - Es ist wichtig, dass Knoten mit demselben Schlüssel auf beiden Seiten anderer Knoten mit demselben Schlüssel verteilt sind. - Das heißt, wenn die Schlüssel in der Reihenfolge 50, 50, 50 eintreffen, • möchten Sie, dass die zweiten 50 rechts von der ersten und die dritten 50 links von der ersten stehen. • Andernfalls wird der Baum aus dem Gleichgewicht gebracht. • Dies könnte durch eine Art Randomisierungsprozess im Einfügealgorithmus behandelt werden. - Der Suchvorgang wird dann jedoch komplizierter, wenn alle Artikel mit demselben Schlüssel gefunden werden müssen. • Es ist einfacher, Gegenstände mit demselben Schlüssel zu verbieten. - In dieser Diskussion wird davon ausgegangen, dass Duplikate nicht zulässig sind
Sie können für jeden Knoten des Baums eine verknüpfte Liste erstellen, die doppelte Schlüssel enthält und Daten in der Liste speichert.
quelle
Ich möchte nur weitere Informationen zu der Antwort von @Robert Paulson hinzufügen.
Nehmen wir an, dass der Knoten Schlüssel und Daten enthält. Knoten mit demselben Schlüssel können also unterschiedliche Daten enthalten.
(Die Suche muss also alle Knoten mit demselben Schlüssel finden.)
1) & 2) funktioniert einwandfrei, wenn der Baum keine rotationsbezogenen Funktionen hat , um eine Schiefe zu verhindern.
Dieses Formular funktioniert jedoch nicht mit dem AVL-Baum oder dem Rot-Schwarz-Baum , da durch die Rotation das Prinzip gebrochen wird.
Und selbst wenn search () den Knoten mit dem Schlüssel findet, muss er für die Knoten mit doppeltem Schlüssel zum Blattknoten durchlaufen.
Zeitkomplexität für die Suche = Theta (logN)
3) funktioniert gut mit jeder Form von BST mit rotationsbezogenen Funktionen.
Aber die Suche wird O (n) dauern , was den Zweck der Verwendung von BST ruiniert.
Angenommen, wir haben den Baum wie folgt mit 3) Prinzipal.
Wenn wir in diesem Baum nach (12) suchen , obwohl wir 12 an der Wurzel gefunden haben, müssen wir sowohl das linke als auch das rechte Kind weiter suchen, um nach dem doppelten Schlüssel zu suchen.
Dies dauert O (n) Zeit, wie ich gesagt habe.
4) ist mein persönlicher Favorit. Angenommen, Geschwister bedeutet den Knoten mit demselben Schlüssel.
Wir können über Baum in unten wechseln.
Jetzt benötigt jede Suche O (logN), da wir keine untergeordneten Elemente für den doppelten Schlüssel durchlaufen müssen.
Und dieses Prinzip funktioniert auch gut mit AVL- oder RB-Bäumen .
quelle
Die Elementordnungsrelation <= ist eine Gesamtreihenfolge daher muss die Relation reflexiv sein, aber üblicherweise ist ein binärer Suchbaum (auch bekannt als BST) ein Baum ohne Duplikate.
Andernfalls müssen Sie bei Duplikaten zweimal oder öfter dieselbe Löschfunktion ausführen!
quelle