Discussion:
[AVL-Baum] Average Case
(zu alt für eine Antwort)
Tarik Mustafic
2005-12-12 20:57:52 UTC
Permalink
Hallo allerseits,

Ich schreibe einen AVL-Baum, nichts spannendes, gibs halt viele Bücher
etc dazu, wo alles bestens erklärt ist.

Was mich aber interessiert ist, wie man bei den Grundoperationen im
AVL-Baum (Search,Insert, Delete) einen Average Case von O(1) erziehlt?

Mir würden paar "schriftliche" Gedanken vollkommen ausreichen.

Bedanke mich im Vorraus

tarik
Jochen Theodorou
2005-12-12 22:48:49 UTC
Permalink
Post by Tarik Mustafic
Hallo allerseits,
Ich schreibe einen AVL-Baum, nichts spannendes, gibs halt viele Bücher
etc dazu, wo alles bestens erklärt ist.
Was mich aber interessiert ist, wie man bei den Grundoperationen im
AVL-Baum (Search,Insert, Delete) einen Average Case von O(1) erziehlt?
Mir würden paar "schriftliche" Gedanken vollkommen ausreichen.
Bedanke mich im Vorraus
ähm... man muss immer einige Teile des Baumes durchgehen, dieses ist
Proportional zur Höhe des Baumes, also log(n). Wobei log(n) wäre es nur
wenn der Baum immer ein garantierter Binärbaum wäre, ein AVL-Baum ist
ein wenig höher. Im Durchschnitt ist ein AVL-Baum aber etwa gleich hoch.
Damit komme ich auf log(n) im Durchsnittlichen Fall und nicht O(1). Wenn
das anders wäre würde ein Sortieren mittels eines AVL-Baumes ja in O(n)
gehen, es gibt aber den Beweis dass kein auf binären Vergleichen
basierendes Sortierverfahren besser als n*log(n) (durchschnittlicher
Fall) arbeiten kann. Daher kann das mit O(1) nicht stimmen.

Gruss theo
Ernst Baumann
2005-12-13 18:53:22 UTC
Permalink
Post by Jochen Theodorou
....
Gruss theo
Hallo Theo,
Entschuldigung (auch an die anderen, die diesen Thread lesen), dass
ich dich versuche, auf diesem Weg zu kontaktieren, aber über deine
email-Adresse konnte ich dich auch nicht erreichen. Ich will nur
wissen, ob du meine Frage in dem Thread
"Unterschied Compiler / Interpreter mit und ohne JIT usw." noch
beantworten (***@4ax.com) wirst, oder
ob für dich diese Sache abgeschlossen ist. Es wäre vielleicht am
besten, wenn du mir eine email schickst an: ***@web.de

mfg (und Entschuldigung an alle)
Ernst
Sebastian Bächle
2005-12-13 21:34:49 UTC
Permalink
Post by Jochen Theodorou
...
wenn der Baum immer ein garantierter Binärbaum wäre, ein AVL-Baum ist
ein wenig höher. Im Durchschnitt ist ein AVL-Baum aber etwa gleich hoch.
...
Ich garantiere dir, dass ein AVL Baum ein Binärbaum ist! ;-)

Gruß,
Sebastian
Jochen Theodorou
2005-12-13 21:03:06 UTC
Permalink
Post by Sebastian Bächle
Post by Jochen Theodorou
...
wenn der Baum immer ein garantierter Binärbaum wäre, ein AVL-Baum ist
ein wenig höher. Im Durchschnitt ist ein AVL-Baum aber etwa gleich hoch.
...
Ich garantiere dir, dass ein AVL Baum ein Binärbaum ist! ;-)
ok, wass ich meinte ist ein Binärbaum, der auch vollständig ausgeglichen
ist. Der Begriff "garantierter Binärbaum" war natürlich der falsche
Begriff dafür.

Ein Baum ist genau dann ausgeglichen, wenn sich für jeden Knoten die
Höhen der zugehörigen Unterbäume um höchstens 1 unterscheiden. Das
heisst aber nicht das der Baum dann vollständig ausgeglichen ist. Die
Erfinder des AVL-Baumes konnten beweisen, dass solch ein Baum höchstens
45% höher ist als ein vollständig ausgeglichener Binärbaum.

Allerdings wären diese 45% Worst Case, der vollständig ausgeglichene
Baum geht in Richtung Best Case.

Gruss theo
Achim Peters
2005-12-14 14:26:35 UTC
Permalink
Post by Sebastian Bächle
Post by Jochen Theodorou
...
wenn der Baum immer ein garantierter Binärbaum wäre, ein AVL-Baum ist
ein wenig höher. Im Durchschnitt ist ein AVL-Baum aber etwa gleich hoch.
...
Ich garantiere dir, dass ein AVL Baum ein Binärbaum ist! ;-)
Sigh, das ist alles schon so lange her ... Aber ich dachte, ein
Binärbaum ist einer, wo jeder Knoten höchstens zwei Äste hat? Das ist
bei einem AVL-Baum doch durchaus keine Voraussetzung? Der mag zwar ein
B- oder B*-Baum sein, aber bekanntermaßen steht das B dabei ja nicht für
"Binär", sondern für Bayer.

Bye
Achim
Stefan Rybacki
2005-12-14 15:15:14 UTC
Permalink
Post by Achim Peters
Post by Sebastian Bächle
Post by Jochen Theodorou
...
wenn der Baum immer ein garantierter Binärbaum wäre, ein AVL-Baum ist
ein wenig höher. Im Durchschnitt ist ein AVL-Baum aber etwa gleich hoch.
...
Ich garantiere dir, dass ein AVL Baum ein Binärbaum ist! ;-)
Sigh, das ist alles schon so lange her ... Aber ich dachte, ein
Binärbaum ist einer, wo jeder Knoten höchstens zwei Äste hat? Das ist
bei einem AVL-Baum doch durchaus keine Voraussetzung?
Doch ist es. Ein AVL ist zusätzlich noch balanciert.
Post by Achim Peters
Der mag zwar ein
B- oder B*-Baum sein, aber bekanntermaßen steht das B dabei ja nicht für
"Binär", sondern für Bayer.
Korrekt, nur ist wie gesagt der AVL kein B-Baum.

Bis denn dann
Stefan
Post by Achim Peters
Bye
Achim
Jochen Theodorou
2005-12-14 15:24:08 UTC
Permalink
Stefan Rybacki schrieb:
[...]
Post by Stefan Rybacki
Post by Achim Peters
Post by Sebastian Bächle
Ich garantiere dir, dass ein AVL Baum ein Binärbaum ist! ;-)
Sigh, das ist alles schon so lange her ... Aber ich dachte, ein
Binärbaum ist einer, wo jeder Knoten höchstens zwei Äste hat? Das ist
bei einem AVL-Baum doch durchaus keine Voraussetzung?
Doch ist es. Ein AVL ist zusätzlich noch balanciert.
man könnte sicher auch einen AVL-Baum definieren, der mit mehr als 2
Kindbäumen auskommt. Allerdings würde dann wahrscheinlich sowas wie der
B-Baum dabei herauskommen.
Post by Stefan Rybacki
Post by Achim Peters
Der mag zwar ein
B- oder B*-Baum sein, aber bekanntermaßen steht das B dabei ja nicht für
"Binär", sondern für Bayer.
Korrekt, nur ist wie gesagt der AVL kein B-Baum.
als das mit dem "Bayer" ist auch nicht so sicher ;) Aus
http://de.wikipedia.org/wiki/B-Baum

"Die Erfinder lieferten keine Erklärung über die Herkunft des Namens
B-Baum. Die häufigste Interpretation ist, dass B für balanciert steht.
Weitere Interpretationen sind B für Bayer, Broad, Bushy, oder Boeing, da
Rudolf Bayer für Boeing Scientific Research Labs gearbeitet hat."

