Binärer Baum vs. sortierte verkettete Liste

Ein binärer Baum (bzw. die optimierte AVL-Variante) hat ja eigentlich den Vorteil der schnelleren Suche (bzw. Einfügen) ggü. einer Liste.

Angenommen man baut eine Art Wrapper um eine verkette Liste, der garantiert, dass die Daten beim Einfügen gleich an die richitige Stelle geschrieben werden (also direkt einsortiert und nicht erst nachträglich durch Algorithmen wie QuickSort o.a.). Somit kann also die binäre Suche verwendet werden.

Welche Vorteile bietet dann ein binärer Baum ggü. einer solch verketteten Liste noch?
Vgl.

Op                  Binärer Baum             sort. verk. Liste

Suche               O(log n)                  O(log n)

Einfügen/Löschen    O(log n) bis ~ O(n)      ~O(log n) 
                    bei Reorganisation       (Reorg nicht notwendig, da nach der Suche ja nur 1 bis 2 Zeiger umgebogen werden müssen)

Hab ich da was übersehen oder steht die sort. verk. Liste tatsächlich so gut da?

audacia

Wie stellst du dir das binäre Suchen in einer verketteten Liste vor? Du mußt dich auch durch eine sortierte Liste erst durchhangeln.

Zeus

Du kannst bei eine Liste doch nur vom einem Knoten zum nächsten oder vorherigen iterieren.

Oh, habe grade den ersten Gedankenfehler entdeckt: Eine binäre Suche kann ja in einer sort. verk. Liste nicht so ohne weiteres (wie z.b. bei sort. Array) verwendet werden, da "die Mitte" eines Bereichs nicht direkt angesprungen werden kann.

Aber nehmen wir mal zus. an, dass der Wrapper ein paar Meta-Infos, wie Zeiger auf Element an 1/2*size, 1/4* bzw. 3/4*size, usw. hält (Anzahl der Sprung Zeiger abhängig von Größe). Das würde diesen zwar Speichertechnisch etwas aufblähen, allerdings hätte diese DS dann immer noch den Vorteil des durchschnittlich schnelleren Einfügens/Löschens ggü. dem binären Baum, oder? Nochmal überlegen...Mist beim Einfügen/Löschen müssen ja auch alle Sprung Zeiger upgedated werden, was den Vorteil wahrscheinlich wieder aufhebt. War wohl doch nix mit der Idee...

Edit: Ups, da waren zwei schneller...

Bashar

hansile schrieb:

Aber nehmen wir mal zus. an, dass der Wrapper ein paar Meta-Infos, wie Zeiger auf Element an 1/2*size, 1/4* bzw. 3/4*size, usw. hält (Anzahl der Sprung Zeiger abhängig von Größe).

Du meinst ungefähr so? http://de.wikipedia.org/wiki/Liste_(Datenstruktur)#Skip-Liste

Christoph

hansile schrieb:

Vgl.

Op                  Binärer Baum             sort. verk. Liste

Suche               O(log n)                  O(log n)

Einfügen/Löschen    O(log n) bis ~ O(n)      ~O(log n) 
                    bei Reorganisation       (Reorg nicht notwendig, da nach der Suche ja nur 1 bis 2 Zeiger umgebogen werden müssen)

Hab ich da was übersehen oder steht die sort. verk. Liste tatsächlich so gut da?

Einfuegen/Loeschen ist beim AVL-Baum O(log n) und nicht O(n), egal ob reorganisiert werden muss oder nicht.

Oh man, ich wäre echt mal froh, wenn mir meine Denkfehler VOR dem Absenden eines Beitrages auffallen würden.

@Bashar: Danke für den Link, da sind ja ganz nette Konzepte für verbesserte Listen zu finden. Interessant scheinen auch die adaptiven Listentypen. Weiß jemand ob/wo sowas Vorteile in der Praxis ggü. Bäumen bieten könnte?

Blue-Tiger

Wenn du N Zahlen in einen AVL-Baum einfuegen willst, ist das ~O(n log n). Insertionsort (den du bei der verketteten Liste machen muesstest) arbeitet allerdings in O(n^2).

Helium

Blue-Tiger schrieb:

Insertionsort (den du bei der verketteten Liste machen muesstest) arbeitet allerdings in O(n^2).

Ich will nicht wie beim sortieren der Liste n Elemente sondern nur ein Element einfügen. Wieso brauche ich O(n^2) und nicht O(n)?

Jester

Helium schrieb:

Blue-Tiger schrieb:

