Diskussion:Suchbaum

Operationen delete

Ich glaube, das ist so nicht ganz richtig. Selbst bei einem ausbalancierten Baum kommt man beim Entfernen nur dann auf eine Komplexität von O(log n), wenn man den rechten Teilbaum am linken unteren Ende beispielsweise anhängt und den linken Teilbaum eine Ebene nach oben rutschen lässt. Im Normalfall ist dann aber der Baum danach unbalanced, so dass diese Annahme schon für den zweiten delete-Vorgang nicht mehr gilt und all die anderen Fälle nicht mehr abgedeckt sind. Ist der Baum aber unbalanced, so kommt man ja auch nicht auf O(log n), d.h. die Komplexität, die hier dargestellt ist, trifft nur in einem einzigen Spezialfall zu. Wäre es dann nicht besser, den allgemeinen Fall zu nehmen und den Baum eben umzusortieren (d.h. Unterscheidung, ob Blatt oder Knoten entfernt werden sollen und Angabe der Komplexität in Abhängigkeit davon)? Wäre für mich logischer... Grüße --Flash1984 21:00, 10. Sep. 2007 (CEST)

kleine Ergänzung: siehe auch hier --Flash1984 21:06, 10. Sep. 2007 (CEST)

Lieber Flash1984, pro Stufe ist die Mächtigkeit einer Ebene bei einem balancierten Baum um einen Faktor ∈ (1,2] größer als der höheren Ebene. D.h. bspw. die Wahrscheinlichkeit, dass man sich in der Nähe der Blätter befindet, ist etwa so groß wie die, das man sich im Rest des Baums befindet. Somit kommt man beim delete im Mittel auf eine Komplexität O(1) und im worst case auf O(log(n)). -- Nomen4Omen 11:05, 10. Jan. 2012 (CET)

Link hinzugefügt

Hallo,

ich hab eine Seite im Internet gefunden, die ein Suchbaum zur Fakultäterrechnung ausführlich beschreibt. Eien Powerpoint-Präsentation gibts dazu auch. http://www.philipphauer.de/info/info/fakultaet-prolog-suchbaum/#loesungssuche_als_suchbaum Fand ich gut und habs hinzugefügt.

Was meint ihr? Ist jemand anderer Meinung? Haui!

Nun gut, Suchen finde ich bei der Fakultät nicht wirklich angebracht. Was kann man nicht alles im Leben suchen? nfu -- Nomen4Omen 19:44, 11. Jan. 2012 (CET)

In-, Pre-, postorder ?

Ist denn ein suchbaum immer Postorder ? Kann der nicht auch mal Preorder sein ? 84.191.187.10 15:45, 28. Okt. 2007 (CET)

Wo steht denn da was von Postorder? --Flash1984 20:20, 28. Okt. 2007 (CET)

Das Interessante beim Suchbaum ist (fast) allein die In-order. Sie ist die Ordnungsrelation, die die Intervallschachtelung ermöglicht. -- Nomen4Omen 19:47, 11. Jan. 2012 (CET)

allgemeine Erklärung

Warum steht nirgends in dem Artikel, was ein Suchbaum überhaupt ist bzw. welche Eigenschaft jeder Knoten hat? (rechter Nachfolger größer, linker Nachfolger kleiner)

Korrekturen (noch bei der alten Suchbaum-Komplexität)

1. Das Subskript am Logarithmus ist gemeinhin die Basis des Logarithmus, die hier nicht gemeint ist. Die Basis bringt am Logarithmus eh nur einen konstanten Faktor bei, der bei der O-Notation sowieso ignoriert wird.
2. Das Balancieren sollte eine rein implizite Operation sein, die für den Anwender unbemerkt abläuft. Der Aufwand dafür ist in die expliziten Schnittstellen eingerechnet.
3. Das Einfügen und Löschen kann auch nach Operationen ≠ Suchen vorkommen. Deshalb sollte man ihren Aufwand ohne das Suchen rechnen, denn das Suchen draufaddieren sollte schließlich jeder selber können.
4. Der Begriff Speicherverbrauch wurde präzisiert.

Suchbaum-Komplexität wurde hierein integriert und kann m.E. verschwinden. -- Nomen4Omen 19:42, 11. Jan. 2012 (CET)

Laufzeitkomplexität

Die mittleren Laufzeiten von Traversieren, Einfügen, Löschen bei Rot-Schwarz-Baum, Splay-Baum, 2-3-4-Baum, B-Baum wäre zu überprüfen! -- Nomen4Omen 19:53, 11. Jan. 2012 (CET)

Ternärer Suchbaum

@Maximum 2520: Du hast Anfang des Jahres einen Abschnitt über den "Ternären Suchbaum" eingebracht. Leider verstehe ich aus der Beschreibung überhaupt nicht, was der "Ternäre Suchbaum" ist und wie er funktioniert. Denn wenn ich die Aussage "der 3 Knoten haben kann" ernst nehme, dann kann in ihm nicht besonders viel untergebracht werden: nämlich maximal 3(!?) Objekte – für sowas lohnt sich ein extra WP-Abschnitt eigentlich nicht.
Außerdem sehe ich keinerlei Literatur, so dass ich auch dort nix nachgucken kann. Wenn das so bleibt, muss der Abschnitt weg. –Nomen4Omen (Diskussion) 17:33, 20. Sep. 2020 (CEST)

Hallo Nomen4Omen, den Abschnitt hab ich aus https://en.wikipedia.org/wiki/Search_tree#Ternary_search_tree übernommen. Dort gibt es auch keine Belege. Grüße--Maximum 2520 (Diskussion) 21:43, 20. Sep. 2020 (CEST)

@Maximum 2520: Aha!
Du meinst vllt sogar den Artikel en:Ternary search tree, der durchaus einige Quellen angibt. Aber einen riesigen Disclaimer am Anfang stehen hat.
Schon in en:Search_tree#Ternary_search_tree ist zu erkennen, dass es sich bei den 3 Knoten um 3 Kindknoten handelt (lo kid, equal kid, hi kid). Das hätte schon recht viel geholfen.
Von einem "einzelnes Zeichen" kommt überhaupt nix. Da hast du möglicherweise etwas völlig falsch verstanden: "um zu testen, ob ein Pfad eine Zeichenfolge enthält"??.
Ich möchte dich eindringlich um Nachbesserung bitten. –Nomen4Omen (Diskussion) 22:46, 20. Sep. 2020 (CEST)

Hallo Nomen4Omen, ich hab den Abschnitt ergänzt, eine Abbildung und einen Einzelnachweis hinzugefügt. Ich hoffe, das passt jetzt. Grüße--Maximum 2520 (Diskussion) 19:54, 21. Sep. 2020 (CEST)