Ein paar Fragen zu Datenstrukturen(AVL-Baum,Datei,Liste)
-
Binärbäume sind grundsätzlich balanziert!
Ansonsten hat der Programmierer den Mathematiker nicht verstanden und der 'Baum' verkommt zu einer verketteten Liste...
-
Nein, sind sie nicht.
-
Joe_M. schrieb:
Binärbäume sind grundsätzlich balanziert!
Ansonsten hat der Programmierer den Mathematiker nicht verstanden und der 'Baum' verkommt zu einer verketteten Liste...ROFLMAO
-
Ah ok, vielen Dank
Also bei der Datei war halt meine Frage, ob sie ein homogener oder heterogener Typ ist, weil da bin ich mir irgendwie unsicher...
Das mit der Liste wollte ich halt nur generell mal wissen, ob es da z.B. irgendeine Definition gibt die z.B. sagt, dass jedes Element in einer verketteten Liste eindeutig identifizierbar sein muss.
-
Eine Datei ist an sich überhaupt kein Datentyp.
Es gibt allerdings in Pascal die Eigenart, dass Dateien als eine Art homogener Felder angesehen werden, man deklariert eine Datei z.b. als Variable vom Typ "File of Integer". Vielleicht meintest du das ja. Mit der realen Welt hat das nicht viel zu tun.
-
Joe_M. schrieb:
Binärbäume sind grundsätzlich balanziert!
Ansonsten hat der Programmierer den Mathematiker nicht verstanden und der 'Baum' verkommt zu einer verketteten Liste...Also soweit ich weiss, gibt die Anzahl der maximal möglichen
Nachfolger den Rang vor.
Somit ist auch eine verkette Liste ein Binärbaum, wenn jeder Knoten die Möglichkeit
besitzt, auf 2 weitere zu zeigen, auch wenn es keiner tut.Ist halt dann einfach dumm gelaufen, wenn die Werte so daherkommen, dass beim Einfügen in einen Baum eine lineare Liste entsteht.
Imho ist ein zufälliger Binärbaum im Mittel sogar besser als ein AVL-Baum,
was die Laufzeit angeht: 1.38 * ln(N) <> 1.44 * ln(N)
(oder irgendwie so ähnlich war das...)
-
Also bei einer verketteten Liste zeigt ein Knoten definitionsgemäß (gemäß der Definition einer Liste) maximal nur auf einen Nachfolger. Was natürlich wirklich passieren kann, ist, dass ein Baum auch zu einer Liste degeneriert. Eine Liste ist jedoch niemals ein Baum.
Wie gut ein zufälliger Baum ist, kann man irgendwie schwer angeben, da es völlig von den Eingabedaten abhängt. Aber ein höhenausgeglichener Baum, wie der AVL-Baum einer ist, ist nicht sehr aufwändig und bietet im Mittel log n Zugriff. Ein komplett ausbalancierter Baum lohnt sich natürlich oft nicht, vor allem nicht, wenn der Inhalt sich häufig ändert. Wenn ich mich nicht irre, sind die beiden Zahlen, die du nennst der Vergleich zwischen einem höhenausgeglichenen Baum und einem vollständig ausgeglichenem. Der zufällige ist mit Sicherheit schlechter.
-
Optimizer schrieb:
Der zufällige ist mit Sicherheit schlechter.
och, gar nicht so. der zufällige ist wenn ich mich recht erinnere so, daß die weglänge durchschnittlich gerademal eine kante länger ist als beim optimalen baum.
AVL oder sowas muß man nehmen, damit der rechner nicht einfach stehenbleibt, wenn doch mal ganz unzufällige daten kommen.
-
Optimizer schrieb:
Wie gut ein zufälliger Baum ist, kann man irgendwie schwer angeben, da es völlig von den Eingabedaten abhängt.
Dann bildet man eben den Erwartungswert.
-
Ich würde bei gleichverteilten Eingaben erwarten, dass der Baum perfekt ausbalanciert ist.
-
Optimizer schrieb:
Ich würde bei gleichverteilten Eingaben erwarten, dass der Baum perfekt ausbalanciert ist.
bei perfekt gleichverteilten eingaben?
also wenn ich einen perfekten würfel habe, würde ich dennoch nicht erwarten, daß nach 600 würfen jede zahl perfekt 100 mal drankam. deswegen ist die weglänge bei zufälligen eingaben auch ein klitzwenig länger.
-
Optimizer schrieb:
Ich würde bei gleichverteilten Eingaben erwarten, dass der Baum perfekt ausbalanciert ist.
bei nem tree aus
[1,2,3] ; hat man 4 mal AVL verletzt bei 6 Möglichkeiten 2/3
[1,2,3,4] ; hat man 12 mal AVL verletzt bei 24 Möglichkeiten 1/2
[1,2,3,4,5] ; hat man 80 mal AVL verletzt bei 120 Möglichkeiten 2/3