Bäume

Next: Bäume Up: Datenstrukturen Previous: double linked lists

Bei N Daten-Elemente, ist der Aufwand, diese in einer gelinkten Liste zu finden im Durchschnitt $\frac{N}{2}$ .
Bei einem balancierten Binärbaum ist der Aufwand lediglich log₂N.
Ein unbalancierter Binärbaum enspricht einer gelinkten Liste. Die Vorteile des Binärbaumes sind dabei nicht mehr gegeben.
Bsp.: ist N=15, so ist $\frac{N}{2} = 7.5$ und log₂N ca. 4.

$\begin{figure} \begin{center} \leavevmode \epsfxsize=16cm \epsffile {sample-tree.eps} \end{center}\end{figure}$

Next: Bäume Up: Datenstrukturen Previous: double linked lists