Sind doppelte Schlüssel in der Definition von binären Suchbäumen erlaubt?

Question

Ich versuche die Definition eines binären Suchbaums zu finden und finde immer wieder andere Definitionen.

Einige sagen, dass für jeden gegebenen Teilbaum der linke Kindschlüssel kleiner oder gleich dem Stamm ist.

Einige sagen, dass für jeden gegebenen Teilbaum der rechte Kindschlüssel größer als oder gleich der Wurzel ist.

Und meine alten College Datenstrukturen Buch sagt "jedes Element hat einen Schlüssel und keine zwei Elemente haben den gleichen Schlüssel."

Gibt es eine universelle Definition eines bst? Vor allem in Bezug auf Bäume mit mehreren Instanzen des gleichen Schlüssels.

EDIT: Vielleicht, ich war nicht klar, die Definitionen ich sehe, sie sind

1) links < = root < rechts

2) links < Wurzel < = rechts

3) links < root < rechts, so dass keine doppelten Schlüssel existieren.

Answer 1

Jede Definition ist gültig. Solange Sie in Ihrer Implementierung konsistent sind (setzen Sie immer die gleichen Knoten nach rechts, legen Sie sie immer nach links, oder lassen Sie sie niemals zu), dann geht es Ihnen gut. Ich denke, es ist am üblichsten, sie nicht zuzulassen, aber es ist immer noch ein BST, wenn sie erlaubt sind und entweder links oder rechts platzieren.

Answer 2

Diese drei Dinge, die Sie gesagt haben, sind alle wahr.

• Keys sind einzigartig
• Auf der linken Seite sind der Schlüssel weniger als diese
• Auf der rechten Seite sind Tasten größer als diese

Ich nehme an, Sie Ihren Baum umkehren könnte und setzen die kleineren Tasten rechts, aber das "linke" und "rechte" Konzept ist genau das: ein visuelles Konzept, das uns hilft, über eine Datenstruktur nachzudenken, die nicht wirklich links oder rechts ist, also spielt es keine Rolle.

Answer 3

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 abfallen, größer als (oder gleich) dem Knotenwert ^(a).

Einige BSTs können doppelte Werte zulassen, daher die oben genannten Qualifikationsmerkmale "oder gleich".

Das folgende Beispiel verdeutlichen kann:

  | 
     +--- 14 ---+ 
     |   | 
+--- 13 +--- 22 ---+ 
|   |   | 
1   16 +--- 29 ---+ 
       |   | 
       28   29 

Dies ein BST zeigt, die Duplikate erlaubt - Sie, dass einen Wert zu finden, sehen Sie am Wurzelknoten starten und je den linken oder rechten Unterbaum nach unten geht auf ob Ihr Suchwert kleiner oder größer als der Knotenwert ist.

def hasVal (node, srchval): 
    if node == NULL: 
     return false 
    if node.val == srchval: 
     return true 
    if node.val > srchval: 
     return hasVal (node.left, srchval) 
    return hasVal (node.right, srchval) 

und mit Aufruf:

Dies kann rekursiv mit so etwas wie getan werden

foundIt = hasVal (rootNode, valToLookFor) 

Dubletten ein wenig Komplexität, da Sie suchen müssen halten, wenn Sie Ihre gefunden haben Wert für andere Knoten mit demselben Wert.

---

^(a) Sie könnte sie tatsächlich in der entgegengesetzten Richtung sortieren sollten Sie so vorgesehen wünschen, dass Sie einstellen, wie Sie nach einem bestimmten Schlüssel suchen. Ein BST muss nur eine sortierte Reihenfolge beibehalten, ob das aufsteigend oder absteigend nicht relevant ist.

Answer 4

Viele Algorithmen geben an, dass Duplikate ausgeschlossen sind. Zum Beispiel präsentieren die Beispielalgorithmen im MIT-Algorithms-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 links Kinder als < = und richtige Kinder als>. In der Praxis erfordert eine BST, die es erlaubt, dass entweder die rechten oder linken Kinder dem Wurzelknoten entsprechen, zusätzliche Rechenschritte, um eine Suche zu beenden, bei der doppelte Knoten zulässig sind.

