TU Wien:Mathematik 1 UE (diverse)/Übungen WS07/Beispiel 216
Die externe Pfadlänge eines Tries ist die Summe der Abstände von der Wurzel zu allen besetzten Endknoten des Baumes, wobei die Abstände in der Anzahl der Kanten auf dem entsprechenden Weg gemessen werden. Wie groß ist die externe Pfadlänge eines Tries, der Daten enthält, mindestens? (Hinweis: Welche Gestalt des Binärbaumes führt zu kleiner Pfadlänge?)
Siehe auch: Trie (Wikipädia)
Lösungsvorschlag: (korrigiert)
Zuerst mal einige Überlegungen:
Die optimale Form scheint ein (balanzierter) Binärbaum zu sein. Die Entfernung des Endknotes bis zur Wurzel entspricht bei vollständig gefülltem Baum der 2-er Potenz der Endknoten, jeder Knoten darüber ist einen Schritt weiter entfernt. Die Knotenmenge N muß gerade sein.
Sind nur die Endknoten (Blätter) gefüllt, wäre der optimale Wert x eine 2-Potenz, d.h. .
Sind auch alle Zwischenknoten gefüllt, wäre die Knotenmenge N Knoten + Wurzel = N +1 und die Anzahl der Endknoten (N+2)/2. Beispiel 8 Endknoten, dann 4+2 Zwischenknoten gibt 14 Knoten (ohne Wurzel) (Def. Trie lt. Wikipedia). Da die Angabe was ein Trie ist, so spezifiziert wurde, daß nor die Blätter gefüllt sind, ist die Überlegung bei diesem Beispiel hinfällig.
Gesucht ist der minimale Weg zu allen Endknoten. Das müßte die Pfadlänge für alle Endknoten einer 2-er Potenz der entsprechende Potenzwert * Anzahl der Knoten sowie für die restlichen Knoten (Potenzwert +1) * restl. Endknoten sein.
Beispiel:
N = 16. Anzahl der Endknoten -1 +2 = 7+ 2 = 9 da ein Knoten dieser Reihe noch 2 Blätter hat. Die Anzahl der Verbindungen zu 7 Knoten ist 3 Schritte, zu 2 Knoten 4 Schritte.
Lt. Urbanek hat ein Trie N = 2 Blätter, so ist die Pfadlänge 2*1 = 2 N = 3 Blätter, so ist die Pfadlänge 2*2+1 = 5 N = 4 Blätter, so ist die Pfadlänge 4*2 = 8
Hat der Trie die Tiefe i, so ist die Pfadlänge zu jedem Blatt i und die gesamte Pfadlänge N*i. Weitere angehängte Blätter erhöhen die Pfadlänge für diese um jeweils 1. Der Baum ist dann optimal, wenn sich die Pfadlängen um nicht mehr als 1 unterscheiden.
Hinsichtlich Formel siehe auch Vorschlag unten.
Hapi
Noch ein Vorschlag:
Setzen wir voraus, der Baum ist balanziert. Sei N = Anzahl Knoten, P = Pfadlänge, i = Tiefe.
Zuerst schauen wir auf einen Baum mit 2^n Knoten: Tiefe der Baum ist eigentlich das "n" hier, also den Exponent von 2! Also N = 2^n = 2^i, daraus folgt => i = log2(N), und daraus folgt => für alle N = 2^n: P = (log2(N))*N
Jetzt, wie modifizieren wir das, damit wir mit anderen Anzahle von Knoten umgehen können? Zuerst finden wir den nächst-kleineren Wert von N, dass gleich 2^n ist. Nennen wir ihn N1. Also N1 = grösste 2^n <= N. Dann bezeichnen wir die Anzahl der Restknoten als "R", also R = N - N1.
Die Gesamtpfadlänge für alle Blättern in der kleinere von den zwei Tiefen (dh die N1 Tiefe dh = log2(N1)) ist:
(log2(N1))*(N1-R)
denn wir müssen die R Blätter subtrahieren, weil sie zu Innenknoten gemacht wurden.
Die nächst-hochste Tiefe, wo die Restliche Blättern liegen, ist gleich den nächst-grössten Exponent von 2, was wir mit log2(N1)+1 finden. Und die Anzahl von diesen Restlichen Blättern ist eigentlich nicht R, sondern 2R, weil wir müssen auch die verloren-gegangenen Knoten von der unteren Tiefe wieder hineinbringen. Also, die Gesamtpfadlänge für die Restlichen Blättern (in der grösseren Tiefe) ist:
(log2(N1)+1)*2R
Die Gesamtpfadlänge für alle Blättern zusammen dann, ist:
P = (log2(N1))*(N1-R) + (log2(N1)+1)*2R
und weil R = N-N1 ist, können wir dass als
P = (log2(N1))*(N1 - (N - N1)) + (log2(N1)+1)*2(N-N1) = (log2(N1))*(2*N1 - N) + (log2(N1)+1)*2(N - N1)
schreiben.
Wenn wir das ausmultiplizieren, kriegen wir:
(log2(N1))*2*N1 - (log2(N1))*N + (log2(N1))*2*N - (log2(N1))*2*N1 + 2N - 2N1
Vereinfacht, das ist:
P = (log2(N1))*N + 2(N-N1)
-Mike