AVL Trees

Dr. Hakim Mellah

Department of Computer Science & Software Engineering
Concordia University, Montreal, Canada

These slides has been extracted, modified and updated from original slides of :
• Data Structures and Algorithms in Java, 5th edition. John Wiley& Sons, 2010. ISBN 978-0-470-38326-1.
• Dr. Hanna’s slides (http://aimanhanna.com/concordia/comp352/index.htm)

Copyright © 2010 Michael T. Goodrich, Roberto Tamassia

All rights reserved
 Coverage
❑ Section 10.2: AVL Trees

6
v
3 8
z
4

AVL trees are named after its their Soviet inventors, G. M. Adelson-Velskii and E. M. Landis, in
1962. AVL Trees were the first invented self-balancing tress.
AVL Trees 2
Performance of Binary Search Trees

❑ A binary search tree should be an efficient data

structure for map implementation.

❑ However, as seen, binary search trees may have

O(n) in the worst case, which is not any better
than list-based or array-based map
implementation.

❑ That problem is caused by the possibility that

the nodes may be arranged such that n = h + 1,
where h is the height of the tree.
AVL Trees 3
AVL Tree Definition
❑ The performance problem
of binary search trees can
be corrected using AVL 4
44
trees.
2 3
17 78
❑ AVL Trees are balanced
1 2 1
Trees. 32 50 88
1 1
❑ An AVL Tree is a binary 48 62
search tree such that for
every internal node v of T,
the heights of the children
of v can differ by at most 1; An example of an AVL tree where the
this is referred to as the heights are shown next to the nodes
Height-Balance
Property. AVL Trees 4
 n(2) 3

4 n(1)

Height of an AVL Tree

❑ Any binary search tree that satisfies the height-balance
property is said to be an AVL tree.

❑ AVL trees are named after their inventors (Adel’son Vel’skii

and Landis).

❑ Fact: The height of an AVL tree storing n keys is O(log n).

❑ Proof: Let us bound n(h): the minimum number of internal

nodes of an AVL tree of height h.
n(2) 3
❑ We can easily see that n(1) = 1 and n(2) = 2,
4 n(1)
since an AVL tree of height 1 must have at least 1
internal node and an AVL of height 2 must have at
least 2 internal nodes. AVL Trees 5
 n(2) 3

4 n(1)

Height of an AVL Tree

❑ Now, for n >= 3, an AVL tree of height h contains the root
node, and at minimum, one AVL subtree of height h-1 and
another of height h-2.

❑ That is, for n >= 3:

n(h) = 1 + n(h-1) + n(h-2)

❑ Knowing that n(h-1) > n(h-2), we get n(h) > 2n(h-2),

which indicates that: n(h) at least doubles each time h
increases by 2.

❑ So:
n(h) > 2n(h-2), n(h) > 4n(h-4), n(h) > 8n(h-6), … (by induction),
➔ n(h) > 2in(h-2i)
AVL Trees 6
 n(2) 3

4 n(1)

Height of an AVL Tree

➔ n(h) > 2in(h-2i), for any integer i such that h-2i >= 1.

❑ Recall that we already know n(1) and n(2).

❑ So, let us pick up i such that h – 2i is equal to either 1 or 2:
i = ceil(h/2) – 1

➔ n(h) > 2in(h-2i) ➔ n(h) > 2ceil(h/2) – 1 n(h- (2ceil(h/2)) +2)

➔ n(h) > 2ceil(h/2) – 1 n(h- (2ceil(h/2)) +2)
➔ n(h) > 2ceil(h/2) – 1 n(h- (ceil(h/2) + ceil(h/2)) +2)
➔ n(h) > 2ceil(h/2) – 1 n(h- (ceil(h/2) -1 + ceil(h/2) -1))
➔ n(h) > 2ceil(h/2) – 1 n(h- (2i)) ➔ n(h) >= 2ceil(h/2) – 1 n(1)
➔ n(h) >= 2ceil(h/2) – 1
AVL Trees 7
 n(2) 3

4 n(1)

Height of an AVL Tree

➔ n(h) >= 2ceil(h/2) – 1 ➔ n(h) >= 2h/2 – 1

➔ log n(h) > (h/2) -1

➔ h < 2 log n(h) + 2

❑ This implies that the height of an AVL tree storing n entries

can, at most, be 2 log n + 2.

❑ Thus the height of an AVL tree is O(log n).

❑ Consequently, a map implemented with an AVL tree runs in

O(log n).
AVL Trees 8
Insertion
❑ Insertion is as in a binary search tree (Always done
by expanding an external node), but additional
computations are needed afterwards.
❑ Example: put(54)
44 44

c=z
17 78 17 78
a=y

32 50 88 32 50 88

48 62 48 62
b=x

54
w
before insertion
AVL Trees 9
after insertion
Insertion
❑ Insertion adds the new node at a previously external node
then creates two external nodes to this new added node.

❑ This would hence increases the height of that part of the

tree which may violates the height-balance property,
resulting in the tree being unbalanced.

❑ Consequently, the tree may have to be “restructured” to

restore the height-balance.

❑ A balanced tree would have the difference (absolute

value) between the heights of its left and right children
being at most 1.

❑ NOTE: If a tree is balanced, then each of its internal

nodes (subtrees at these nodes) must be balanced as
well. AVL Trees 10
after insertion
Trinode Restructuring
❑ If the tree becomes unbalanced after the addition, then the
nodes in the path from this new node to the root have to be the
only involved nodes where the unbalance has occurred.

❑ Let w be the new added node causing the unbalance to occur.

❑ Let z be the first encountered node from w up towards the root
when the unbalance started to occur.
❑ Let y be the child of z with the higher height.
❑ Finally, let x be the child of y with the higher height.
5
44
2 z 4
17 78
1 3 y 1
32 50 88
1 2 x
48 62
1
w T3
Unbalanced, after put(54) 54

T0 T2
Trinode Restructuring
❑ We now need to rebalance the tree rooted at z. The rebalancing method is referred to as
trinode restructuring.

❑ Trinode restructuring starts by temporarily renaming x, y and z to a, b and c, where a

precedes b and b precedes c in an inorder traversal (see illustrative example).

❑ There are actually 4 possible ways for mapping x, y and z to a, b and c.

a=z a=z

b=y T0 c=y
T0
T1 c=x b=x

T3 T2 T3
T2
T1
c=z
c=z
a=y T3
b=y T3
b=x
a=x T2
T0 T1
T0
T1 T2
Trinode Restructuring
❑ Trinode restructuring rebalances the tree as follows:
1) Replace z with the node called b (that is, direct the edge heading to z from its parent to
b instead of z).

