|
Data Structures and Algorithms
|
| Unbalanced Trees
|
If items are added to a binary tree in order
then the following unbalanced tree
results:
.
The worst case search of this tree may require up to
n comparisons.
Thus a binary tree's worst case searching time is
O(n).
Later, we will look at red-black trees,
which provide us with a strategy for avoiding this
pathological behaviour.
- Balanced Binary Tree
- Binary tree in which each leaf is the same distance from the
root.
© 
, 1998