Gruss theo
Alexander Reifinger
2005-12-14 16:00:02 UTC
Permalink
Post by Jochen Theodorou
als das mit dem "Bayer" ist auch nicht so sicher ;) Aus
http://de.wikipedia.org/wiki/B-Baum
"Die Erfinder lieferten keine Erklärung über die Herkunft des Namens
B-Baum. Die häufigste Interpretation ist, dass B für balanciert steht.
Weitere Interpretationen sind B für Bayer, Broad, Bushy, oder Boeing, da
Rudolf Bayer für Boeing Scientific Research Labs gearbeitet hat."
Also mir hat er auf Nachfrage damals nichts gesagt sondern nur wissend
gegrinst...
--
Servus,
Alexander Reifinger
Jochen Theodorou
2005-12-14 17:30:13 UTC
Permalink
Post by Alexander Reifinger
Post by Jochen Theodorou
als das mit dem "Bayer" ist auch nicht so sicher ;) Aus
http://de.wikipedia.org/wiki/B-Baum
"Die Erfinder lieferten keine Erklärung über die Herkunft des Namens
B-Baum. Die häufigste Interpretation ist, dass B für balanciert steht.
Weitere Interpretationen sind B für Bayer, Broad, Bushy, oder Boeing,
da Rudolf Bayer für Boeing Scientific Research Labs gearbeitet hat."
Also mir hat er auf Nachfrage damals nichts gesagt sondern nur wissend
gegrinst...
hehe, ja, das macht er wohl gerne so ;)

Gruss theo
Steffen Heinisch
2005-12-12 23:06:00 UTC
Permalink
Post by Tarik Mustafic
Was mich aber interessiert ist, wie man bei den Grundoperationen im
AVL-Baum (Search,Insert, Delete) einen Average Case von O(1) erziehlt?
Ich glaub da könntest du in einer Newsgroup, die sich mit
Theoretischer Informatik beschäftigt mehr Chancen haben.

Aber hier mal mein (laienhafter) Senf dazu:

Der Bestcase eines binären Suchbaums ist ein Vollständiger Baum, d.h.
bei n=(2^i)-1 Knoten haben wir eine Tiefe von i (Wurzel = Tiefe 1).

Suchen wir nun dort ein Element benötigen wir im Mittel
(2^(i-1) * i + 2^(i-2) * (i-1) + 2^(i-3) * (i-2) + ... + 2^1*2 +
2^0 * 1) / ((2^i)-1) Vergleiche.
(In Worten: die 2^(i-1) Blätter benötigen je i Vergleiche, die 2^(i-2)
Vaterknoten der Blätter benötigen je i-1 Vergleiche ... die 2 Knoten
in Tiefe 2 benötigen je 2 Vergleiche, der Wurzelknoten benötigt einen
Vergleich. Das ganze dividieren wir durch die Anzahl Knoten um den
Mittelwert zu erhalten.)
Es kommt etwas mit O(i) heraus, also O(log(n)). Also halte ich(!) es
für unmöglich auf O(1) Average Case Suchaufwand zu kommen.

Beim Einfügen und Löschen kommt es jetzt darauf an, ob du schon weißt
wo du einfügst/löscht, oder ob du die stelle noch suchen musst. Gilt
letzteres sollte es auch unmöglich sein, da ja das Suchen schon
0(log(n)) Vergleiche benötigt.
Wie es ohne das Suchen aussieht weiß ich jetzt nicht. Im Worstcase
musst du da O(log(n)) mal rotieren, aber wie Average Case wird, ist
mir nicht klar.



Ich hoffe das war jetzt nicht jede Menge Stuss auf einem Haufen.

MfG Steffen.
Oliver Haupt
2005-12-13 07:28:42 UTC
Permalink
Post by Tarik Mustafic
Hallo allerseits,
Ich schreibe einen AVL-Baum, nichts spannendes, gibs halt viele Bücher
etc dazu, wo alles bestens erklärt ist.
Was mich aber interessiert ist, wie man bei den Grundoperationen im
AVL-Baum (Search,Insert, Delete) einen Average Case von O(1) erziehlt?
Indem Du eine andere Datenstruktur nimmst ;)

Dein Problem ist halt, dass (fast) alle Operationen o(log(n))
benoetigen, da dies die Tiefe deines Baumes ist.

Der einzige Vorteil eines AVL Baumes ist - wimre - , dass Du nicht im
Worst-Case eine Liste bekommst. Fuer diesen Vorteil zahlst Du aber
hoehere Kosten beim Einfuegen, wg. evtl. umstrukturierens.

Wenn Du bei sehr vielen Operationen O(1) moechtest, schau dir mal
B-Baeume an. Die Hoelle bei der Implementation, dafuer sind alle
interessanten Operationen in O(1).

Alles bitte mit einem Quentchen Salz, da meine Theo-Info Pruefung schon
ein Weilchen her ist.

... Ich hab mal bei Wiki nachgesehen - ein B-Baum ist leider nicht der,
den ich meinte - allerdings will mir der richtige Datentyp nicht
einfallen. Nichtsdestotrotz ist der B-Baum in der Paraxis schneller.

Da war was mit Kreisfoermigen Verweisen und in verschiedenen Ebenen
rotierenden Blaettern. Das ist aber auch alles was ich aus meinem Hirn
herausbekomme ;)

cu,

olli
Stefan Rybacki
2005-12-13 12:56:51 UTC
Permalink
Post by Oliver Haupt
...
Indem Du eine andere Datenstruktur nimmst ;)
Korrekt.
Post by Oliver Haupt
Dein Problem ist halt, dass (fast) alle Operationen o(log(n))
benoetigen, da dies die Tiefe deines Baumes ist.
Richtig.
Post by Oliver Haupt
...
Wenn Du bei sehr vielen Operationen O(1) moechtest, schau dir mal
B-Baeume an. Die Hoelle bei der Implementation, dafuer sind alle
interessanten Operationen in O(1).
Ein B-Baum ist nur ein abgewandelter AVL Baum und alle Operationen (Einfügen,
Suchen und Löschen) laufen in O(LOGm(n)) ab, wobei m die Ordnung des B-Baums ist.
Post by Oliver Haupt
Alles bitte mit einem Quentchen Salz, da meine Theo-Info Pruefung schon
ein Weilchen her ist.
... Ich hab mal bei Wiki nachgesehen - ein B-Baum ist leider nicht der,
den ich meinte - allerdings will mir der richtige Datentyp nicht
einfallen. Nichtsdestotrotz ist der B-Baum in der Paraxis schneller.
Aha ;)
Post by Oliver Haupt
Da war was mit Kreisfoermigen Verweisen und in verschiedenen Ebenen
rotierenden Blaettern. Das ist aber auch alles was ich aus meinem Hirn
herausbekomme ;)
Wer weiß, sobald du eine Baumstruktur hast wird das wohl nichts in O(1), weil du
ja mindestens beim Suchen einen Ast ablaufen mußt und du zum Löschen und
Einfügen meist einmal Suchen mußt.

Was mir adhoc zu O(1) einfällt ist Hashing, allerdings können Kollisionen das
O(1) wieder relativieren.

Bis denn dann
Stefan
Post by Oliver Haupt
cu,
olli
Oliver Haupt
2005-12-14 07:34:04 UTC
Permalink
Moin!
Post by Stefan Rybacki
Post by Oliver Haupt
Da war was mit Kreisfoermigen Verweisen und in verschiedenen Ebenen
rotierenden Blaettern. Das ist aber auch alles was ich aus meinem Hirn
herausbekomme ;)
Wer weiß, sobald du eine Baumstruktur hast wird das wohl nichts in O(1), weil du
ja mindestens beim Suchen einen Ast ablaufen mußt und du zum Löschen und
Einfügen meist einmal Suchen mußt.
Irgendwo hinten in meinem Hirn ist die Information, dass es eine
Baum(-artige) Struktur gibt die alle 'haeufigen' Operationen in O(1)
erledigt.

Wollte eigentlich gestern noch in meinem alten Uni-Kram nachsehen, da
hat dann aber die Motivation gefehlt.
Post by Stefan Rybacki
Was mir adhoc zu O(1) einfällt ist Hashing, allerdings können Kollisionen das
O(1) wieder relativieren.
*denk* Ist der Zugriff immer in O(1)? Ist das nicht
Verfahrensabhaengig?

cu,

