Balanced Search Trees
AVL Trees
Balancing Binary Search Trees
• Many algorithms exist for keeping binary
search trees balanced
– Adelson-Velskii and Landis (AVL) trees (height-
balanced trees)
– Splay trees and other self-adjusting trees
– B-trees and other multiway search trees
2
AVL Trees
• An AVL tree is a binary
search tree that either is Unbalanced vs.
balanced:
empty or in which: 160 100
– Heights between left and
right subtrees differs by 100 200 80 160
only 1
– The left and right subtrees 80 120 40 90 120 200
are also AVL trees.
40 90 50
50
3
AVL Trees
• For each AVL tree node, the difference
between the heights of its left and right
subtrees is either -1, 0 or +1.
balanceFactor = height(left subtree) - height(right subtree)
– If balanceFactor is positive, the node is "heavy on
the left" since the height of the left subtree is
greater than the height of the right subtree.
– With a negative balanceFactor, the node is "heavy
on the right."
– A balanced node has balanceFactor = 0.
Balance can be maintained through
rotations
• Rotation: an adjustment Right rotation around
element 90
to the tree, around an
90
element, that maintains
the required ordering of 45 45 20 90
elements
20
5
AVL Trees (continued)
AVLTree
Balanced Binary Search Trees
For any right rotation around element x, the right
subtree of x’s left child becomes the left subtree of x.
x
Rotate right around y
100: y
100 x
?
z z
80 120
40 90
50
9
For any right rotation around element x, the right
subtree of x’s left child becomes the left subtree of x.
x
Here is a right rotation around
100:
y
y x
100 80
z z
80 120 40 100
40 90 50 90 120
50
Notice that 90 is now in the right
subtree.
10
There are four kinds of rotation:
1. A left rotation;
2. A right rotation;
3. A left rotation around the left child of an
element, followed by a right rotation around the
element itself;
4. A right rotation around the right child of an
element, followed by a left rotation around the
element itself.
11
Implementing the AVLTree Class
Implementing the AVLTree Class
(continued)
AVL Tree Rotations (continued)
• A single right rotation rotates the nodes so
that the left child (LC) replaces the parent,
which becomes a right child. In the process,
the nodes in the right subtree of LC (RGC) are
attached as a left child of P. This maintains the
search tree ordering since nodes in the right
subtree are greater than LC but less than P.
AVL Tree Rotations (continued)
singleRotateRight()
// perform a single right rotation for parent p
private static <T> AVLNode<T> singleRotateRight(
AVLNode<T> p)
{
AVLNode<T> lc = p.left;
p.left = lc.right;
lc.right = p;
p.height =
max( height( p.left ),
height( p.right ) ) + 1;
lc.height =
max( height( lc.left ),
lc.height ) + 1;
return lc;
}
AVL Tree Rotations (continued)
• A symmetric single left rotation occurs when
the new element enters the subtree of the
right outside grandchild. The rotation
exchanges the parent and right child nodes,
and attaches the subtree LGC as a right
subtree for the parent node.
AVL Tree Rotations (continued)
AVL Tree Rotations (continued)
• When a new item enters the subtree for an
inside grandchild, the imbalance is fixed with a
double rotation which consists of two single
rotations.
AVL Tree Rotations (continued)
Rotations summary
Elements not in the subtree of the
element rotated about are
unaffected by the rotation.
A rotation takes constant time.
Before and after a rotation, the tree is
still a binary search tree.
The code for a left rotation is symmetric
to the code for a right rotation:
Simply swap “left” and “right.”
21
Example - Building an AVL Tree
Example - Building an AVL Tree
(continued)
Example - Building an AVL Tree
(continued)
Example - Building an AVL Tree
(concluded)
Efficiency of AVL Tree Insertion
• A mathematical analysis shows that the
worst case running time for insertion is
O(log2n). The worst case for the difficult
deletion algorithm is also O(log2n).
