12/1/2010

AVL Trees

An AVL tree is a binary search tree with a balance
condition.

AVL is named for its inventors: Adel’son-Vel’skii and
Landis

AVL tree approximates the ideal tree (completely
balanced tree).

AVL Tree maintains a height close to the minimum.

Definition:
An AVL tree is a binary search tree such that
for any node in the tree, the height of the left and
right subtrees can differ by at most 1.

1
 12/1/2010

Figure 19.21
Two binary search trees: (a) an AVL tree; (b) not an AVL tree (unbalanced
nodes are darkened)

Figure 19.22
Minimum tree of height H

2
 12/1/2010

Properties

The depth of a typical node in an AVL tree is
very close to the optimal log N.

Consequently, all searching operations in an
AVL tree have logarithmic worst-case bounds.

An update (insert or remove) in an AVL tree
could destroy the balance. It must then be
rebalanced before the operation can be
considered complete.

After an insertion, only nodes that are on the
path from the insertion point to the root can
have their balances altered.

Rebalancing

Suppose the node to be rebalanced is X. There
are 4 cases that we might have to fix (two are the
mirror images of the other two):
1. An insertion in the left subtree of the left child of X,
2. An insertion in the right subtree of the left child of X,
3. An insertion in the left subtree of the right child of X, or
4. An insertion in the right subtree of the right child of X.

Balance is restored by tree rotations.

3
 12/1/2010

Balancing Operations: Rotations

Case 1 and case 4 are symmetric and
requires the same operation for balance.

Cases 1,4 are handled by single rotation.

Case 2 and case 3 are symmetric and
requires the same operation for balance.

Cases 2,3 are handled by double rotation.

Single Rotation
 A single rotation switches the roles of the parent
and child while maintaining the search order.
 Single rotation handles the outside cases (i.e. 1
and 4).
 We rotate between a node and its child.

Child becomes parent. Parent becomes right child
in case 1, left child in case 4.
 The result is a binary search tree that satisfies
the AVL property.

4
 12/1/2010

Figure 19.23
Single rotation to fix case 1: Rotate right

Figure 19.26
Symmetric single rotation to fix case 4 : Rotate left

10

5
 12/1/2010

Figure 19.25
Single rotation fixes an AVL tree after insertion of 1.

11

Example

Start with an empty AVL tree and insert
the items 3,2,1, and then 4 through 7 in
sequential order.

12

6
 12/1/2010

Example

Start with an empty AVL tree and insert
the items 3,2,1, and then 4 through 7 in
sequential order.

Answer:

2 6

1 3 5 7

13

Analysis
 One rotation suffices to fix cases 1 and 4.
 Single rotation preserves the original height:

The new height of the entire subtree is exactly the
same as the height of the original subtree before
the insertion.
 Therefore it is enough to do rotation only at the
first node, where imbalance exists, on the path
from inserted node to root.
 Thus the rotation takes O(1) time.
 Hence insertion is O(logN)

14

7
 12/1/2010

Double Rotation

Single rotation does not fix the inside
cases (2 and 3).

These cases require a double rotation,
involving three nodes and four subtrees.

15

Figure 19.28
Single rotation does not fix case 2.

16

8
 12/1/2010

Left–right double rotation to fix case 2

Lift this up:
first rotate left between (k1,k2),
then rotate right between (k3,k2)

17

Left-Right Double Rotation

A left-right double rotation is equivalent to a
sequence of two single rotations:

1st rotation on the original tree:
a left rotation between X’s left-child and grandchild

2nd rotation on the new tree:
a right rotation between X and its new left child.

18

9
 12/1/2010

Figure 19.30
Double rotation fixes AVL tree after the insertion of 5.

19

Right–Left double rotation to fix case 3.

20

10
 12/1/2010

Example

Insert 16, 15, 14, 13, 12, 11, 10, and 8, and 9
to the previous tree obtained in the previous
single rotation example.

2 6

1 3 5 7

21

Example

Insert 16, 15, 14, 13, 12, 11, 10, and 8, and 9
to the previous tree obtained in the previous
single rotation example.

Answer:
7

4 13

2 6 11 15

1 3 5 9 12 14 16

8 10

22

11
 12/1/2010

Node declaration for AVL trees

template <class Comparable>
class AvlTree;

template <class Comparable>

class AvlNode {
Comparable element;
AvlNode *left;
AvlNode *right;
int height;

AvlNode(const Comparable & theElement, AvlNode *lt,

AvlNode *rt, int h=0)
:element(theElement), left(lt),
right(rt), height(h) { }
friend class AvlTree<Comparable>;
};

23

Height
template class <Comparable>
int AvlTree<Comparable>
::height(AvlNode<Comparable> *t) const {

return t == NULL ? -1 : t->height;

}

24

12
 12/1/2010

Single right rotation

/**
* Rotate binary tree node with left child.
* For AVL trees, this is a single rotation for case 1.
* Update heights, then set new root.
*/
template <class Comparable>
void AvlTree<Comparable>
::rotateWithLeftChild(AvlNode<Comparable> * & k2) {

AvlNode<Comparable> *k1 = k2->left;

k2->left = k1->right;
k1->right = k2;
k2->height = max(height(k2->left), height(k2->right))+1;
k1->height = max(height(k1->left), k2->height) + 1;
k2 = k1;
}

25

Double Rotation
/**
* Double rotate binary tree node: first left child.
* with its right child; then node k3 with new left child.
* For AVL trees, this is a double rotation for case 2.
* Update heights, then set new root.
*/
template <class Comparable> void AvlTree<Comparable>
::doubleWithLeftChild(AvlNode<Comparable> * & k3) {

rotateWithRightChild(k3->left);
rotateWithLeftChild(k3);
}

26

13
 12/1/2010

/* Internal method to insert into a subtree.

* x is the item to insert.
* t is the node that roots the tree.
*/
template <class Comparable>
void AvlTree<Comparable>
::insert(const Comparable & x, AvlNode<Comparable> * & t) const {

if(t == NULL)
t = new AvlNode<Comparable>(x, NULL, NULL);
else if(x < t->element) {
insert(x, t->left);
if(height(t->left) - height(t->right) == 2)
if(x < t->left->element)
rotateWithLeftChild(t);
else
doubleWithLeftChild(t);
}
else if(t->element < x) {
insert(x, t->right);
if(height(t->right) - height(t->left) == 2)
if(t->right->element < x)
rotateWithRightChild(t);
else
doubleWithRightChild(t);
}
else ; // Duplicate; do nothing
t->height = max(height(t->left), height(t->right)) + 1;
}

27

AVL Tree -- Deletion

Deletion is more complicated.

We may need more than one rebalance
on the path from deleted node to root.

Deletion is O(logN)

28

14