Page 141 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes sub-tree), balanced (both sub-trees are the same height) or right-heavy (the height of the right
sub-tree is 1 greater than the left sub-tree). If the balance would be destroyed by an insertion, a
rotation is performed to correct the balance.
Let us consider the following AVL tree in which a node has been inserted in the left subtree of
node 1.

2

1

This insertion causes its height to become 2 greater than node-2’s right sub-tree. A right-rotation
is performed to correct the imbalance, as shown below.

1

1

AVL Rotation: A tree rotation can be an intimidating concept at first. You end up in a situation

where you’re juggling nodes, and these nodes have trees attached to them, and it can all become

confusing very fast. I find it helps to block out what’s going on with any of the subtrees which
are attached to the nodes you’re fumbling with, but that can be hard.

Left Rotation (LL)

Imagine we have this situation:
a
\
b
\

c

136 LOVELY PROFESSIONAL UNIVERSITY