AVL Trees in Data Structures

Ratings:
(4)
Views:1074
Banner-Img
  • Share this blog:

AVL Trees

One of the more popular balanced trees, known as an AVL tree in Data Structures, was introduced in 1962 by Adelson-Velski and Landis

Definition:

An empty binary search tree is an AVL tree. If T is a non empty binary search tree with T2 and TR as its left and right sub trees, The T is an AVL tree iff.

  • T2 and TR are AVL trees and
  • | hL – hR | < =1 where hL and hR are the heights of TL and T respectively

                                                                Or An Avl trees is a binary search tree in which for every node in the tree, The height of the left and right Sub trees differ by at most1. 64     hL – hR =1 This is AVL Tree   65     hL – hR =2 This is not AVL Tree 66       This is also a AVL tree hL = Height of left sub tree =2 |hl – hR |=|2-3|=|- 1|=1 | hL –hR| <=1     The difference between heights at left sub tree and right sub tree is called balancing Factor of a node.   Importance of Rotations :

  • The insert and delete operations of AVL tree are the same as binary search tree (BST)
  • Since an insertion(deletion) involve adding (deleting) a tree node, this can only increase (decrease) the heights of same sub tree(s) by 1
  • Thus, the AVL tree property may be violated
  • If the AVL tree property is violated ata node x, it means that the height of left(x) and right(x) differ by exactly 2
  • After the insertion or deletion operations, we need to examine the tree and see if any node violates the AVL tree property
  • If the AVL tree property is violated at node so, single or double rotation will be applied to x to restore the AVL tree property.
  • Rotation will be applied in a bottom up manner starting at the place of insertion(deletion)
  • Thus when we perform a rotation at x, The AVL tree property is restored at all proper descendants of x.

This fact is important.   Single Rotations : RR rotation :- [ Right – Right Rotation] 67 68   69    

 Double Rotations :

70  

LR Rotaion  c Left Right Rotation :

  71         Ex : Example of RL Rotation : 72    

Ex: Example of LR Rotation:

  72   Example: Construct an AVL tree with the following elements 3,2,1,4,5,6,716,15,14 72 72 72    

Insertion :

  • Trace from path of inserted leaf towards the root, and check if the AVL tree property is violated perform rotation if necessary
  • For insertion, once we perform (Single or doubles) rotation at a node x, The AVL tree property is already restored. We need not to perform any rotation at any ancestor of X.
  • Thus one rotation is enough to restore the AVL tree properly
  • There are 4 different cases (actually 2) , so don’t mix up them
  • The time complexity to perform rotation is 0(1)
  • The time completely to insert, and find a node that violates the AVL property is dependent on the height of the tree, which is 0(log(n))
  • So insertion takes o(log(n))

 

Deletion :

  • Delete a node X as in ordinary BST(Note that X is either a leaf or X has exactly one child)
  • Check and restore the AVL tree property.
  • Trace from path of deleted node towards the root and check if the AVL tree property is violated
  • Similar to an insertion operation, there are four cases to restore the AVL tree property.
  • The only difference from insertion is that after we perform a rotation at x, we may have to perform, a rotation at some ancestors of x, It may involve several rotations.
  • Therefore, we must continue to trace the path until we reach the root.
  • The time complexity to delete a node is dependent on the height of the tree, which is also o(log(n))

 

You liked the article?

Like : 0

Vote for difficulty

Current difficulty (Avg): Medium

Recommended Courses

1/15

About Author
Authorlogo
Name
TekSlate
Author Bio

TekSlate is the best online training provider in delivering world-class IT skills to individuals and corporates from all parts of the globe. We are proven experts in accumulating every need of an IT skills upgrade aspirant and have delivered excellent services. We aim to bring you all the essentials to learn and master new technologies in the market with our articles, blogs, and videos. Build your career success with us, enhancing most in-demand skills in the market.


Stay Updated


Get stories of change makers and innovators from the startup ecosystem in your inbox