olli
Stefan Rybacki
2005-12-14 09:50:47 UTC
Permalink
Post by Oliver Haupt
...
Post by Stefan Rybacki
Was mir adhoc zu O(1) einfällt ist Hashing, allerdings können Kollisionen das
O(1) wieder relativieren.
*denk* Ist der Zugriff immer in O(1)? Ist das nicht
Verfahrensabhaengig?
prinzipiell ist der Zugriff in O(1), gehen wir aber davon aus, daß wir
Kollisionen haben können und wir eine einfache verkettete Liste als Lösung für
eine Kollision nehmen wird O(1) zu O(1+Länge der liste). Natürlich gibt es auch
Ansätze neben der Liste. Man kann noch eine 2. Hashfunktion nehmen und dann erst
eine Liste. Dann ergibt sich O(2+Länge der Liste), wobei die Länge hier meist
kleiner ist als in der ersten Variante. Man kann natürlich auch statt eine Liste
wieder einen Baum nehmen, dann gibt ist die Komplexität O(1+log(länge)). Aber
prinzipell, d.h. ohne Kollisionen sind alle Operationen O(1).

Bis denn dann
Stefan


PS: die Baumstruktur, die dir vorschwebt würde mich mal interessieren, wäre als
schön, wenn du sie irgendwie rausfindest ;)
Post by Oliver Haupt
cu,
olli
Tarik Mustafic
2005-12-14 10:27:08 UTC
Permalink
Hallo allerseits,

also bedanke mich erstmal bei allen die auf mein Problem eingegangen
sind.

Es soll aber irgendwie möglich sein, einen AVL-Baum so zu
MANIPULIEREN, dass ein average case von O(1) auftritt, mit einem worst
case von O(log n). Dabei soll die Anzahl n der Elemente, die in die
Datenstruktur eingefügt werden sollen bekannt sein. Es ist angeblich
durch eine Verknüpfung von balancierten Suchbäumen und Hashing
machbar, dh. wenn man die beiden Vorteile der Verfahren kombiniert.

Vielleicht kommt man dadurch zu einer ganz neuen Art von Bäumen, oder
einer neuen Datenstruktur, das kann ich leider nicht sagen, weil mein
Wissen mir das nicht erlaubt ;)

Also ich bemühe mich weiter da was nützliches zu bauen, wenn ich
erfolg haben sollte, teile ich euch das hier gerne mit ;)

mfg

tarik
Oliver Haupt
2005-12-14 11:06:05 UTC
Permalink
Moin,
Post by Tarik Mustafic
Vielleicht kommt man dadurch zu einer ganz neuen Art von Bäumen, oder
einer neuen Datenstruktur, das kann ich leider nicht sagen, weil mein
Wissen mir das nicht erlaubt ;)
Ich bin mir sicher, dass es eine deratige Datenstruktur gibt.

Das war irgendwas mit Baeumen mit rotiernden Knotenlsiten pro Ebene.
Wimre aber alles andere als einfach zu implmentieren.

cu,

olli
Ingo Menger
2005-12-14 11:24:39 UTC
Permalink
Post by Tarik Mustafic
Hallo allerseits,
also bedanke mich erstmal bei allen die auf mein Problem eingegangen
sind.
Es soll aber irgendwie möglich sein, einen AVL-Baum so zu
MANIPULIEREN, dass ein average case von O(1) auftritt, mit einem worst
case von O(log n).
Hieße "average case O(1)" nicht, daß Du mindestens einen Fall dabei
hast, wo Du für eine Operation weniger als 1 Schritt brauchst, oder
aber alle Oprationen in O(1) ablaufen?
Das dürfte einigermaßen schwerfallen. :)
Paul Ebermann
2005-12-14 22:57:44 UTC
Permalink
Post by Ingo Menger
Post by Tarik Mustafic
Es soll aber irgendwie möglich sein, einen AVL-Baum so zu
MANIPULIEREN, dass ein average case von O(1) auftritt, mit einem worst
case von O(log n).
Hieße "average case O(1)" nicht, daß Du mindestens einen Fall dabei
hast, wo Du für eine Operation weniger als 1 Schritt brauchst, oder
aber alle Oprationen in O(1) ablaufen?
Das dürfte einigermaßen schwerfallen. :)
Schau dir mal die O-Notation genauer an. Konstante Faktoren sind
da egal, d.h. O(5) = O(1).


Paul
--
Alle meine Antworten, Feststellungen, Behauptungen
sind mit AFAIK und IMHO zu lesen und nicht in der
Luft- und Raumfahrt oder Atomindustrie zu verwenden.
Ingo R. Homann
2005-12-15 07:50:55 UTC
Permalink
Hi,
Post by Paul Ebermann
Post by Ingo Menger
Post by Tarik Mustafic
Es soll aber irgendwie möglich sein, einen AVL-Baum so zu
MANIPULIEREN, dass ein average case von O(1) auftritt, mit einem worst
case von O(log n).
Hieße "average case O(1)" nicht, daß Du mindestens einen Fall dabei
hast, wo Du für eine Operation weniger als 1 Schritt brauchst, oder
aber alle Oprationen in O(1) ablaufen?
Das dürfte einigermaßen schwerfallen. :)
Schau dir mal die O-Notation genauer an. Konstante Faktoren sind
da egal, d.h. O(5) = O(1).
Auch wenn mein Namensvetter es vielleicht nicht geschickt bzw. 100%id
exakt formuliert hat: Sein Argument ist IMHO richtig (ersetze "1" durch
"const", dann passt es).

Ciao,
Ingo
Ingo Menger
2005-12-15 10:53:49 UTC
Permalink
Post by Ingo R. Homann
Hi,
Post by Paul Ebermann
Post by Ingo Menger
Post by Tarik Mustafic
Es soll aber irgendwie möglich sein, einen AVL-Baum so zu
MANIPULIEREN, dass ein average case von O(1) auftritt, mit einem worst
case von O(log n).
Hieße "average case O(1)" nicht, daß Du mindestens einen Fall dabei
hast, wo Du für eine Operation weniger als 1 Schritt brauchst, oder
aber alle Oprationen in O(1) ablaufen?
Das dürfte einigermaßen schwerfallen. :)
Schau dir mal die O-Notation genauer an. Konstante Faktoren sind
da egal, d.h. O(5) = O(1).
Auch wenn mein Namensvetter es vielleicht nicht geschickt bzw. 100%id
exakt formuliert hat: Sein Argument ist IMHO richtig (ersetze "1" durch
"const", dann passt es).
Danke für die Klarstellung, nur so ergibt es natürlich einen Sinn.
Paul Ebermann
2005-12-15 11:43:05 UTC
Permalink
Post by Ingo R. Homann
Post by Paul Ebermann
Post by Ingo Menger
Post by Tarik Mustafic
Es soll aber irgendwie möglich sein, einen AVL-Baum so zu
MANIPULIEREN, dass ein average case von O(1) auftritt, mit einem worst
case von O(log n).
Hieße "average case O(1)" nicht, daß Du mindestens einen Fall dabei
hast, wo Du für eine Operation weniger als 1 Schritt brauchst, oder
aber alle Oprationen in O(1) ablaufen?
Das dürfte einigermaßen schwerfallen. :)
Schau dir mal die O-Notation genauer an. Konstante Faktoren sind
da egal, d.h. O(5) = O(1).
Auch wenn mein Namensvetter es vielleicht nicht geschickt bzw. 100%id
exakt formuliert hat: Sein Argument ist IMHO richtig (ersetze "1" durch
"const", dann passt es).
Hmm. Wenn bei n Aufrufen fast alle O(1) brauchen,
und (z.B.) nur O(n/(log n)) viele O(log n), dann
sind das zusammen
O(n/(log n) * log n) + O(n) = O(2n) = O(n),
also durchschnittlich O(1).


Paul
--
Zitieren im Usenet: http://einklich.net/usenet/zitier.htm
Warum Realnamen: http://www.wschmidhuber.de/realname/
Ingo R. Homann
2005-12-15 13:18:09 UTC
Permalink
Hi,
Post by Paul Ebermann
Hmm. Wenn bei n Aufrufen fast alle O(1) brauchen,
und (z.B.) nur O(n/(log n)) viele O(log n), dann
sind das zusammen
O(n/(log n) * log n) + O(n) = O(2n) = O(n),
also durchschnittlich O(1).
Damit setzt Du voraus, dass bei steigendem n die Anzahl der Fälle, in
denen der worst case auftritt, nicht proportional mit steigt.

Das klingt IMHO nach einer sehr ungewöhnlichen Annahme, von der ich mir
nicht vorstellen kann, dass es dafür ein praktisches Beispiel gibt. Aber
ich kann nicht beweisen, dass so etwas auch theoretisch ausgeschlossen ist.

Ciao,
Ingo
Ingo R. Homann
2005-12-15 13:23:57 UTC
Permalink
Hi,
Post by Ingo R. Homann
Damit setzt Du voraus, dass bei steigendem n die Anzahl der Fälle, in
denen der worst case auftritt, nicht proportional mit steigt.
Das klingt IMHO nach einer sehr ungewöhnlichen Annahme, von der ich mir
nicht vorstellen kann, dass es dafür ein praktisches Beispiel gibt. Aber
ich kann nicht beweisen, dass so etwas auch theoretisch ausgeschlossen ist.
Natürlich lässt sich so ein Fall konstruieren, z.B. eine HashMap, deren
Capacity mit n^2 steigt. Aber das ist IMHO genau das, was ich gerade
sagte, nämlich eben "konstruiert".

Ciao,
Ingo
Paul Ebermann
2005-12-17 04:19:34 UTC
Permalink
Post by Ingo R. Homann
Post by Paul Ebermann
Hmm. Wenn bei n Aufrufen fast alle O(1) brauchen,
und (z.B.) nur O(n/(log n)) viele O(log n), dann
sind das zusammen
O(n/(log n) * log n) + O(n) = O(2n) = O(n),
also durchschnittlich O(1).
Damit setzt Du voraus, dass bei steigendem n die Anzahl der Fälle, in
denen der worst case auftritt, nicht proportional mit steigt.
Ja. So muss man das machen, wenn man den Durchschnitt
retten will :-)

Ich hatte mir keinen Algorithmus überlegt, der so komische
Eigenschaften hat (du hast ja einen gefunden - aber der
n^2-Platz-Overhead relativiert den Gewinn wieder), aber
mit solchen Quotienten haben wir in der Probabilistische-
Analyse-Vorlesung auch immer gearbeitet, wenn ich mich recht
erinnere.


Paul
--
The Java Virtual Machine Specification:
http://java.sun.com/docs/books/vmspec/2nd-edition/html/VMSpecTOC.doc.html
Tarik Mustafic
2005-12-17 09:18:11 UTC
Permalink
Hallo Leute,

also nach einiger Recherche kam ich (mit euer Hilfe :)) zu folgendem
Lösungsvorschlag des oben angeführten Problems:

Das Rezept :)

Man implememntiere eine Klasse HashTabelle, welche ein Array von
NodeAVL-Elementen speichert. Zusätzlich implementiert man die
benötigten Methoden: hashFunktion()-soll den Hashwert zu einem String
liefern, dieser soll dann als Index in der Hashtabelle benutzt werden
beim Einfügen, Suchen, Löschen, dann Methoden wie search(), insert(),
delete(), etc...

Dabei speichert NodeAVL einen Namen z.B. (String), die Baumhöhe (für
die Balancierung), zwei Zeiger vom Typ NodeAVL und die Wurzel, auch vom
Typ AVLNode. Dann werden noch entsprechende Methoden, die ein AVLBaum
so halt braucht, implementiert: searchInTree(), insertInTree(),
deleteInTree(), Methoden für die Rotation, und andere...

So dann geht man meiner Meinung so vor wie jemand hier vorgeschlagen
hat, nämlich bei Kollisionen in der Hashtabelle, als Lösung Seperate
Chaining zu benutzen und halt dann als AVLBaum weiter verzweigen.

Vorgehensweise:
Einfügen
- Nehme den zu speichernden String und berechne den hashIndex mittels
hashFunktion()

- Nun überprüfe ob an der Stelle hashTabelleArray[hashIndex] etwas
steht, wenn nichts steht, füge dort ein, ansonsten, dh. es ensteht
eine Kollision, weil ein NodeAVL schon an der Stelle eingefügt ist,
dann fahre fort mit einfügen wie bei einem AVLBaum, also benutze dann
insertInTree(denKnoten) der Klasse AVLNode.

- Suchen
Beim Suchen, eines Elements, nehme ich den zu suchenden String,
berechne den hashIndex mittels der Funktion hashFunktion() und gucke im
hashTabelleArray[hashIndex] ob da das gesuchte Element steht, ist da
nix, kann ich false liefern, wenn das Element übereinstimmt dann true,
ansonsten suche ich weiter im AVLBaum, also searchInTree(denKnoten)

-Löschen
wäre dann Suchen und dann halt Löschen und die Bedingungen des
AVLBaums prüfen, etc...

Sooo damit entsteht dann ein Array von NodeAVL-Elementen, genaugesagt
sind es dann die Wurzeln der AVLBäume. Wie jemand schon gesagt
hat(Sorry das ich nicht nachgucke wer das wahr :)), habe ich im
arraybereich O(1) als average sowieso, wegen der
HashTabellenEigenschaft, weil ich den Index berechne beim Einfügen,
Löschen und beim Suchen, dh. hier brauch ich ja keine Sortierung, weil
ich weiß ich finde mein Element wenn ich mittels hashFunktion() den
indexwert habe, also greife ich sofort darauf zu.
Andernfalls suche ich ja weiter im Baum. Da dass aber sehrviele KLEINE
Bäume sind, es sei denn man wählt eine gute SträuFunktion
(hashFunktion()), die nicht so viele Kollisionen entstehen lässt, kann
ich davon ausgehen dass ich den Kontakt mit den Elementenmit wenig
Schritten, 2,3,4,5... erreiche, also dann auch in O(1) (glaube ich :))

Ansonsten im schlimmsten Fall muss ich den ganzen Baum an der Stelle
hashTabelleArray[hashIndex] durchlaufen, und das ist in dem Fall der
worst case der im AVLBaum gilt, also O(log n).

Also ich hoffe ich konnte das erläutern, hab das auch versprochen
falls ich darauf kommen sollte, und hoffe dass es auch stimmt. Bedanke
mich bei euch allen, und wünsche euch schöne Feiertage.


mfg

Tarik

Jochen Theodorou
2005-12-15 14:47:25 UTC
Permalink
Paul Ebermann schrieb:

[...]
Post by Paul Ebermann
Hmm. Wenn bei n Aufrufen fast alle O(1) brauchen,
und (z.B.) nur O(n/(log n)) viele O(log n), dann
sind das zusammen
O(n/(log n) * log n) + O(n) = O(2n) = O(n),
also durchschnittlich O(1).
ich dachte wir reden von n Aufrufen und nicht von n/logn. Ein
sortieralgorithmus der auf n/lognEinträgen arbeitet, statt auf n braucht
dann schliesschlich auch nur noch O((n/logn)*log(n/logn)) =
O((n/logn)*(logn-loglogn))) = O(n - n*(loglogn)/logn) = O(n)

der letzte Schrit ist erlaubt, weil loglogn sehr langsam wächst, also
sehr klein ist, und dann noch durch logn geteilt wird. Dh. n wächst sehr
viel schneller sodass asymptotisch n herauskommen dürfte.

Deswegen läuft ein Sortieralgorithmus aber noch lange nicht in O(n)!

Gruss theo
Ingo R. Homann
2005-12-15 14:56:12 UTC
Permalink
Hi,
Post by Jochen Theodorou
ich dachte wir reden von n Aufrufen und nicht von n/logn.
Nein, in diesem SubThread geht es im Wesentlichen um Ingos Aussage von
gestern, 12:24.

Ciao,
Ingo
Ingo Menger
2005-12-15 17:28:42 UTC
Permalink
Post by Paul Ebermann
Schau dir mal die O-Notation genauer an. Konstante Faktoren sind
da egal, d.h. O(5) = O(1).
Da fällt mir ein: da der OP ja davon ausgeht, daß n bekannt ist, ist
dann nicht auch n eine Konstante, und wäre somit nicht auch ein
O(n)-Algorithmus okay?
Paul Ebermann
2005-12-17 03:25:20 UTC
Permalink
Post by Ingo Menger
Post by Paul Ebermann
Schau dir mal die O-Notation genauer an. Konstante Faktoren sind
da egal, d.h. O(5) = O(1).
Da fällt mir ein: da der OP ja davon ausgeht, daß n bekannt ist, ist
dann nicht auch n eine Konstante, und wäre somit nicht auch ein
O(n)-Algorithmus okay?
Wenn n konstant ist, ist O(n) = O(n^2) = O(e^n) = O(1) ...

Aber n ist nicht konstant, nur für jedes konkrete Exemplar
des Problems vorher bekannt.


