Java Reference
In-Depth Information
AVL Tree is a balanced binary search tree.
Key
Point
Chapter 25 introduced binary search trees. The search, insertion, and deletion times for a
binary tree depend on the height of the tree. In the worst case, the height is
O
(
n
). If a tree
is
perfectly balanced
-i.e., a complete binary tree—its height is log
n
. Can we maintain a
perfectly balanced tree? Yes, but doing so will be costly. The compromise is to maintain a
well-balanced tree
—that is, the heights of every node's two subtrees are about the same. This
chapter introduces AVL trees. Web Chapters 40 and 41 introduce 2-4 trees and red-black trees.
AVL trees
are well balanced. AVL trees were invented in 1962 by two Russian computer
scientists, G. M. Adelson-Velsky and E. M. Landis (hence the name
AVL
). In an AVL tree,
the difference between the heights of every node's two subtrees is
0
or
1
. It can be shown that
the maximum height of an AVL tree is
O
(log
n)
.
The process for inserting or deleting an element in an AVL tree is the same as in a regular
binary search tree, except that you may have to rebalance the tree after an insertion or dele-
tion operation. The
balance factor
of a node is the height of its right subtree minus the height
of its left subtree. A node is said to be
balanced
if its balance factor is
-1
,
0
, or
1
. A node is
considered
left-heavy
if its balance factor is
-1
, and
right-heavy
if its balance factor is
+1
.
perfectly balanced tree
well-balanced tree
AVL tree
O
(log
n
)
balance factor
balanced
left-heavy
right-heavy
Pedagogical Note
For an interactive GUI demo to see how an AVL tree works, go to
www.cs.armstrong.edu/
liang/animation/web/AVLTree.html
,
as shown in Figure 26.1.
AVL tree animation on
Companion Website
F
IGURE
26.1
The animation tool enables you to insert, delete, and search elements.
After inserting or deleting an element from an AVL tree, if the tree becomes
unbalanced, perform a rotation operation to rebalance the tree.
Key
Point
If a node is not balanced after an insertion or deletion operation, you need to rebalance it. The
process of rebalancing a node is called
rotation
. There are four possible rotations: LL, RR,
LR, and RL.
rotation
Search WWH ::
Custom Search