# Durchschnittliche Pfadlänge eines binärem Baumes



## REC (20. Feb 2011)

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 (20. Feb 2011)

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 (20. Feb 2011)

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 (20. Feb 2011)

REC hat gesagt.:


> Das ist ein Binärer Baum


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


----------



## darekkay (20. Feb 2011)

mogel hat gesagt.:


> 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 (20. Feb 2011)

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


----------



## Empire Phoenix (21. Feb 2011)

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


----------



## JohannisderKaeufer (21. Feb 2011)

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 (21. Feb 2011)

darekkay hat gesagt.:


> 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 (21. Feb 2011)

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 (21. Feb 2011)

mogel hat gesagt.:


> 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 (21. Feb 2011)

REC hat gesagt.:


> ```
> A
> /  \
> B    C
> ```



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


REC hat gesagt.:


> ```
> A
> /    \
> B      C
> ...



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 (21. Feb 2011)

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 (21. Feb 2011)

Empire Phoenix hat gesagt.:


> 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 (21. Feb 2011)

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 (21. Feb 2011)

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_ (22. Feb 2011)

REC hat gesagt.:


> 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 (22. Feb 2011)

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 (22. Feb 2011)

Blakh hat gesagt.:


> Vielleicht kriegst du die Pfadlänge so:
> 
> Zur 4 : 0
> Zur 2 : 1
> ...



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.



Dit_ hat gesagt.:


> 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_ (22. Feb 2011)

Mittlere Pfadlänge der binären Bäume


----------



## binbaeume (22. Feb 2011)

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


----------



## Gast2 (23. Feb 2011)

binbaeume hat gesagt.:


> 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 (23. Feb 2011)

mogel hat gesagt.:


> 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.


----------