2) Take a and c and make them children of b.

3) Take the 4 subtrees (T0, T1, T2, and T3, which were the previous children of x, y and z)
and make them children of a and c.
 Maintain the inorder relationship between these 4 subtrees when placing them as the children of a and c.

➔ The trinode restructuring adjustments locally the balance of the originally unbalanced
subtree at the older node z, which actually results in the entire tree, globally,
becoming balanced again.

a=z
b=y b=y
T0
T1 a=z c=x
c=x
T0 T1 T2 T3
T3
T2
Trinode Restructuring
❑ The restructuring of the first two cases are referred to as single rotation (since
geometrically can be visualized as rotating y over z.

a=z single rotation

b=y b=y
T0
T1 a=z c=x
c=x
T0 T1 T2 T3
T3
T2

c=z
single rotation
b=y T3 b=y

a=x T2 a=x c=z

T0 T0 T1 T2 T3
T1
Trinode Restructuring
❑ The restructuring of the other two cases are referred to as double rotation (since
geometrically can be visualized as rotating x over y then rotating x over z.

a=z
double rotation
T0 c=y b=x

b=x a=z c=y

T2 T3 T0 T1 T2 T3

T1

c=z

a=y T3 double rotation

b=x
b=x
a=y c=z
T0 T1
T0 T1 T2 T3
T2
Insertion Example
5
44
2 c=z 4
17 78
1 3 a=y 1
32 50 88
1
2 b=x
48 62
1
w 54 T3
unbalanced... T2
T0
4
T1 44
2 3 b=x
17 62
a=y c=z
1 2 2
32 50 78
1 1 1
...balanced 48 54 88

T2

T0 T1 T3
AVL Trees 16
Removal
❑ Removal begins as in a binary search tree, which means that the
removed node will become an empty external node.
Consequently, however, its parent, w, may cause an imbalance.

❑ Example: 44 44

17 62 17 62

32 50 78 50 78

48 54 88 48 54 88

before deletion of 32 after deletion

AVL Trees 17
Rebalancing after a Removal
❑ Let z be the first unbalanced node encountered while travelling
up the tree from w. Also, let y be the child of z with the larger
height, and let x be the child of y with the larger height

❑ We perform restructure(x) to restore balance at z

62
a=z 44

44 78
w 17 62 b=y

17 50 88
50 78 c=x

48 54
48 54 88

AVL Trees 18
Rebalancing after a Removal
❑ Unfortunately, this restructuring may upset the balance of
another node higher in the tree. That is, locally adjusting the
tree does not guarantee the tree being adjusted globally.

❑ For instance, assume a node has height 6 with its children

having heights of 5 and 4, and the one with height 4 has
children with heights of 3 and 2. If the removal is taken from
the child with height 2, then that tree height becomes 1, which
is unbalanced with its sibling (having 3). The restructuring will
turn these two children to height 2, which is balanced, but this
will consequently change the height of their parent from 4 to 3,
causing further unbalance between this node (now having
height 3) and its sibling, which has height 5.

❑ Thus, we must continue checking for balance until the root of T

is reached, and readjust along the way if needed (which may
result in log n constructions in the worst case).
AVL Trees 19
AVL Tree Performance
❑ a single restructure takes O(1) time
◼ using a linked-structure binary tree
❑ get takes O(log n) time
◼ height of tree is O(log n), no restructures needed

❑ put takes O(log n) time

◼ initial find is O(log n)
◼ Restructuring up the tree, maintaining heights is O(1)
◼ However, we still need O(log n) to find out if restructuring is
needed
❑ remove takes O(log n) time
◼ initial find is O(log n)
◼ Restructuring up the tree, maintaining heights is O(log n)
AVL Trees 20