Insertionsort (den du bei der verketteten Liste machen muesstest) arbeitet allerdings in O(n^2).

Ich will nicht wie beim sortieren der Liste n Elemente sondern nur ein Element einfügen. Wieso brauche ich O(n^2) und nicht O(n)?

Brauchst Du nicht. Hat ja auch keiner behauptet.

Bashar

Es bleibt allerdings die Frage, warum man eine Liste mit Insertion Sort sortieren müssen sollte.

Jester

In der Tat... ich glaube er meinte naives eins nach dem anderen Einfügen, so dass es zu jedem zeitpunkt sortiert ist und dann von vorne bis hinten durchlaufen und ausgeben.

Blue-Tiger

Bashar schrieb:

Es bleibt allerdings die Frage, warum man eine Liste mit Insertion Sort sortieren müssen sollte.

Na ja, wenn man mehrere Elemente nacheinander in die Liste einfuegt, und die Liste gleich beim Einfuegen eines Elements geordnet sein soll, dann laeuft das doch auf Insertionsort raus.

Helium schrieb:

Blue-Tiger schrieb:

Insertionsort (den du bei der verketteten Liste machen muesstest) arbeitet allerdings in O(n^2).

Ich will nicht wie beim sortieren der Liste n Elemente sondern nur ein Element einfügen. Wieso brauche ich O(n^2) und nicht O(n)?

Wenn du fuer das Einfuegen von 1 Element O(n) brauchst, brauchst du fuer's Einfuegen von n Elementen O(n^2), das hab ich gemeint. Beim Baum wuerdest du fuer's Einfuegen von n Elementen nur O(n log n) brauchen.

Bashar

Achso. Ansonsten gäbs da ja z.B. Merge Sort.

wenn ich aber k elemente in eine n-elementige liste einfügen will, hab ich als aufwand doch k*n. und dann würd sich merge doch schon wieder nicht lohnen, bei kleinem k.

Jester

bei kleinen werten isses eh egal. für kleine n ist es auch wurscht ob liste, array oder baum.

Ben04

hansile schrieb:

Aber nehmen wir mal zus. an, dass der Wrapper ein paar Meta-Infos, wie Zeiger auf Element an 1/2*size, ...

Wenns du den Gedanken jetzt konkretisierst dann hast du einen Binär Baum.

Bashar schrieb:

Achso. Ansonsten gäbs da ja z.B. Merge Sort.

Um Merge Sort aber in O(n*log(n)) zu realisieren brauchst du einen zweiten Puffer. Dann kannst du aber auch gleich deine Liste in ein Array kopieren, XY Sort drauf loslassen und dann wieder in die Liste zurückkopieren.

Merge Sort kann man zwar auch ohne extra Puffer realisieren allerdings ist das dann nicht mehr O(n*log(n)). Ich bin mir jetzt nicht sicher wie das Verfahren genau ist aber im Sedgewick steht was zum Thema drin.

Desweiteren sehe ich nicht wie man Teile & Herrsche auf einer verketteten Liste machen sollte ohne noch mal zusätzlichen Speicher zu brauchen.

Heap Sort geht soweit ich das sehe auch nicht auf einer verketteten Liste.

Eigentlich eine interessante Frage : Gibt es ein Sortierverfahren mit einer Zeitkomplexität in O(n*log(n)) welches einfach verkettete Listen allgemeiner Werte sortiert ohne dabei zusätzlichen Speicher zu verwenden? ("allgemeiner Werte" damit keiner mit Bucket Sort ankommt und einfach verkettet da man bei doppelt verketteten Listen diese wahrscheinlich in einen binär Baum überführen kann und dann wieder zurück. Mit zwei Zeigern pro Knoten kann man ja ganz gut einen Baum basteln.)

Blue-Tiger

@Ben04:
MergeSort ist doch hervorragend dafuer geeignet, verkettete Listen inplace zu sortieren? (und das sehr wohl in O(n log n)

Aber warum reden wir hier eigentlich ueber Mergesort? Ich wollt mit meinem Kommentar nur drauf hinweisen dass das Einfuegen von neuen Elementen in die Liste mit der Forderung, die Liste zu jedem Zeitpunkt geordnet zu halten, auf Insertionsort hinauslaeuft. Und das ist auf Dauer nicht sehr effizient.

Jester

Zumindest wenn man von einer zufälligen gleichverteilten Eingabe ausgehen kann man listen auch mit quicksort in O(n log n) Zeit inplace sortieren. Mit Listen in-place arbeiten ist sowieso viel einfacher als mit Arrays.