AVL balanced trees and Balancing algorithm

AVL Tree

An AVL tree is a binary search tree with a balance condition such that for every internal node v of Tree 'T', the heights of the children of v can differ by at most 1.

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.

In an AVL tree, every node maintains an extra information known as balance factor.

Every sub-trees is an AVL tree.

Balance factor of a node is the difference between the heights of left and right subtrees of that node. The balance factor of a node is calculated either height of left subtree - height of right subtree (OR) height of right subtree - height of left subtree.

Balance factor = heightOfLeftSubtree - heightOfRightSubtree

In an AVL tree, the balance factor is either -1, 0 or +1.

Here, every node satisfies the balance factor condition. So, this tree is an AVL tree.

Height of an AVL Tree

If we denote N_hthe minimum no. of nodes in an AVL tree of height h

The bases can be defined as N₀ = 0, N₁ = 1, N₂= 2

N_h = N_h-1 + N_h-2+ 1 (by recursive relation)

or, N_h>= N_h-1+ N_h-2+ 1

>= 2N_h-2+ 1

>= 1+ 2(1 + 2N_h-4)

= 1 + 2 + 2²N_h-4

>= 1 + 2 + 2²+ 2³N_h-6

_...

>= 1 + 2 + 2²+ 2³+ ... + 2^h/2

= 2^h/2+ 1

or, 2^h/2 - 1 <= n

h/2 <= log₂(n+1)

h <= 2log₂(n+1)

AVL Tree Algorithms

1. Insert a newnode into an AVL tree by using the usual binary search tree insertion algorithm.

2. Trace the path from the new leaf towards the root. For each node x encountered, check if height of left(x) and right(x) differ by at most 1.

if yes: proceed to parent(x)

if not: restructure the tree by doing either single or double rotations.

When the node is imbalanced, consider the imbalanced node and two nodes immediately below this node on the path back to the newnode.

If these three nodes lie in a straight line, apply a single rotation to the imbalanced node.

If these three nodes lie in dog-tail pattern, apply a double rotation to the imbalanced node.

Rotations in AVL tree are classified as:

1. Single Rotation

a) Left Rotation (LL Rotation)

b) Right Rotation (RR Rotation)

2. Double Rotation

a) Left Right Rotation (LR Rotation)

b) Right Left Rotation (RL Rotation)

SingleLeft Rotation (LL Rotation)

In this rotation, every node moves one position to left from the current position. Let us consider the following insertions into an AVL Tree to understand LL rotation:

Here, at first the tree is imbalanced. To balanced it LL rotation is done which moves nodes one position to the left. Thus,the tree is balanced after the LL rotation.

Single Right Rotation (RR Rotation):

In this rotation, every node moves one position to the right from the current position. Lets consider the following example:

Here, at first, the tree is imbalanced. To balanced it RR rotation is done which moves nodes one position to the right. Thus, the tree is balanced after theRR rotation.

Left Right Rotation (LR Rotation

The LR Rotation involves the combination of a LL Rotation followed by a RR Rotation. Thus, first every node moves one position to left and one position to right from the current position. Lets consider the following example:

Here, at first, the tree is imbalanced. So, LL rotation is done at the node '1' followed by the RR Rotation at node '3' giving a balanced tree.

Right Left Rotation (RL Rotation)

The RL Rotation involves the combination of a RR Rotation followed by a LL Rotation. Thus, first, every node moves one position to rightand one position to leftfrom the current position. Lets consider the following example:

Here, at first, the tree is imbalanced. So, RRrotation is done at the node '3' followed by the LL Rotation at node '1' giving a balanced tree.

A Complete Example:

Construction of AVL trees from numbers 1 to 8.

References:

1.http://btechsmartclass.com/DS/U5_T2.html

2. Y. Langsam, M. J. Augenstein and A. M Tenenbaum, “Data Structures using C and C++

3.R. L. Kruse, B. P. Leung, C. L. Tondo, “Data Structure and Program design in C”