Java Reference
In-Depth Information
I
n Chapter 25, you saw that the operations on a binary search tree are O(log
n
) if the tree is balanced.
Unfortunately, the add and remove operations do not ensure that a binary search tree remains balanced.
This chapter will consider search trees that maintain their balance, and hence their efficiency.
Our goal is to introduce you to several types of balanced search trees and compare them. We
will discuss the algorithms that add entries to a search tree while retaining its balance. We also will
show you how to search the trees. We will not, however, cover the algorithms that remove entries,
leaving this topic for a future course.
The entries in a tree are usually objects, but to make the pictures of trees clear and concise, we
will show the entries as integers.
27.1
Segment 23.28 in Chapter 23 showed that you can form several differently shaped binary search trees
from the same collection of data. Some of these trees will be balanced and some will not. You could
take an unbalanced binary search tree and rearrange its nodes to get a balanced binary search tree.
Recall that every node in a balanced binary tree has subtrees whose heights differ by no more than 1.
This idea of rearranging nodes to balance a tree was first developed in 1962 by two mathema-
ticians, Adel'son-Vel'skii and Landis. Named after them, the
AV L t r e e
is a binary search tree that
rearranges its nodes whenever it becomes unbalanced. The balance of a binary search tree is upset
only when you add or remove a node. Thus, during these operations, the AVL tree rearranges nodes
as necessary to maintain its balance.
For example, Parts
a
,
b
, and
c
of Figure 27-1 show a binary search tree as we add 60, 50, and 20 to
it. After the third addition, the tree is not balanced. An AVL tree would rearrange its nodes to restore bal-
ance, as shown in Figure 27-1d. This particular reorganization is called a
right rotation
, since you can
imagine the nodes rotating about 50. If we now add 80 to the tree, it remains balanced, as Figure 27-2a
shows. Adding 90 disrupts the balance (Figure 27-2b), but a
left rotation
restores it (Figure 27-2c).
Here the rotation is about 80. Notice that after each rotation, the tree is still a binary search tree.
In discussing balance, we sometimes will mention a
balanced node
. A node is balanced if it is
the root of a balanced tree, that is, if its two subtrees differ in height by no more than 1.
VideoNote
AVL trees
27.2
Right rotations.
Let's examine the previous rotations in more detail. Figure 27-3a shows a subtree
of an AVL tree that is balanced. The heights of the subtrees
T
1
,
T
2
, and
T
3
are the same. An addition
that occurs in the left subtree
T
1
of node
C
will add a leaf to
T
1
. Suppose that such an addition increases
the height of
T
1
by 1, as Figure 27-3b shows. The subtree rooted at node
N
is now unbalanced.
FIGURE 27-1
After inserting (a) 60; (b) 50; and (c) 20 into an initially empty
binary search tree, the tree is not balanced; (d) a corresponding
AVL tree rotates its nodes to restore balance
(a)
(b)
(c)
(d)
60
60
60
50
50
50
20
60
20
Balanced
Unbalanced
