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 redblack 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.
© John Morris, 1998