Es empfiehlt sich, eine Liste am Knoten zu verwenden, um Duplikate zu speichern, da das Einfügen eines '=' - Wertes auf einer Seite eines Knotens den Baum auf dieser Seite neu schreiben muss, um den Knoten als untergeordneten Knoten zu platzieren als Enkel platziert, irgendwann unterhalb, was einige der Effizienz der Suche beseitigt.

Sie müssen sich daran erinnern, dass die meisten Klassenbeispiele vereinfacht dargestellt werden und das Konzept liefern. Sie sind in vielen realen Situationen nicht wert. Aber die Aussage "Jedes Element hat einen Schlüssel und keine zwei Elemente haben den gleichen Schlüssel" wird nicht durch die Verwendung einer Liste am Elementknoten verletzt.

Also gehen Sie mit, was Ihre Datenstrukturen Buch gesagt!

Edit:

Universal-Definition eines binären Suchbaum beinhaltet die Speicherung und für einen Schlüssel suchen eine Datenstruktur in eine von zwei Richtungen, basierend auf durchquert. Im pragmatischen Sinn, dh wenn der Wert <> ist, durchlaufen Sie die Datenstruktur in einer von zwei "Richtungen". In diesem Sinne ergeben doppelte Werte überhaupt keinen Sinn.

Dies unterscheidet sich von BSP oder binäre Suchpartition, aber nicht so unterschiedlich. Der Suchalgorithmus hat eine von zwei Richtungen für "Reisen" oder ist erfolgreich oder nicht erfolgreich. Daher entschuldige ich mich, dass meine ursprüngliche Antwort das Konzept einer "universellen Definition" nicht behandelt hat, da Duplikate wirklich ein Unterschied sind Thema (etwas, das Sie mit nach einer erfolgreichen Suche beschäftigen, der binären Suche nicht als Teil.)

Answer 5

1.) links < = root < rechts

2.) links < Wurzel < = rechts

3.) links < root < rechts, so dass keine doppelten Schlüssel exi st.

Ich muss gehen und meine Algorithmen Bücher ausgraben, aber von der Spitze meines Kopfes (3) ist die kanonische Form.

(1) oder (2) nur dann, wenn Sie beginnen, Duplikate Knoten und Sie setzen doppelten Knoten im Baum selbst (anstelle der Knoten enthält eine Liste) zu ermöglichen.

Answer 6

Wenn Ihr binärer Suchbaum ein rot-schwarzer Baum ist oder Sie beabsichtigen, irgendeine Art von "Baumrotation" -Operationen durchzuführen, verursachen doppelte Knoten Probleme. Stellen Sie sich vor Ihrem Baum Regel ist dies:

links < Wurzel < = rechts

nun einen einfachen Baum vorstellen, deren Wurzel 5, linkes Kind ist gleich Null, und die rechte Kind ist 5. Wenn Sie eine Linksdrehung auf das tun Wurzel endet mit einer 5 im linken Kind und einer 5 in der Wurzel, wobei das rechte Kind Null ist. Nun ist etwas im linken Baum gleich der Wurzel, aber Ihre Regel oben links < root.

Ich verbrachte Stunden damit herauszufinden, warum meine rot/schwarzen Bäume gelegentlich außer Betrieb gehen, das Problem war, was ich oben beschrieben habe. Hoffentlich liest jemand dies und spart sich stundenlanges Debugging in der Zukunft!

Answer 7

Arbeiten an einem rot-schwarzen Baum-Implementierung war ich Probleme Validierung der Baum mit mehreren Schlüsseln bekommen, bis ich mit dem rot-schwarzen Einsatz Drehung erkannt, dass, müssen Sie die Einschränkung

left <= root <= right

lockern Da keine der Dokumentationen, die ich betrachtete, doppelte Schlüssel erlaubte und ich die Rotationsmethoden nicht umschreiben wollte, um sie zu berücksichtigen, entschied ich mich, meine Knoten so zu modifizieren, dass mehrere Werte innerhalb des Knotens und keine doppelten Schlüssel möglich waren der Baum.

Answer 8

Die Elemente Reihenfolge < = ist ein total order so muss die Beziehung reflexiv sein, aber in der Regel ein binärer Suchbaum (alias BST) ist ein Baum ohne Duplikate.

