AVL Trees

Properties

An AVL tree is a BST where the height of every node's left and right subtrees differ by at most 1. Another way to define AVL trees uses recursion: an AVL tree is a BST where the height of the root's left and right subtrees differ by at most 1, and the left and right subtrees are AVL trees.

In an AVL tree each node contains balance and height info. Both height and balance info are calculated from the leaves up. THe height is calculated as:

     height(leaf) = 1
     height(internal node) = 1 + max(height(left child), height(right child))

The balance of a node is calculated as:

     balance(leaf) = 0
     balance(internal node) = height(left child) - height(right child))

Here is a sample AVL tree with height and balance information:

Rebalancing

Nodes are inserted and deleted using the same algorithm as a standard BST. After inserting or deleting, the tree may be out of balance. In this case the balance at some node will be 2 or -2, because the height of the subtrees differs by 2. After inserting or deleting, every node from the point of insertion/deletion up to the root has its height and balance recomputed. During this process, if a node's new balance is 2 or -2, it needs to be rebalanced.

Rebalancing is done through rotation. Rotation shortens the taller subtree so the balance is restored. There are 4 different types of imbalances based on combinations of left and right subtrees. If the balance at a node is 2, that means the left subtree is taller. This is called an L imbalance. If the balance at a node is -2, that means the right subtree is taller. This is called an R imbalance. The steps required to rebalance depend on which of its subtrees needs to be shortened.

• LL: The balance at a node X is 2, meaning that its left subtree is taller. Also the balance at X's left child is 1, which means that the left subtree of the left child is taller.
• LR: The balance at a node X is 2, meaning that its left subtree is taller. Also the balance at X's left child is -1, which means that the right subtree of the left child is taller.
• RR: The balance at a node X is -2, meaning that its right subtree is taller. Also the balance at X's right child is -1, which means that the right subtree of the right child is taller.
• RL: The balance at a node X is -2, meaning that its right subtree is taller. Also the balance at X's left child is 1, which means that the left subtree of the right child is taller.

LL Rotation

An LL rotation is performed at X when X has a balance of 2 and X_L (the left child of X) has a balance of 1. The rotation performed is a single clockwise rotation around X by moving X_L up a level.

1. X becomes X_L's right child.
2. X_L's right child (T₂) becomes X's left child.
3. X_L is the new root of the subtree.

RR Rotation

An RR rotation is performed at X when X has a balance of -2 and X_R (the right child of X) has a balance of -1. The rotation performed is a single counter-clockwise rotation around X by moving X_R up a level.

1. X becomes X_R's left child.
2. X_R's left child (T₂) becomes X's right child.
3. X_R is the new root of the subtree.

LR Rotation

An LR rotation is performed at X when X has a balance of 2 and X_L (the left child of X) has a balance of -1. Two rotations are required: a counter-clockwise rotation around X_L and then a clockwise rotation around X.

Rotation 1 (counter-clockwise rotation around X_L moving X_LR up a level):

1. X_LR becomes left child of X.
2. X_L becomes left child of X_LR.
3. X_LR's left subtree (T_2L) becomes right subtree of X_L.
4. X_LR's right subtree (T_2R) remains the right subtree of X_LR.

Rotation 2 (clockwise rotation around X moving X_LR up a level):

1. X becomes X_LR's right child.
2. X_LR's right child (T_2R) becomes X's left child.
3. X_LR is the new root of the subtree.

RL Rotation

An RL rotation is performed at X when X has a balance of -2 and X_R (the right child of X) has a balance of 1. Two rotations are required: a clockwise rotation around X_R and then a counter-clockwise rotation around X.

Rotation 1 (clockwise rotation around X_R moving X_RL up a level):

1. X_RL becomes right child of X.
2. X_R becomes right child of X_RL.
3. X_RL's right subtree (T_2R) becomes left subtree of X_R.
4. X_RL's left subtree (T_2L) remains the left subtree of X_RL.

Rotation 2 (counter-clockwise rotation around X moving X_RL up a level):

1. X becomes X_RL's left child.
2. X_RL's left child (T_2L) becomes X's right child.
3. X_RL is the new root of the subtree.

Email Me | Office Hours | My Home Page | Department Home | MCC Home Page

© Copyright Emmi Schatz 2010