D a t a s t r u c t u r e s a n d a L g o r I t h m s Annotated Reference with Examples

O(n). By applying a balance condition we ensure that the worst case running
time of each common operation is O(log n). The height of an AVL tree with n
nodes is O(log n) regardless of the order in which values are inserted.
The AVL balance condition, known also as the node balance factor represents
an additional piece of information stored for each node. This is combined with
a technique that efficiently restores the balance condition for the tree. In an
AVL tree the inventors make use of a well-known technique called tree rotation.
h
h+1
Figure 7.1: The left and right subtrees of an AVL tree differ in height by at
most 1
54

---

CHAPTER 7. AVL TREE
55
1
2
3
4
5
Figure 7.2: Unbalanced binary search tree
2
4
5
1
3
4
5
3
2
1
a)
b)
Figure 7.3: Avl trees, insertion order: -a)1,2,3,4,5 -b)1,5,4,3,2

---

CHAPTER 7. AVL TREE
56
7.1
Tree Rotations
A tree rotation is a constant time operation on a binary search tree that changes
the shape of a tree while preserving standard BST properties. There are left and
right rotations both of them decrease the height of a BST by moving smaller
subtrees down and larger subtrees up.
14
24
11
8
2
8
14
24
2
11
Right
Rotation
Left
Rotation
Figure 7.4: Tree left and right rotations

---

CHAPTER 7. AVL TREE
57
1) algorithm LeftRotation(node)
2)
Pre: node.Right ! = ∅
3)
Post: node.Right is the new root of the subtree,
4)
node has become node.Right’s left child and,
5)
BST properties are preserved
6)
RightN ode ← node.Right
7)
node.Right ← RightN ode.Left
8)
RightN ode.Left ← node
9) end LeftRotation
1) algorithm RightRotation(node)
2)
Pre: node.Left ! = ∅
3)
Post: node.Left is the new root of the subtree,
4)
node has become node.Left’s right child and,
5)
BST properties are preserved
6)
Lef tN ode ← node.Left
7)
node.Left ← Lef tN ode.Right
8)
Lef tN ode.Right ← node
9) end RightRotation
The right and left rotation algorithms are symmetric. Only pointers are
changed by a rotation resulting in an O(1) runtime complexity; the other fields
present in the nodes are not changed.
7.2
Tree Rebalancing
The algorithm that we present in this section verifies that the left and right
subtrees differ at most in height by 1. If this property is not present then we
perform the correct rotation.
Notice that we use two new algorithms that represent double rotations.
These algorithms are named LeftAndRightRotation, and RightAndLeftRotation.
The algorithms are self documenting in their names, e.g. LeftAndRightRotation
first performs a left rotation and then subsequently a right rotation.

---

CHAPTER 7. AVL TREE
58
1) algorithm CheckBalance(current)
2)
Pre: current is the node to start from balancing
3)
Post: current height has been updated while tree balance is if needed
4)
restored through rotations
5)
if current.Left = ∅ and current.Right = ∅
6)