Andernfalls, wenn es Duplikate gibt, müssen Sie zweimal oder mehr die gleiche Funktion des Löschens ausführen!

Answer 9

Doppelte Schlüssel • Was passiert, wenn mehr als ein Datenelement mit denselben Schlüssel enthält? - Dies ist ein kleines Problem bei rot-schwarzen Bäumen. - Es ist wichtig, dass Knoten mit demselben Schlüssel unter auf beiden Seiten anderer Knoten mit demselben Schlüssel verteilt sind. - Wenn die Schlüssel in der Reihenfolge 50, 50, 50, ankommen, • möchten Sie, dass die zweite 50 nach rechts von der ersten und die dritte 50 nach links von der ersten gehen. • Andernfalls wird der Baum unausgeglichen. • Dies könnte durch einen zufälligen Prozess im Einfügealgorithmus erfolgen. - Der Suchvorgang wird dann jedoch komplizierter, wenn alle Artikel mit dem gleichen Schlüssel gefunden werden müssen. • Es ist einfacher, Gegenstände mit demselben Schlüssel zu verbieten. - In dieser Diskussion nehmen wir an, dass Duplikate nicht erlaubt sind

Man kann eine verknüpfte Liste für jeden Knoten der Struktur erstellen, die doppelte Schlüssel enthält und Daten in der Liste speichert.

Answer 10

Alle drei Definitionen sind akzeptabel und korrekt. Sie definieren verschiedene Variationen eines BST.

Das Buch Ihrer Universitätsdatenstruktur konnte nicht klarstellen, dass seine Definition nicht die einzig mögliche war.

Sicherlich erlaubt das Hinzufügen von Duplikaten Komplexität. Wenn Sie die Definition verwenden „links < = root < rechts“ und Sie haben ein Baum wie:

 3 
    / \ 
    2  4 

dann das Hinzufügen einer „3“ doppelten Schlüssel zu diesem Baum in resultieren:

 3 
    / \ 
    2  4 
    \ 
    3 

Hinweis dass die Duplikate nicht zusammenhängend sind. Dies ist ein großes Problem, wenn Duplikate in einer BST-Darstellung wie die obige zugelassen werden: Duplikate können durch eine beliebige Anzahl von Ebenen getrennt sein, so dass das Vorhandensein von Duplikaten nicht so einfach ist, wie das Suchen nach unmittelbaren Kindern eines Knotens.

Eine Möglichkeit, dieses Problem zu vermeiden, besteht darin, Duplikate nicht strukturell (als separate Knoten) darzustellen, sondern einen Zähler zu verwenden, der die Anzahl der Vorkommen des Schlüssels zählt. Im vorherigen Beispiel würde dann einen Baum wie:

 3(1) 
    / \ 
    2(1)  4(1) 

und nach dem Einsetzen der Duplikats Taste „3“ wird es,:

 3(2) 
    / \ 
    2(1)  4(1) 

Dies vereinfacht Lookup, das Entfernen und Einsetzen Operationen auf Kosten von einigen zusätzlichen Bytes und Zähleroperationen.

Answer 11

In dem Buch "Introduction to algorithms", dritte Ausgabe, von Cormen, Leiserson, Rivest und Stein, ist ein binärer Suchbaum (BST) explizit als erlaubt Duplikate.

„Die Schlüssel in einem binären Suchbaum in einer solchen Art und Weise werden immer als die binary-Suchbaum-Eigenschaft erfüllen gespeichert: Dies kann in Abbildung 12.1 und die folgenden (Seite 287) zu sehen Let x sein ein Knoten in einem binären Suchbaum. Wenn y ein Knoten in dem linken Teilbaum von x ist, dann y:key <= x:key. Wenn y ein Knoten in dem rechten Teilbaum von x ist, dann y:key >= x:key.

Zusätzlich ist ein rot-schwarz Baum wird dann definiert auf Seite 308 als:

„A Rot-Schwarz-Baum ist ein binärer Suchbaum mit einem zusätzlichen Bit Speicherplatz pro Knoten: seine Farbe "

Daher unterstützen Rot-Schwarz-Bäume, die in diesem Buch definiert sind, Duplikate.