Paul
--
Ich beantworte Java-Fragen per E-Mail nur gegen Bezahlung. Kostenpunkt
100 Euro pro angefangene Stunde. Bitte erwähne in der Anfrage, dass du
das akzeptierst, da ich sonst die E-Mail einfach ignoriere.
(In der Newsgroup fragen ist billiger und oft auch schneller.)
Stefan Rybacki
2005-12-14 11:30:38 UTC
Permalink
Post by Tarik Mustafic
Hallo allerseits,
also bedanke mich erstmal bei allen die auf mein Problem eingegangen
sind.
Es soll aber irgendwie möglich sein, einen AVL-Baum so zu
MANIPULIEREN, dass ein average case von O(1) auftritt, mit einem worst
Wer sagt das?
Post by Tarik Mustafic
case von O(log n). Dabei soll die Anzahl n der Elemente, die in die
Datenstruktur eingefügt werden sollen bekannt sein. Es ist angeblich
durch eine Verknüpfung von balancierten Suchbäumen und Hashing
machbar, dh. wenn man die beiden Vorteile der Verfahren kombiniert.
Na dann mach das doch. Wie ich auch schon sagte kannst du ja das Hashing mit nem
AVL Baum als Kollisionslösung implementieren. Dabei benutzt du in erster Stufe
das Hashing und in jedem "Hashbucket" einen AVL Baum. Damit hast du im besten
Fall O(1) für jede Operation und bei Kollisionen halt O(1+log(a)), wobei a hier
bei Gleichverteilung um einiges kleiner ist als n.
Aber bedenke das Hashfunktioen auf einen bestimmten Bereich abbilden, d.h. hast
du den Bereich zu klein gewählt, d.h. du hast um einiges mehr an Elementen als
Hashbuckets, dann wird die Zahl der Kollisionen steigen und du entfernst dich
von O(1). Abhilfe schafft hier eine neue Hashfunktion mit größerem Bereich oder
man nimmt gleich lineares Hashen, bei dem der Bereich bei Bedarf ohne
*komplettes* neuhashen vergrößert werden kann. (Im Durschnitt werden maximal n/2
Elemente neugehasht)

Das hat allerdings nichts mit der Verknüpfung von balancierten Suchbäumen zu
tun. Fraglich ist da auch, wo dann der 2. balancierte Baum herkommt? Der muß
doch auch erzeugt werden und dann ist O(1) wieder futsch?!
Post by Tarik Mustafic
Vielleicht kommt man dadurch zu einer ganz neuen Art von Bäumen, oder
einer neuen Datenstruktur, das kann ich leider nicht sagen, weil mein
Wissen mir das nicht erlaubt ;)
Wer weiß.
Post by Tarik Mustafic
Also ich bemühe mich weiter da was nützliches zu bauen, wenn ich
erfolg haben sollte, teile ich euch das hier gerne mit ;)
Jup.


Bis denn dann
Stefan
Post by Tarik Mustafic
mfg
tarik
Jochen Theodorou
2005-12-14 12:32:43 UTC
Permalink
Post by Tarik Mustafic
Hallo allerseits,
also bedanke mich erstmal bei allen die auf mein Problem eingegangen
sind.
Es soll aber irgendwie möglich sein, einen AVL-Baum so zu
MANIPULIEREN,
also Einfügen und Löschen, suchen ist egal. Aber normalerweise besteht
das Einfügen aus einem Suchschritt. Wie wäre es mit Fibonacci-Heaps?

http://de.wikipedia.org/wiki/Fibonacci-Heap

Das ist auch ein AVL-Baum. Das ist allerdings schon ziemlich weit davon
entfernt was man im allgemeinen unter einem AVL-Baum versteht. Hier hat
man auch weniger einen Baum als eine Liste vo Bäumen... Naja, es erfüllt
deine Anforderung dass das Einfügen in O(1) (amortisiert) geht,
allerdings braucht das Löschen O(logn). Und damit kann es nciht die
gesuchte Struktur sein, oder?

Oder vielleicht erklärst du uns mal was du unter "manipulieren" verstehst.
Post by Tarik Mustafic
dass ein average case von O(1) auftritt, mit einem worst
case von O(log n). Dabei soll die Anzahl n der Elemente, die in die
Datenstruktur eingefügt werden sollen bekannt sein.
nunja, das für die meisten Verfahren ist es eher unwichtig wieviele
Elemente es letzendlich gibt. Ausser vielleicht bei Hashverfahren, da
könnte sich das als Vorteil herausstellen.
Post by Tarik Mustafic
Es ist angeblich
durch eine Verknüpfung von balancierten Suchbäumen und Hashing
machbar, dh. wenn man die beiden Vorteile der Verfahren kombiniert.
Wie jemand anderes schon meinte könnte man ein normales Hashverfahren
nehmen und wenn eine Kollision auftritt, dann baut man an dieser Stelle
einen Baum. Best Case wäre dann das Hashverfahren mit O(1), Worst Case
das des Baumes, also O(logn). Average case dürfte sich bei einem
geeigneten Hashverfahren nahezu bei O(1) bewegen
Post by Tarik Mustafic
Vielleicht kommt man dadurch zu einer ganz neuen Art von Bäumen, oder
einer neuen Datenstruktur, das kann ich leider nicht sagen, weil mein
Wissen mir das nicht erlaubt ;)
Also ich bemühe mich weiter da was nützliches zu bauen, wenn ich
erfolg haben sollte, teile ich euch das hier gerne mit ;)
mit obigem erledigst du zwar das Einfügen und Suchen sehr gut, aber was
ist mit dem Entfernen? Normalerweise willst du ja etwas sortieren, dass
heisst Einfügen von n Elementen und Entfernen von n Elementen. Wobei du
beim Entfernen logischerweise nicht weisst welchen Wert dieses Element hat.

Das heisst im Prinzip musst du alle Elemente durchgehen, damit wäre das
Entfernen O(n) und dein gesamter Algorithmus O(n²)... übel...

Also muss die Hashfunktion es mir erlauben einen Rückschluss darüber zu
erlauben wo in der Hashliste die Elemente zu finden sind.

h(x) = x mod m

x sei ein Wert, der eingefügt werden soll und m sei die Länge der
Hashliste. Dann organisiere ich die Bäume so dass das kleinste Element
immer in der Wurzel ist. Dann reicht es aus einmal durch meine Liste zu
gehen und das kleinste Element zu bestimmen (O(m)). Dann baue ich den
Baum um (O(log(bi), bi=Anzahl der Elemente im Baum i=h(x)).

Der Vorteil ist, dass du jetzt für ein Entfernen eine Laufzeit von
O(m+log(bi)) bekommst. Allerdings ist der Bestcase jetzt nicht m>=n,
denn dann habe ich für das Entfernen ja wieder einen Laufzeit von O(n)
und damit landet der Algorithmus wieder bei O(n²). Sagen wir also mal
m=log(n). Damit wächst m sehr langsam im Vergleich zu n.

Bei gleicher Verteilung kann ich annehmen alle bi sind etwa gleich
gross, also n/m bzw. n/logn. Das Entfernen eines Elementes in solch
einem Baum dauert daher O(log(n/logn)). Als Gesamtlaufzeit ergibt sich
für das Entfernen eines Elementes daher:

O(logn + log(n/logn)), was O(logn+logn-loglogn) = O(logn) ist.

Der WorstCase wäre dass alle Elemente vielfache von m sind und daher
alles in einen Baum gepackt wird. Dann ist der Baum logn hoch, dass
heisst O(logn+logn), was wiederum O(logn) ist.

Ein Sortieralgorithmus, der auf diesem Verfahren basiert hat dann als
Gesamtlaufzeit O(nlogn)

Was ich damit sagen will... es kann nicht sein dass Einfügen und
Entfernen in O(1) gehen für den Average Case. Wenn dem so wäre könnte
man in O(n) als average Case etwas sortieren. Denn jedes Sortieren
besteht aus n Einfüge und n Lösch-Operationen. Das würde bedeuten der
Algorithmus hätte eine Gesamtlaufzeit von nur O(n). Siehe dazu auch

http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/lowerbound.htm

Gruss theo
Paul Ebermann
2005-12-14 23:03:49 UTC
Permalink
Post by Jochen Theodorou
Post by Tarik Mustafic
Es ist angeblich
durch eine Verknüpfung von balancierten Suchbäumen und Hashing
machbar, dh. wenn man die beiden Vorteile der Verfahren kombiniert.
Wie jemand anderes schon meinte könnte man ein normales Hashverfahren
nehmen und wenn eine Kollision auftritt, dann baut man an dieser Stelle
einen Baum. Best Case wäre dann das Hashverfahren mit O(1), Worst Case
das des Baumes, also O(logn). Average case dürfte sich bei einem
geeigneten Hashverfahren nahezu bei O(1) bewegen
Klingt gut.
Post by Jochen Theodorou
Post by Tarik Mustafic
Vielleicht kommt man dadurch zu einer ganz neuen Art von Bäumen, oder
einer neuen Datenstruktur, das kann ich leider nicht sagen, weil mein
Wissen mir das nicht erlaubt ;)
Also ich bemühe mich weiter da was nützliches zu bauen, wenn ich
erfolg haben sollte, teile ich euch das hier gerne mit ;)
mit obigem erledigst du zwar das Einfügen und Suchen sehr gut, aber was
ist mit dem Entfernen? Normalerweise willst du ja etwas sortieren, dass
heisst Einfügen von n Elementen und Entfernen von n Elementen. Wobei du
beim Entfernen logischerweise nicht weisst welchen Wert dieses Element hat.
Kannst du das genauer erläutern?
Wenn ich ein Element aus der Struktur rausnehme, weiß ich
doch üblicherweise, welches (oder es ist mir egal, dann
ist das aber kein Problem).


