Algorithms & Data Structures - Data Structures And Operations

Objectives
At the end of the class learner will be able to answer the :

Insert, delete, and process nodes in an AVL tree

Understand the operation of the AVL tree ADT

Write application programs using an AVL tree

AVL Tree

Introduction
In 1962, two Russian mathematicians, G.M Adelson-velskii and E.M Landis, created the balanced binary tree structure that is named after them-the AVL tree.

Definition
An AVL tree is a height-balanced binary search tree.

AVL Balance Factor:
The formula to calculate the height-balance is :
│ H_L – H_R │ <=1 Where H_L is the height of the left subtree and H_R is the height of the right subtree

The balance factor for any node in an AVL tree must be +1, or -1,we will use the descriptive identifiers

• LH for left hight(+1) to indicate that the left subtree is higher than the right subtree.
• EH for even high(0) to indicate that the subtrees are the same height, and
• RH for right high(-1) to indicate that the left subtree is shorter than the right subtree.

Example of an AVL tree



Balancing Trees
Whenever we insert or delete a node the tree is unbalance. To make it balance we have to perform the rotations either to the left or to the right.

There are four cases required to rebalance the tree they are:

1. Left of Left
2. Right of Right
3. Right of left
4. Left of right

Left of Left - Single Rotation right:

Right of Right - Single Rotation Left:

Right of Left - Double Rotation Right:

Left of Right - Double Rotation Right:

AVL tree Implementation

AVL Tree Insert:

AVL Tree Left Balance:

Rotate AVL Tree Right and Left:

AVL Tree delete: