Diskussion:Binärer Suchbaum
Duplikate
BearbeitenWie ist das eigentlich mit Duplikaten in Binären Suchbäumen? Die verkomplizieren die Situation doch ziemlich, oder nicht? afaik gibt es da auch spezielle Invarianten dann, die definieren wie mit Duplikaten umgegangen werden soll. --Mike@experimentelles.org 16:33, 5. Aug 2006 (CEST)
Löschen (Ersatz durch InOrder-Nachfolger)
Bearbeitenlt. Artikel ist es als Löschoperation zulässig, den InOrder-Nachfolger für das zu löschende Element einzusetzen. Aber bei einem solchen Baum würde das Ersetzen von G durch J(den InOrder-Nachfolger) dazu führen, dass K "in der Luft hängt", und daher das Entfernen von J eine besondere Behandlung, evtl einen weiteren Aufruf der Löschfunktion erfordert:
S S
/ \ / \
(G) W J W
/ \ / \
D M D M
/ \ / \ / \ / \
B F J P B F K P
\
K
Es sollte meiner Meinung nach erwähnt werden, dass das austauschen alleine nicht reicht, denn der Inorder-Nachfolger kann im Allgemeinen noch einen Teilbaum als Kind haben.
--Deejaydarvin 13:21, 1. Mai 2005 (CEST)
Ich hab erstmal den Absatz geändert, weil die gleiche Information mehrmals unter verschiedenen Begriffen genannt wurde. Mir waren nur die Begriffe symmetrischer Vorgänger und Nachfolger geläufig, Inorder-Vorgänger/Nachfolger scheint jedoch (laut google...) häufiger verwendet zu werden. Wäre das evtl. einen neuen kurzen Artikel wert? Ich habs jetzt erstmal bei symmetrisch belassen und dein Beispiel mit eingefügt. Wenn jemand Zeit hat, könnte er ja die beiden Beispiel noch anpassen, so dass beim oberen Beispiel auch das K mit hängt und das Design gleich aussieht. --Samx 15:22, 27. Jul 2006 (CEST)
geändert: Komplexität im schlechtesten Fall
BearbeitenDer Artikel nennt (richtig) als Komplexität im schlechtesten Fall O(h), h Höhe des Baums. Allerdings ist der nächste Satz irreführend: „Der Baum ist in diesem Fall allerdings zu einer Liste entartet.“ Nein, die Laufzeit im schlechtesten Fall ist immer O(h).
Ich konnte auch nicht sehen, welcher spezielle Fall sonst gemeint ist und habe mir deshalb erlaubt, diesen Satz zu streichen und den folgenden Satz (der auf vollständig gefüllte Bäume und O(log n) verweist) um einen Hinweis auf balancierte Bäume zu ergänzen.
Außerdem unten im Artikel habe ich die Komplexität der Löschoperation ebenfalls korrigiert: O(h); erst balancierte Suchbäume ermöglichen eine Komplexität O(log n).
Pseudocode
Bearbeiten
Löschen( T, x )
knoten y knoten z 1 if x.left = NULL || x.right = NULL 2 theny = z 3 elsey = baumNextSuche ( T, x )
4 if y.left!NULL 5 then z = y.left 6 else z = y.right
7 if z!=NULL 8 then z.parent = y.parent
9 if y.parent = NULL 10 then T.root = z 11 else if y = y.parent.left 12 then y.parent.left = z 13 else y.parent.right = z 14 if y!x 15 then x.key = y.key;
Knoten löschen mit 2 Nachfolgern
Bearbeiten"Üblich ist es jedoch, den zu löschenden Knoten durch den symmetrischen Vorgänger oder Nachfolger zu ersetzen."
--> Dies stimmt so nicht. Laut der oben im Artikel genannten Konvention, dass der linke Kindknoten zwingend kleiner sein muss als der Vorgänger, kann es zu Komplikationen kommen, wenn der "symmetrische Vorgänger" eingesetzt wird.
2 / \ 1 3 / \ 0 1
Löscht man in diesem Fall die 2, haben wir laut Definition keinen Binären Suchbaum mehr, wenn der sym. Vorgänger eingesetzt wird.
--Mirko Schinck 19:35, 4. Jul. 2009 (CEST)
Knoten löschen mit 2 Nachfolgern
Bearbeitenhat ein Knoten zwei Nachfolger, wird er durch den Kindknoten (bzw Kind-Kind-...-Knoten) der sich auf der linken Seite des zu ersetzenden Knotens ganz rechts befindet ersetzt. Dann kann es auch nicht zu Komplikationen wegen der Größen kommen. (nicht signierter Beitrag von 78.42.27.76 (Diskussion | Beiträge) 23:13, 1. Sep. 2009 (CEST))
Einfügen in einen Suchbaum
BearbeitenDieser Abschnitt sollte mal überarbeitet werden. Die aktuelle Erklärung ist unvollständig und teils falsch. Außerdem ist das aktuelle Beispiel ohne zu wissen wie groß die Variablen sind, ziemlich nutzlos. Die englische Wikipedia liefert da einen wesentlich besseren Artikel: http://en.wiki.x.io/wiki/Binary_search_tree#Insertion --Eemux 17:09, 2. Jun. 2010 (CEST)
Änderungen am 2010-07-21:
Bearbeiten1) Suchen mit Duplikaten (gebracht, weil nicht bekannt bei Binarytreesort)
2) Suchen per Index rüber von AVL
3) Geglättet: Komplexität beim Suchen
Verstanden:
3a) zunächst nur Suchen
3b) dann aber doch (allem Anschein nach) der ganze Baum-Aufbau
3c) "best case" entspricht average und wird nur noch bei Sortierverfahren#Vergleichsbasiertes Sortieren gebracht
4) Proximitäts-Suche (statt GrößerGleichKleiner-Suche)
5) Einfügen, Löschen, Rotation im Wesentlichen rüber zu Binärbaum, da nicht Such-spezifisch
Höhe des binären Suchbaumes im Beispiel
BearbeitenLaut folgendem Wikipedia-Beitrag: http://de.wiki.x.io/wiki/Glossar_Graphentheorie#H.C3.B6he müsste die Höhe des Suchbaumes im Beispiel doch 4 sein (und nicht 5)? (nicht signierter Beitrag von 88.72.17.67 (Diskussion) 18:32, 30. Mär. 2011 (CEST))
- Dort steht aber auch im 2. Satz, dass viele Autoren 1 mehr (also die Zahl der Knoten) nehmen - mit Begründung.
- Ich bevorzuge diese Definition. -- Nomen4Omen 07:37, 31. Mär. 2011 (CEST)
- Danke für die schnelle Antwort (und die "Nachhilfe"). (nicht signierter Beitrag von 88.72.17.67 (Diskussion) 16:05, 31. Mär. 2011 (CEST))
Frage: Aus meiner Sicht müsste es nicht nur einen binären (zweiwertigen), sondern auch multiplen mehrwertigen Suchbaum geben, sofern es sich um einen booleschen Verband handelt. Wer könnte dazu etwas sagen/beitragen ? WilmjakobWilmjakob (Diskussion) 12:45, 3. Sep. 2013 (CEST)
Multipler Suchbaum
BearbeitenFrage: Aus meiner Sicht müsste es nicht nur einen binären (zweiwertigen), sondern auch multiplen (mehrwertigen) Suchbaum geben, sofern es sich um einen booleschen Verband handelt. Wer könnte dazu etwas sagen/beitragen ? WilmjakobWilmjakob (Diskussion) 12:48, 3. Sep. 2013 (CEST)
- Ein binärer Suchbaum ist ja keineswegs zweiwertig, sondern kann außerordentlich viele Werte beherbergen. Die Rangigkeit der Zweier-Verzweigung im binären Suchbaum ist für den Anwender eher marginal und hat fast nur Folgen hinsichtlich der Performanz.
- Natürlich gibt es auch Suchbäume, die nicht nur Zweier-, sondern auch größere Verzweigungen haben. Sie brauchen aber alle eine Totalordnung (also eine Art R1) und sind wegen der inhärenten Binärität der Vergleichsrelation etwas langsamer und etwas schwieriger zu implementieren. Siehe Suchbaum, dort insbesondere die Verweise 2-3-4-Baum, B-Baum etc.
- Richtig interessant ist aber die Frage nach effizientem Suchen im Rn. Sowas könnte mit dem »booleschen Verband« gemeint sein. Ein Beispiel könnte eine Datenbank sein, bei der ich Vermessungspunkte aufgrund von geographischer Länge, Breite und Höhe suchen kann. Es gibt hierzu einen Band von Kurt Mehlhorn: Mehrdimensionales Suchen und Algorithmische Geometrie. --Nomen4Omen (Diskussion) 16:16, 7. Sep. 2013 (CEST)
Vielen Dank für die Hinweise; da ich kein ausgebildeter Mathematiker bin, drücke ich mich nicht immer korrekt aus. Die Frage für mich ist, welche mathematischen Strukturen müssen den betrachtetetn Objekten zugrunde liegen, damit eine mehrwertige Verzweigung sinnvoll möglich ist. Dies ist n.m.K. bei den Untermengen einer idealen booleschen Mengenalgebra der Fall. Liege ich da richtig ?
- Wie oben erwähnt, sind Bäume mit einer Ordnung als Out-Tree > 2 möglich und beschrieben. Sicherlich sind sie auch sinnvoll. Sind es zusätzlich Suchbäume, so werden sie dies n.m.K. immer durch eine Totalordnung (genauer: eine totale Quasiordnung), wie im Artikel beschrieben, womit für den Anwender der Unterschied zu den binären Suchbäumen eher marginal wird. Im Artikel Verband (Mathematik) steht, dass eine solche Ordnungsrelation stets auch einen Verband etabliert. Verbände, die keine totale Quasiordnung sind, – wie eine Mengenalgebra – lassen sich sicherlich als Datenstrukturen darstellen. Ob der Out-Tree dafür das richtige Werkzeug ist, möchte ich eher bezweifeln, auch wenn er eine hohe Ordnung (sprich: »Mehrwertig«keit) hat. --Nomen4Omen (Diskussion) 12:15, 9. Sep. 2013 (CEST)