Paul
--
The Java Language Specification: http://java.sun.com/docs/books/jls/index.htmls
Mit Änderungen durch 5.0:
http://jcp.org/aboutJava/communityprocess/pfd/jsr014/index2.html
(18 PDFs in einem Zip in einem anderen Zip - wer kennt eine bessere Version?)
Jochen Theodorou
2005-12-15 00:42:14 UTC
Permalink
[...]
Post by Paul Ebermann
Post by Jochen Theodorou
mit obigem erledigst du zwar das Einfügen und Suchen sehr gut, aber was
ist mit dem Entfernen? Normalerweise willst du ja etwas sortieren, dass
heisst Einfügen von n Elementen und Entfernen von n Elementen. Wobei du
beim Entfernen logischerweise nicht weisst welchen Wert dieses Element hat.
Kannst du das genauer erläutern?
Wenn ich ein Element aus der Struktur rausnehme, weiß ich
doch üblicherweise, welches (oder es ist mir egal, dann
ist das aber kein Problem).
du weisst ja auch welches Element du herausnehmen willst, aber leider
nciht *genau* welches. Üblicherweise willst du das kleinste Element oder
das grösste Element herausnehmen, aber den Wert weisst du noch nicht.
Wenn du den Wert schon vorher wüsstest, dann bräuchtest du ja
schliesslich nicht zu sortieren ;)

Gruss theo
Bernd Eckenfels
2005-12-15 00:57:41 UTC
Permalink
Post by Jochen Theodorou
Wenn du den Wert schon vorher wüsstest, dann bräuchtest du ja
schliesslich nicht zu sortieren ;)
Naja, du kennst den Wert des Keys, nicht notwendigerwiese den Rest des
Objektes (oder dessen Value Objoekt bei ner Map)

Gruss
Bernd
Jochen Theodorou
2005-12-15 12:00:30 UTC
Permalink
Post by Bernd Eckenfels
Post by Jochen Theodorou
Wenn du den Wert schon vorher wüsstest, dann bräuchtest du ja
schliesslich nicht zu sortieren ;)
Naja, du kennst den Wert des Keys, nicht notwendigerwiese den Rest des
Objektes (oder dessen Value Objoekt bei ner Map)
das ist aber eine andere Problemklasse. Das ist die Operation "suchen",
nciht löschen. Und um auf diese Art zu sortieren müsste ich a) alle keys
kennen un b) die Reihenfolge der keys wissen. Dann arbeite ich aber
schon mit sortierten Daten, daher brauche ich nicht nochmal sortieren.
Das Problem verlagert sich also nur.

Es sei denn, du willst garnicht sortieren. Für einen Cache brauche ich
in der Regel zum Beispiel keine sortierten Daten... zumindest nicht
solange da nicht automatisch etwas entfernt werden soll.

Gruss theo
Paul Ebermann
2005-12-15 00:49:42 UTC
Permalink
Post by Jochen Theodorou
[...]
Post by Paul Ebermann
Post by Jochen Theodorou
mit obigem erledigst du zwar das Einfügen und Suchen sehr gut, aber was
ist mit dem Entfernen? Normalerweise willst du ja etwas sortieren, dass
heisst Einfügen von n Elementen und Entfernen von n Elementen. Wobei du
beim Entfernen logischerweise nicht weisst welchen Wert dieses Element hat.
Kannst du das genauer erläutern?
Wenn ich ein Element aus der Struktur rausnehme, weiß ich
doch üblicherweise, welches (oder es ist mir egal, dann
ist das aber kein Problem).
du weisst ja auch welches Element du herausnehmen willst, aber leider
nciht *genau* welches. Üblicherweise willst du das kleinste Element oder
das grösste Element herausnehmen, aber den Wert weisst du noch nicht.
Wenn du den Wert schon vorher wüsstest, dann bräuchtest du ja
schliesslich nicht zu sortieren ;)
Dann musst du das anders formulieren - es geht
dir ja ums Suchen nach einem nicht-Hash-verträglichen
Kriterium, nicht um das Entfernen an sich.


Paul (Ja, das geht nicht in O(n) für n Objekte.)
--
Die Homepage von de.comp.lang.java: http://www.dclj.de
Pauls Package-Sammlung: http://purl.org/NET/ePaul/#pps
Paul Ebermann
2005-12-14 23:07:54 UTC
Permalink
Post by Tarik Mustafic
Es soll aber irgendwie möglich sein, einen AVL-Baum so zu
MANIPULIEREN, dass ein average case von O(1) auftritt, mit einem worst
case von O(log n). Dabei soll die Anzahl n der Elemente, die in die
Datenstruktur eingefügt werden sollen bekannt sein. Es ist angeblich
durch eine Verknüpfung von balancierten Suchbäumen und Hashing
machbar, dh. wenn man die beiden Vorteile der Verfahren kombiniert.
Nur um mal klar zu machen, was du willst:

Du hast n Elemente, und willst die irgendwie in
deine Datenstruktur stecken, so dass das ganze
insgesamt höchstens O(n) Zeit braucht.

Nachher willst du die n Elemente irgendwie alle
wieder herausholen, und das soll ebenfalls
höchstens O(n) brauchen.

Richtig?

Kannst du zu den benötigten Zugriffen noch etwas sagen?


Paul
--
Die dclj-FAQ wird immer freitags hier gepostet.
Eine (nicht ganz aktuelle) HTML-Version gibt es hier:
http://de.geocities.com/uweplonus/faq/
Tarik Mustafic
2005-12-15 00:37:32 UTC
Permalink
Hallo Paul,

es geht eigentlich nicht darum ALLE Elemente einzufügen und sie wieder
nacheinander zu löschen. Da erreicht man O(n), kann ich dir zustimmen,
es geht ja viel mehr um das Löschen, Einfügen, Suchen eines einzelnen
Elements. Die Baumstruktur soll halt so manipuliert werden, dass beim
Löschen z.B. nicht O(log n) im AVERAGE case auftritt. Deser Aufwand
(O(log n)) soll zwar im Worst Case gelten, aber es soll irgendwie
möglich sein im Average Case O(1) zu erreichen. Die Idee oben, dass
man ne Hashfunktion nimmt, und bei Kollisionen weiter als Baum
verzweigt, klingt ziemlich gut. Denn somit kann man mittels Hashing
entweder sofort auf das gesuchte(zu löschende Element) treffen, oder
man sucht halt weiter im worst case (O(log n)) weiter. Das gilt dann
auch für das Einfügen meiner Meinung nach.

Ich hoffe ich habe damit klarstellen können wie ich das meine :)
Ansonst nicht böse sein ;)

mfg

