384 CHAPTER 6 Graph Theory
The efficiency of searching a binary search tree depends on the form of the tree. In
Figure 6.47, we see extreme cases for a binary search tree with five vertices.(a) (b)Figure 6.47 Two binary search trees with five vertices.The difficulty with the binary search tree shown in Figure 6.47(a) is that its height
is four. On the other hand, the height of the binary search tree in Figure 6.47(b) is only
two. These two facts say that a search using the tree shown in Figure 6.47(a) can require
five comparisons while a search using the tree shown in Figure 6.47(b) will require at most
three comparisons in any search. To be efficient, algorithms using a binary search tree must
deal with the problem of keeping the height of the tree as small as possible. This is called
"balancing" the tree, and it is often a major implementation problem. One technique for
dynamic balancing of a rooted tree involves operations called rotations. The family of
A-V-L trees use rotations to keep the tree "balanced." An A-V-L tree rebalances a vertex
when its left subtree has height two greater than the height of its right subtree. An example
of this procedure is shown in Figure 6.48.10
666 /1% heights (^4 10 10)
15 7
7 height 2 height (^2) height 2 e height
height 3 2 15 2 7 15
2 STEP 1 STEP 2
Balanced
Figure 6.48 Rebalancing an A-V-L tree.
When building a binary search tree one element at a time, the detection of a vertex
having a left subtree with height two greater than the height of the other subtree causes
a balancing action to take place. In this example, vertex 10 has a left subtree of height
three and a right subtree of height one. Step 1 in Figure 6.48 is to move the vertex that is
unbalanced (10) down one level in the tree and its left child (6) up one level to become
its parent. The problem now is that vertex 6 has three children! We observe, however, that
when vertex 10 was moved down one level, it lost its left child! Therefore, we can now
make vertex 7 the left child of vertex 10 (see Step 2 in Figure 6.48), and the tree becomes a
binary search tree with no vertex having a left subtree with height more than one different
from the height of its right subtree.