Explain any two rotations performed on an AVL tree with the he* of example.

QuestionsExplain any two rotations performed on an AVL tree with the he* of example.
manish.mishraPublished on: 6/21/2021 2:47:09 PM



1 Answers
Answer is under review.

AVL Tree-

  • AVL trees are special kind of binary search trees.
  • In AVL trees, height of left subtree and right subtree of every node differs by at most one.
  • AVL trees are also called asself-balancing binary search trees.

Example-

Following tree is an example of AVL tree-


This tree is an AVL tree because-

  • It is a binary search tree.
  • The difference between height of left subtree and right subtree of every node is at most one.

Following tree is not an example of AVL Tree-


AVL Tree Operations-

Like BST Operation commonly performed operations on AVL tree are-

  1. Search Operation
  2. Insertion Operation
  3. Deletion Operation

Case-01:

  • After the operation, the balance factor of each node is either 0 or 1 or -1.
  • In this case, the AVL tree is considered to be balanced.
  • The operation is concluded.

Case-02:

  • After the operation, the balance factor of at least one node is not 0 or 1 or -1.
  • In this case, the AVL tree is considered to be imbalanced.
  • Rotations are then performed to balance the tree.

AVL Tree Rotations-

Kinds of Rotations-

There are 4 kinds of rotations possible in AVL Trees-

  1. Left Rotation (LL Rotation)
  2. Right Rotation (RR Rotation)
  3. Left-Right Rotation (LR Rotation)
  4. Right-Left Rotation (RL Rotation)

Cases Of Imbalance And Their Balancing Using Rotation Operations-

Case-01:


Case-02:


Case-03:


Case-04:


image widget