Durchschnittliche Pfadlänge eines binärem Baumes

[REC]

Ich habe hier mal wieder eine Aufgabe zu lösen.
Man muss/kann die durchschnittliche Pfadlänge eines binärem Baumes herausfinden. Der Lehrer gab uns als Tipp anzahl Pfadlänge/ anzahl Knoten.
Habe nun ein bisschen was probiert. Aber mal zu Verständniss. Bei solch einem Baum,

          A
         /  \
        B    C

Erhalte ich die Pfadlänge 3. Weil ich quasi den Pfad zu A mitzähle. Aber das kann ich ja leicht korriegieren indem ich am Schluss vor der Division einfach minus 1 rechne.
Aber stimmt das überhaupt?Ist dies die Pfadlänge?
Bei solch einem Baum:

                            A
                          /    \
                         B      C
                                  \
                                    D
                                     \
                                       E

Ist meiner Meinung nach die Pfadlänge 4. Und die Anzahl Knoten 5.
Das heisst die durschnittliche Pfadlänge ist 0.8?
Stimmt das so oder schaue ich die Sache falsch an?Weil wenn ich es falsch verstehe muss ich gar nicht erst beginnen zu implementieren

 

[Gast2]

Dein zweiter Baum ist Unsinn ... das ist kein Binärer Baum ... die Pfadlänge ergibt sich aus den Suchschritten zunächst finden eines Blattes

 

[REC]

Ok wäre schön zu wissen warum mein 2 Baum Unsinn ist? Vielleicht nochmal mit Zahlen.Das ist ein Binärer Baum

                         4
                       /  \
                      2    8
                     /      \
                    1        9
                               \
                                15

Das heisst alles was kleiner ist kommet in den linken Zweig oder sonst in den rechten.Wenn man nun zum Beispiel 10 einsetzten will kommt das nun links unten bei 15.Da es grösser als 9 aber kleiner als 15 ist

                         4
                       /  \
                      2    8
                     /      \
                    1        9
                               \
                                15
                               /
                             10

