AVL Tree

AVL Tree

1. Introduction

   • Self balanced binary search tree
   • Balance factor of every node is either +1,0,-1
   • Balance factor=height of left subtree -height of right subtree

2. Application

   • Insertion: Insert new element into tree, check the balance factor, perform the suitable rotation
   • In all these cases, u will end up removing a leaf
     • Searching
     • Traversing
     • Deletion

3. Rotation

   • Single Rotation
     • Left Rotation: Every node moves to one position left
     • Right Rotation: Every node moves to one position right
   • Double Rotation
     • Left-Right Rotation: One single left rotation followed by one single right rotation
     • Right-Left Rotation: One single right rotation followed by a single left rotation