tarik
Jochen Theodorou
2005-12-15 01:15:05 UTC
Permalink
Tarik Mustafic schrieb:
[..]
Post by Tarik Mustafic
Ich hoffe ich habe damit klarstellen können wie ich das meine :)
Ansonst nicht böse sein ;)
Was du meinst ist mir schon relativ klar, aber was du damit machen
willst nicht unbedingt. Hashverfahren eignen sich nur bedingt zum
Sortieren, und deiner Beschreibung entnehme ich ein wenig dass du auch
granicht sortieren willst. Also die Frage: Was willst du überhaupt
machen? bzw. Welche Operationen musst du in welcher Zeit ausführen?
Operationen sind: suchen nach einem bestimmtem Element, einfügen,
löschen eines bestimmten Elementes, löschen des kleinsten/grössten
Elementes.

Die ersten 3 lassen sich mit einem Hashverfahren in O(1) bis O(logn)
erledigen.

Aber in der Regel lassen sich Operation 2 (einfügen) und 4 (löschen von
min/max) nicht beide gleichzeitig in O(1) als Average Case lösen. Das
gilt natürlich nur für Baumbasiernde Verfahren, denn die haben in der
Regel eine Aufbauphase und dann eine Abbauphase. Bei Verfahren wie
Quicksort gibt es keine echte Aufbau- oder Abbauphase, dafür einen
Sortierschritt, der bei den Baumverfahren in der Regel im Aufbau oder
Abbau oder beidem steckt, also durch die Anordnung der Knoten im Baum
wiedergespiegelt wird.


Gruss theo
Paul Ebermann
2005-12-15 01:03:13 UTC
Permalink
Post by Tarik Mustafic
es geht eigentlich nicht darum ALLE Elemente einzufügen und sie wieder
nacheinander zu löschen. Da erreicht man O(n), kann ich dir zustimmen,
Nicht unbedingt, das hängt ein wenig von den
genauen Anforderungen ab.
Post by Tarik Mustafic
es geht ja viel mehr um das Löschen, Einfügen, Suchen eines einzelnen
Elements. Die Baumstruktur soll halt so manipuliert werden,
Rede mal lieber nicht von "manipuliert", das passt hier nicht
ganz, glaube ich. Du möchtest sie variieren, kann das sein?

Nach welchen Kriterien suchst du hier?
Hast du den kompletten Schlüssel gegeben, oder willst
du auch größer-kleiner-Suchen machen?
Post by Tarik Mustafic
dass beim
Löschen z.B. nicht O(log n) im AVERAGE case auftritt.
Aber wie bestimmtst du denn den Durchschnitt?
Indem du n Elemente entfernst, und die Zeit durch
n teilst.
Oder willst du jetzt wirklich eine Betrachtung
über _alle möglichen Eingaben_ machen?
Post by Tarik Mustafic
Deser Aufwand
(O(log n)) soll zwar im Worst Case gelten, aber es soll irgendwie
möglich sein im Average Case O(1) zu erreichen. Die Idee oben, dass
man ne Hashfunktion nimmt, und bei Kollisionen weiter als Baum
verzweigt, klingt ziemlich gut. Denn somit kann man mittels Hashing
entweder sofort auf das gesuchte(zu löschende Element) treffen, oder
man sucht halt weiter im worst case (O(log n)) weiter. Das gilt dann
auch für das Einfügen meiner Meinung nach.
Klar, wenn du den Schlüssel des Elementes kennst (und somit den
Hash anwenden kannst), geht das so. Wenn du aber deine Struktur,
wie Jochen meinte, zum Sortieren nutzen willst, dann ist das
i.a. nicht mit dem Hash verträglich, und das suchen des jeweils
nächsten Elementes dauert zu lange.


Paul
--
Eine Signatur sollte mit "-- " abgetrennt werden,
wobei OjE meist das " " verschluckt. Eine nicht
korrekt abgetrennte Signatur ist keine Signatur ...
Stefan Rybacki
2005-12-15 11:46:14 UTC
Permalink
Post by Paul Ebermann
...
Klar, wenn du den Schlüssel des Elementes kennst (und somit den
Hash anwenden kannst), geht das so. Wenn du aber deine Struktur,
wie Jochen meinte, zum Sortieren nutzen willst, dann ist das
i.a. nicht mit dem Hash verträglich, und das suchen des jeweils
nächsten Elementes dauert zu lange.
Das stimmt, will man Kriterien wie größer/kleiner bei einer Suche mit
einbeziehen (das würde beim Sortieren ja zutreffen), dann hilft hashen nicht
wirklich weiter. Aber was spricht dann z.B. gegen eine weitere Hybridität (heißt
das so).

1. Halte Hashbuckets mit z.B. einem AVL Baum zur Kollisionsauflösung
1.1. zusätzlicher Verweis auf das größte als auch kleinste Element, damit kann
dann eine Exact-Match gemacht werden
2. Halte zusätzlich einen normalen AVL, B-Baum, R-Baum was auch immer auf alle
Elemente

Macht man nun einen Exact-Match benutzt man 1.
Macht man einen Partial-Match oder ein Range-Match nimmt man 2.

Kostet natürlich etwas mehr Speicher, aber was tut man nicht alles für
Geschwindigkeit ;)

Bis denn dann
Stefan
Post by Paul Ebermann
Paul
Jochen Theodorou
2005-12-15 12:42:45 UTC
Permalink
Stefan Rybacki schrieb:
[...]
Post by Stefan Rybacki
1. Halte Hashbuckets mit z.B. einem AVL Baum zur Kollisionsauflösung
einfügen = O(logb), b= grösse des Buckets. Bei konstanter Anzahl von
Buckets ist das O(logn)
Post by Stefan Rybacki
1.1. zusätzlicher Verweis auf das größte als auch kleinste Element,
damit kann dann eine Exact-Match gemacht werden
was ist mit dem zweitgrössten? Wenn ich auch das nth grösste Element
haben will, dann -> O(logn) für Einfügen
Post by Stefan Rybacki
2. Halte zusätzlich einen normalen AVL, B-Baum, R-Baum was auch immer
auf alle Elemente
O(logn) für Einfügen.
Post by Stefan Rybacki
Macht man nun einen Exact-Match benutzt man 1.
Macht man einen Partial-Match oder ein Range-Match nimmt man 2.
1 was? 2 was?

Werte? Und in wie weit bringt mir der 2. Wert etwas wenn ich nur den
grössten Wert zur Verfügung habe?

Gruss theo
Stefan Rybacki
2005-12-15 13:44:22 UTC
Permalink
Post by Jochen Theodorou
[...]
Post by Stefan Rybacki
1. Halte Hashbuckets mit z.B. einem AVL Baum zur Kollisionsauflösung
einfügen = O(logb), b= grösse des Buckets. Bei konstanter Anzahl von
Buckets ist das O(logn)
nein immernoch O(logb), wie kommst du auf O(logn)?
Post by Jochen Theodorou
Post by Stefan Rybacki
1.1. zusätzlicher Verweis auf das größte als auch kleinste Element,
damit kann dann eine Exact-Match gemacht werden
was ist mit dem zweitgrössten? Wenn ich auch das nth grösste Element
haben will, dann -> O(logn) für Einfügen
Dann kommt die 2. Struktur zum Tragen.
Post by Jochen Theodorou
Post by Stefan Rybacki
2. Halte zusätzlich einen normalen AVL, B-Baum, R-Baum was auch immer
auf alle Elemente
O(logn) für Einfügen.
korrekt, daß ist leider der Nachteil, daß Einfügeoperationen trotz Hashings auf
O(logn) ausarten.
Post by Jochen Theodorou
Post by Stefan Rybacki
Macht man nun einen Exact-Match benutzt man 1.
Macht man einen Partial-Match oder ein Range-Match nimmt man 2.
1 was? 2 was?
1. Hashverfahren
2. normaler Baum
Post by Jochen Theodorou
Werte? Und in wie weit bringt mir der 2. Wert etwas wenn ich nur den
grössten Wert zur Verfügung habe?
Welche Werte? 2. Wert?

Obiges hybrides Konstrukt ist für Suchoperationen effektiv allerdings für
Einfügeoperationen nicht zwingend effektiv.


Bis denn dann
Stefan
Post by Jochen Theodorou
Gruss theo
Jochen Theodorou
2005-12-15 14:57:30 UTC
Permalink
Post by Stefan Rybacki
Post by Jochen Theodorou
[...]
Post by Stefan Rybacki
1. Halte Hashbuckets mit z.B. einem AVL Baum zur Kollisionsauflösung
einfügen = O(logb), b= grösse des Buckets. Bei konstanter Anzahl von
Buckets ist das O(logn)
nein immernoch O(logb), wie kommst du auf O(logn)?
b = n/B, B = Anzahl der Buckets

