Aufwand Der Baumtraversierung
← Baumsuche | ● | Baumknoten EinfĂĽgen →
Die Höhe eines Baums entspricht der maximalen Pfadlänge.
Einen Baum nenn man vollständig, wenn alle Blätter dieselbe Pfadlänge besitzen.
Ein vollständiger binärer Baum mit der Höhe h hat $2^h-1$ Knoten.
Im Gegenzug hat ein (balancierter) binärer Baum die Höhe $log_2(k+1)$, wenn im Baum k Elemente gespeichert sind.
Dann ist bei einer Suchoperation die Anzahl der aufzusuchenden Baumknoten $log_2(k+1)$.
Im Vergleich dazu, ist bei linearen Listen ist die durchnittliche Anzahl der aufzusuchenden Elemente $\frac k2$.
Gegenüberstellung des Suchaufwands bei Listen und Bäumen:
| k | 1 | 16 | 128 | 1024 | 16384 | 131072 | 1048576 |
|---|---|---|---|---|---|---|---|
| Baum | 1 | 4 | 8 | 10 | 14 | 17 | 20 |
| Liste | 1 | 8 | 64 | 512 | 8192 | 65536 | 524288 |
Man sagt, dass die Laufzeitkomplexität (sog. Big-O Notation oder Laufzeit-Ordnung) der Baumsuche O(log k) ist.
Im Gegensatz dazu ist die Komplexität der Listensuche O(k).
Die Baumsuche ist der schnellste allgemeine Suchalgorithmus.
Der Suchaufwand steigt so langsam, dass er faktisch als konstant (d.h. unabhängig von k) angenommen werden kann.
Für Spezialfälle existieren schnellerer Implementierungen, insbesondere für eine eingeschränkte Anzahl von verschiedenen Elementen. Es existiert jedoch kein Algorithmus, der für eine unbeschränkte Anzahl von Elementen die Suche in echt konstanter Zeit durchführen würde.
← Baumsuche | ● | Baumknoten EinfĂĽgen →