Queue vergleich mit binär Baum

[Lotus]

Hallo, ich schreibe demnächst eine Klausur in Informatik

Bin nun allerdings mal auf eine Frage gestoßen und hoffe ihr könnt mir mal helfen

Ich würde gerne die Arbeitsweisen der beiden (Queue und binär Baum) vergleichen, bzw. will das meine Lehrerin ;)

Ich weiß das der binärbaum sehr effektiv ist, allerdings weiß ich a) nicht wie effektiv, ich glaube das zeitverhältnis war t~log n, aber das sagt mir leider nicht viel..

könntet ihr mir paar tipps geben was man zu den beiden arbeitsweisen sagen könnte?

vielen dank Lotus

[Laufi]

Hallo!

Also ein Baum kann vielmehr als eine Queue! Eine Queeu kann nur einfügen und das letzte element lesen oder wieder wegnehmen dafür geht das ohne verzögerung. Beim Baum kannst du einfügen und löschen über den logarithmus aber das ist auch fast ohne verzögerung. Wichtig ist dass du auch ein element suchen kannst über den logarithmus und das ist ein grosser vorteil! :)

Liebe Grüsse
Laufi

[mkinzler]

Eine Warteschlange entspricht dem sequentiellen Suchen; ein Binärbaum der Binärsuche.

[alzaimar]

Zitat:

Zitat von mkinzler

Eine Warteschlange entspricht dem sequentiellen Suchen; ein Binärbaum der Binärsuche.

In einer Warteschlange soll man nicht suchen (können). Sie unterstützt per definitionem nur die Operationen 'Einfügen','IstLeer' und 'Abholen'.

Ich persönlich finde es blödsinnig, eine Queue mit einem Binärbaum zu vergleichen. Das ist ja so, als ob man einen Golfball mit einem Blumenstrauß vergleichen soll.

Eine Queue implementiert einen FIFO-Speicher (First In, First Out). Man stopft was rein, und wenn man ein Element abholt, kommen die Elemente in genau der Reihenfolge raus, wie sie reingestopft wurden. Das ist mit einem Rohr vergleichbar, in das man oben Kugeln reinpackt und unten eine Klappe hat, um jeweils die nächste Kugel zu holen.

[mkinzler]

Ich vermute mal er meinte eine Liste

[alzaimar]

Muss wohl.

[Lotus]

nun ja, ich habe auf dem zettel noch mal raufgeschaut, und da stand definitv ich solle die arbeitsweisen von queue und binär baum.. ich finds auch nich gerade sinnvoll und mir kam nich gerade originelle ideen dabei heraus deswegen wollte ich mal euch fragen! an sich is das jetzt was ihr geschrieben habt denke ich auch alles was man dazu sagen kann! lediglich das suchen eines elementes und löschen eines elementes kann man sofort erledigen

ich danke euch =)

ich denke das selbe trifft auch auf stack zu, schließlich ist das nur ne einfach verkettete liste

[mkinzler]

Queue: Verkette Liste FIFO
Stack: Verkette Liste LIFO

[alzaimar]

Eine Queue bzw. Stack hat aber nun gar nichts mit verketteten Listen zu tun. Es handelt sich um abstrakte Container mit einer bestimmten Funktionalität. Wie man das implementiert, bleibt jedem selbst überlassen. Der CPU-Stack beispielsweise ist alles andere als eine verkettete Liste. Sehr wohl sind verkettete Liste eine(!) mögliche (und auch sinnvolle) Implementierung für eine Queue.

Hier ist auch der fundamentale Unterschied: Während die Queue einen Container mit einer bestimmten Funktionalität bezeichnet, ist ein binärer Baum eine konkrete Datenstruktur zur Implementierung eines Containers 'Suchen, Finden und sortiert ausgeben'. So einen Container kann man mit einem binären Baum, einer sortierten Liste, einer Skipliste, einer verketteten Liste oder wie man lustig ist implementieren.