Trotzdem habe ich deinen Satz nicht ganz verstanden`?

...die Pfadlänge ergibt sich aus den Suchschritten zunächst finden eines Blattes

 

[Gast2]

Das ist ein Binärer Baum

nein ist es nicht :autsch: ... :rtfm: Binärbaum ? Wikipedia

 

[darekkay]

nein ist es nicht :autsch: ... :rtfm: Binärbaum ? Wikipedia

Und was genau macht das Beispiel von REC zu einem nicht binären Baum? Falls du darauf hinaus willst, dass der Baum immer zwei Kindknoten haben muss, sollte der von dir gepostete Wiki-Eintrag klar machen, dass es nicht notwendig ist.

Genauer gesagt handelt es sich um einen Wurzelbaum (gewurzelten Baum), bei dem jeder Knoten höchstens zwei Kindknoten besitzt.

 

[Final_Striker]

Ich würde mal sagen log n. Wobei n die Anzahl der Knoten ist.

 

[Empire Phoenix]

log n ist die durchschnittliche ziet einen knoten zu finden, wobei ja der pfad abgegangen werden muss -> durchschnittliche pfadlänge log n

 

[JohannisderKaeufer]

Was ist die durchschnittliche Pfadlänge?

Ein Binärbaum kann balanciert sein, muss es aber nicht.

Die Berechnungen der Pfadlänge mit

[log n] // mit Gaußklammern

beziehen sich auf einen balancierten Baum.
Die Pfadlänge gibt die Anzahl der Kanten an, die durchlaufen werden müssen um zum weitest Entfernten Blatt zu kommen.

Für die Beispiele sollte folgendes gelten.

Post | Beispiel | Pfadlänge | Balanciert | Anz. Knoten | Pfadlänge in balanciertem Zustand
1 | 1 | 1 | true | 3 | 1
1 | 2 | 3 | false| 5 | 2
2 | 1 | 3 | false| 6 | 2
2 | 2 | 4 | false| 7 | 2

Die Frage nach der durchschnittlichen Pfadlänge kann ich allerdings nicht beantworten.

 

[Gast2]

Und was genau macht das Beispiel von REC zu einem nicht binären Baum? Falls du darauf hinaus willst, dass der Baum immer zwei Kindknoten haben muss, sollte der von dir gepostete Wiki-Eintrag klar machen, dass es nicht notwendig ist.

das ist mir bewusst ... nur hat er einen Knoten - der Rest ist ein normale Liste und nicht mal annähernd ein Bin-Baum

das Beispiel muss die 8 als Wurzel haben ... dann geht es nach Links mit 2 und 4 weiter - die 1 wird unter die 2 angeordnet ... 9 und 15 werden rechts von 8 angeordnet ... gar lustig wird es wenn die 10 einsortiert wird ... dann wird die 9 zur Wurzel mit 10 und 15 als Kind rechts ... von der 9 geht es links mit 4 und 8 weiter ... 1 und 2 werden unter die 4 einsortiert

log2 zur 7 ist rund 3 ... 3 Schritte werden benötigt um die 1 zu finden

 

[Empire Phoenix]

annähernd ein Bin-Baum

Dummschwätzer, das ist ein binbaum, niemand hat hier was von gewichteten oder RBBaumen gesagt.
Der ist zwar degeneriert, aber das darf durchaus vorkommen, auch wenn es die effizienz verringert(Beim suchen) und die Pfadlängen erhöht.

 

[Blakh]

das ist mir bewusst ... nur hat er einen Knoten - der Rest ist ein normale Liste und nicht mal annähernd ein Bin-Baum

Genauer gesagt handelt es sich um einen Wurzelbaum (gewurzelten Baum), bei dem jeder Knoten höchstens zwei Kindknoten besitzt.

Aus deinem Wiki-Link.....

Du redest von:

Vollständig balancierter Binärbaum [Bearbeiten]

Ein vollständig balancierter Binärbaum ist ein voller Binärbaum, bei dem die Abstände zweier beliebiger Blätter von der Wurzel um höchstens 1 voneinander abweichen. Ein vollständiger Binärbaum ist ein vollständig balancierter Binärbaum. (Siehe auch Balancierter Baum oder AVL-Baum.)

Ebenfalls aus deinem Wiki-Link...

 

[Blakh]

          A
         /  \
        B    C

Knoten: 1, Pfadlänge: 2 Pfadlänge/Knoten: 2 Müsste eher 1 sein hmm...

                            A
                          /    \
                         B      C
                                  \
                                    D
                                     \
                                       E

Die unteren Einträge sind doch Blätter und eine Knoten. Für mich heisst das: Anzahl Knoten: 3, Pfadlänge zu B: 1 PfadLänge zu E 3 Pfadlänge/Knoten: 4/3 müsste eher 2 sein

K.a. da übersehen wir was...

 

[Blakh]

Wieso rechnest nicht einfach die Anzahl der Knoten / 2, wobei in beiden Beispielen A 2 mal durchlaufen wird und somit doppelt zählt? Müsste doch hinhauen oder?

 

[darekkay]

annähernd ein Bin-Baum

Dummschwätzer, das ist ein binbaum, niemand hat hier was von gewichteten oder RBBaumen gesagt.
Der ist zwar degeneriert, aber das darf durchaus vorkommen, auch wenn es die effizienz verringert(Beim suchen) und die Pfadlängen erhöht.

So sieht's aus... Ich find's traurig, wenn jemand Quellen angibt, diese aber anscheinend selbst nicht durchgelesen hat. Die reine Definition eines bin. Baumes habe ich bereits oben zitiert, von Spezialfällen war hier nie die Rede.

 

[REC]

Wie ich sehe ist hier ziemlich diskutiert worden. Leider habe ich immer noch nicht ganz verstanden warum mein Beispiel KEIN binärer Baum ist? Ein Knoten muss ja nicht zwingend 2 Kinder haben. Und es geht ja ums einordnen von Zahlen.Darum kann es ja manchmal sein das ein Ast halt länger wird als der andere. Dann kann es ja eben sein das der Baum nicht ausbalanciert ist. Wenn man das wollte müsste man doch eine Liste sortieren dann die Mitte nehmen und dann anfangen den binären Baum zu füllen. Und ja die einzelne Knoten sind dann einfach eine verkettete Listen.

Soviel ich weiss kann man nicht einfach /2 rechen. Man muss die Pfadlänge und die Anzahl Knoten haben. Leider habe ich aus euren Antworten nicht ganz gsehen wie ich diese Pfadlänge zähle?

Habe noch andere Leute gefragt. Anscheined ist bei folgendem Beispiel die Pfadlänge 6. Stimmt das????:L

--> 1 +2+2

                              4
                             / \
                            2   17
                                /  \
                               12  19

 

[Blakh]

Vielleicht kriegst du die Pfadlänge so:

Zur 4 : 0
Zur 2 : 1
Zur 17 : 1
Zur 12 : 2
Zur 19 : 2

Macht 6 ....

 

[Dit_]

Wie ich sehe ist hier ziemlich diskutiert worden. Leider habe ich immer noch nicht ganz verstanden warum mein Beispiel KEIN binärer Baum ist?

dein Baum ist ein binärer Baum. Ein nicht balancierter Baum kann durchaus zu einer Liste entarten. Es geht immer um die Reihenfolge beim einfügen. Werden die Zahlen gut ausgewaehlt so wird dein Baum immer balanciert sein.

PfadLänge steht ja für "Qualität" des Baumes. Dafür gibt es spezielle komplizierte mathematische Formel.
Hat der Lehrer keine vereinfachte Formel vorgestellt?

 

[binbaeume]

Die Konten eines bin. Baums haben keine, einen oder zwei Kindernoten. Alle dargestellten Bäume sind b. Bäume. Irritierend sind die Antworten von mogel.
Blätter sind ebenfalls Knoten. Knoten, die keine Blätter sind, nennen sich auch innere Knoten und Blätter auch Blattknoten.
In ausbalancierten b. Bäumen ist die Pfadlänge von der Wurzel zu Blättern maximal log n aufgerundet.
Beim ersten Beispiel haben beide Pfade die Länge 1 und beim zweiten Beispiel der linke Pfad von der Wurzel zum Blatt die Länge 1, der rechte Pfad von der Wurzel zum Blatt die Länge 3.
Was ist mit durchschnittlicher Pfadlänge gemeint? Ist ein Pfad immer von der Wurzel zu einem Blatt?

 

[REC]

Vielleicht kriegst du die Pfadlänge so:

Zur 4 : 0
Zur 2 : 1
Zur 17 : 1
Zur 12 : 2
Zur 19 : 2

Macht 6 ....

Nun ja wenn das stimmt könnte das wahrscheinlich die Pfadlänge sein. So sehe ich auch schon wie man es nun zählt.
Ist eben blöde,gibt der Lehrer solche Aufgaben aber keine Lösung was für Zahlen dabei rauskommen sollten.

dein Baum ist ein binärer Baum. Ein nicht balancierter Baum kann durchaus zu einer Liste entarten. Es geht immer um die Reihenfolge beim einfügen. Werden die Zahlen gut ausgewaehlt so wird dein Baum immer balanciert sein.

PfadLänge steht ja für "Qualität" des Baumes. Dafür gibt es spezielle komplizierte mathematische Formel.
Hat der Lehrer keine vereinfachte Formel vorgestellt?

Nein eben nicht. Es heisst einfach man soll die Anzahl Pfadlänge / Anzahl Knoten rechnen.

Aber wenn das von Blakh stimmt, dann wirdwird das die Pfadlänge sein.

 

[Dit_]

Mittlere Pfadlänge der binären Bäume

 

[binbaeume]

Bleibt noch zu klären, was ein Pfad ist. In dem Wiki kommt Pfad nicht vor. Was meint der Lehrer dazu?

 

[Gast2]

Irritierend sind die Antworten von mogel.

weil der Sonderfall (als Liste) in meinem Kopf keinen Sinn ergibt ... damit verliere ich den Vorteil schnell ein Element zu finden

 

[binbaeume]

weil der Sonderfall (als Liste) in meinem Kopf keinen Sinn ergibt ... damit verliere ich den Vorteil schnell ein Element zu finden

Es ist aber ein Bin-Baum..immernoch. Nichtbalancierte Bäume haben auch ihre Anwendung und wenn es darum geht, ein Element schnell zu finden, gibt es andere implementierungen.