O(log(n/B)) = O(logn - logB) = O(logn), da logB konstant.
Post by Stefan Rybacki
Post by Jochen Theodorou
Post by Stefan Rybacki
1.1. zusätzlicher Verweis auf das größte als auch kleinste Element,
damit kann dann eine Exact-Match gemacht werden
was ist mit dem zweitgrössten? Wenn ich auch das nth grösste Element
haben will, dann -> O(logn) für Einfügen
Dann kommt die 2. Struktur zum Tragen.
ja gut, aber das befreit mich nicht davon es zu ermitteln ;) Also
entweder beim Einfügen vorzubereiten, oder eben beim Löschen
Post by Stefan Rybacki
Post by Jochen Theodorou
Post by Stefan Rybacki
2. Halte zusätzlich einen normalen AVL, B-Baum, R-Baum was auch immer
auf alle Elemente
O(logn) für Einfügen.
korrekt, daß ist leider der Nachteil, daß Einfügeoperationen trotz
Hashings auf O(logn) ausarten.
womit der Vorteil des Hashing schwindet.
Post by Stefan Rybacki
Post by Jochen Theodorou
Post by Stefan Rybacki
Macht man nun einen Exact-Match benutzt man 1.
Macht man einen Partial-Match oder ein Range-Match nimmt man 2.
1 was? 2 was?
1. Hashverfahren
2. normaler Baum
ok. Von 1 hast du nur was wenn du oft fragen musst.

[...]
Post by Stefan Rybacki
Obiges hybrides Konstrukt ist für Suchoperationen effektiv allerdings
für Einfügeoperationen nicht zwingend effektiv.
deswegen wollte ich ja wissen von welchen Operationen wir eigentlich
sprechen.

Gruss theo
Stefan Rybacki
2005-12-15 15:35:59 UTC
Permalink
Post by Jochen Theodorou
Post by Stefan Rybacki
Post by Jochen Theodorou
[...]
Post by Stefan Rybacki
1. Halte Hashbuckets mit z.B. einem AVL Baum zur Kollisionsauflösung
einfügen = O(logb), b= grösse des Buckets. Bei konstanter Anzahl von
Buckets ist das O(logn)
nein immernoch O(logb), wie kommst du auf O(logn)?
b = n/B, B = Anzahl der Buckets
O(log(n/B)) = O(logn - logB) = O(logn), da logB konstant.
logb kann icht konstant sein, weil du n nicht kennst sonst wäre logn auch
konstant? Es ist doch so, daß ich beim Einfügen gerade nicht alle n Elemente in
dem Bucket habe, sondern halt nur b Elemente, ich verstehe somit nicht, wie
O(logb) auf O(logn) ausarten könnte.
Post by Jochen Theodorou
Post by Stefan Rybacki
Dann kommt die 2. Struktur zum Tragen.
ja gut, aber das befreit mich nicht davon es zu ermitteln ;) Also
entweder beim Einfügen vorzubereiten, oder eben beim Löschen
Beim löschen sehe ich noch nicht so das Problem, solange ein exakt match gemacht
werden kann, könnte man den Eintrag per hashen suchen und dort löschen und
zusätzlich könnte man ja einen Verweis auf den Knoten im normalen Baum dort
halten womit man direkten Zugriff hat. Bleibt aber immernoch das Einfügen :(
Post by Jochen Theodorou
Post by Stefan Rybacki
korrekt, daß ist leider der Nachteil, daß Einfügeoperationen trotz
Hashings auf O(logn) ausarten.
womit der Vorteil des Hashing schwindet.
ja leider
Post by Jochen Theodorou
Post by Stefan Rybacki
1. Hashverfahren
2. normaler Baum
ok. Von 1 hast du nur was wenn du oft fragen musst.
Richtig.
Post by Jochen Theodorou
deswegen wollte ich ja wissen von welchen Operationen wir eigentlich
sprechen.
Ja, daß wäre natürlich hilfreich, da man nicht alles mit O(1) abdecken kann.

Bis denn dann
Stefan
Post by Jochen Theodorou
Gruss theo
Jochen Theodorou
2005-12-15 16:25:47 UTC
Permalink
Stefan Rybacki schrieb:
[...]
Post by Stefan Rybacki
Post by Jochen Theodorou
Post by Jochen Theodorou
einfügen = O(logb), b= grösse des Buckets. Bei konstanter Anzahl von
Buckets ist das O(logn)
[...]
Post by Stefan Rybacki
Post by Jochen Theodorou
b = n/B, B = Anzahl der Buckets
O(log(n/B)) = O(logn - logB) = O(logn), da logB konstant.
logb kann icht konstant sein,
logB, nicht logb. logb ist proportional zu logn.
Post by Stefan Rybacki
Es ist doch so, daß ich beim Einfügen gerade nicht alle n
Elemente in dem Bucket habe, sondern halt nur b Elemente, ich verstehe
somit nicht, wie O(logb) auf O(logn) ausarten könnte.
bei einer Gleichverteilung auf alle Buckets ist bei fester Anzahl der
Buckets eben eine Anzahl von Elementen in jedem Bucket welche
proportional zu n ist.

Sobald auch nur eines deiner Buckets proportional zu n wächst hast du
verloren.

Gruss theo
Sven Köhler
2005-12-13 14:19:39 UTC
Permalink
Post by Tarik Mustafic
Ich schreibe einen AVL-Baum, nichts spannendes, gibs halt viele Bücher
etc dazu, wo alles bestens erklärt ist.
Hmmm ...

Mein Prof hat mich mal gewarnt: schreiben Sie nie einen AVL-Baum. So
viele Spezialfälle - da vertut man sich nur. Schreiben Sie statt dessen
einen Rot-Schwarz-Baum.

Den Rot-Schwarz-Baum gibt's schon, nennt sich TreeSet/TreeMap im package
java.util ;-)
Ingo Menger
2005-12-13 16:20:43 UTC
Permalink
Post by Tarik Mustafic
Was mich aber interessiert ist, wie man bei den Grundoperationen im
AVL-Baum (Search,Insert, Delete) einen Average Case von O(1) erziehlt?
Da gibt es nur eine Möglichkeit: Speichere nie mehr als 1 Element in
den Baum, dann kommst Du bei Search, Update, Delete und Insert (das Du
halt nur einmal machen darfst) mit O(1) aus.
Stefan Rybacki
2005-12-13 21:32:49 UTC
Permalink
Post by Ingo Menger
...
Da gibt es nur eine Möglichkeit: Speichere nie mehr als 1 Element in
den Baum, dann kommst Du bei Search, Update, Delete und Insert (das Du
halt nur einmal machen darfst) mit O(1) aus.
Die Komplexität bleibt trotzdem bei O(n).

Bis denn dann
Stefan
Marco Lange
2005-12-13 17:37:15 UTC
Permalink
Hi,
Post by Tarik Mustafic
Ich schreibe einen AVL-Baum, nichts spannendes, gibs halt viele Bücher
etc dazu, wo alles bestens erklärt ist.
Was mich aber interessiert ist, wie man bei den Grundoperationen im
AVL-Baum (Search,Insert, Delete) einen Average Case von O(1) erziehlt?
Mir würden paar "schriftliche" Gedanken vollkommen ausreichen.
Eine Average-Case-Analyse von Algorithmen ist alles andere als trivial.
Als Startpunkt benötigt man dafür erstmal eine
Wahrscheinlichkeitsverteilung auf den möglichen Eingaben. Im einfachsten
Fall kann man dafür eine Gleichverteilung heranziehen, aber ob die immer
Sinn macht, ist eine andere Frage. In den meisten Anwendungsfällen
dürften die Daten nicht gleichverteilt sein.

O(1) auf gleichverteilten Eingaben halte ich für Unsinn, siehe Jochens
Begründung. Ein auf Vergleichen beruhendes Sortierverfahren kann nicht
schneller als O(n log n) im Average Case (Gleichverteilung) sein. Mit
einem AVL-Baum mit diesen Eigenschaften könntest Du in durchschnittlich
O(n) sortieren.

Viele Grüße,
Marco
Lesen Sie weiter auf narkive:
Loading...