Ein paar Fragen zu Datenstrukturen(AVL-Baum,Datei,Liste)
-
AVL-Baum:
Stimmt es, dass ein AVL-Baum auch immer ein binärer SUCHBaum sein muss, oder reicht da auch schon ein binärer Baum ? Hab da mal bissl im Internet geschaut, und einmal stand es als binärer Suchbaum, und einmal als Binärbaum...Datei:
Eine Datei ist ja ein dynamischer, strukturierter Typ. Und ist eine Datei homogen oder heterogen ? Ich würde sagen homogen oder ?Verkettete Liste:
Müssen die Elemente einer verketteten Liste eine Komponente enthalten, wodurch sie eindeutig identifizierbar sind oder nicht (nach der strengen Definition) ?
Also implementieren könnte man das ja schon (so dass auch doppelte Elemente vorkommen), aber kann ja sein, dass das so nicht vorgesehen ist..Wär super wenn mir da jmd helfen könnte. Danke.
-
AVL-Baum: Ja, ist ein Suchbaum, der halt zusätzlich ausbalanciert wird.
Datei: Welchen Sinn soll diese Frage haben?
Verkette Liste: Ob ein Element identifizierbar ist, hängt vom Elementtyp ab, das ist IMHO nicht Aufgabe der verketteten Liste. Eine verkettete Liste an sich muss eigentlich überhaupt keine Anforderungen nach Vergleichbarkeit oder Identifizierbarkeit stellen und prinzipiell können Elemente auch doppelt enthalten sein. Aber das musst du ja eigentlich je nach Anwendungszweck selber wissen, was du brauchst.
-
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