AVL Tree

Introduction of AVL Tree

• The AVL tree is named after its two Soviet Union inventors, Georgy Adelson-Velsky and Evgenii Landis, who published it in their paper “An algorithm for the organization of information” in 1962.
• The AVL tree is also called Self Balancing BST.

• Tree Rotation :

  • Tree rotation is an operation performed on an AVL tree that changes the structure of the tree without interfering the order of the elements.
  • A tree rotation moves one node up in the tree and one node down at a time.
  • It is used to change the shape of the tree for rebalancing, and in particular to decrease its height by moving smaller subtrees down and larger subtrees up.
  • Tree rotation operation improved the performance of tree operations such as searching, insertion, deletion, etc.
  • This tree applies tree rotation operation automatically/dynamically.
  • There are the following types of tree rotation –
    • LL Rotation
    • RR Rotation
    • LR Rotation
    • RL Rotation

• Balance Factor(bf) :

  • The balance factor of an AVL tree is the difference in heights of its two subtrees i.e. left and right subtree from their root.
  • The bf is calculated as, bf= (hL – hR) here hL=height of left subtree, hR=height of right subtree.
  • The value of the balance factor (bf) of a height-balanced/AVL tree may take on one of the values from -1, 0, +1.

Definition

• An AVL tree is an automatic self-balancing binary search tree in which each node maintains extra information (called a balance factor)using the tree rotation technique.

Properties

• In this tree, the heights(h) of the two child subtrees of any node are either the same or differ by at most one. If at any time they differ by more than one, rebalancing is required and done using the concept of Balance Factor concept to restore the self-balanced property.
• All the nodes in this tree store their own balance factor value either -1, 0, or +1.
• Rebalancing in this tree is done by Tree Rotation.
• If the height of the AVL tree is h, the maximum number of nodes can be 2^h+1 – 1.
• The minimum number of nodes(n) in this tree with height h can be N(h) = N(h-1) + N(h-2) + 1

• The height or depth of the AVL tree is O(log n).
• The insertion and Deletion time complexity in this tree is O(log n). 
• The searching time complexity of this tree is O(n).

Advantages

• It has a faster and better search time.
• It is simple to implement.
• The structure or height of the AVL tree is always balanced.
• This tree gives better search time complexity than Binary Search trees.
• This tree has self-balancing capabilities.

Disadvantages

• Each node of this tree contains extra information as a balance factor.
• Tree rotation and Self-balancing in this tree is an expensive operation.
• Insertion and Deletion operation takes comparatively more time to complete the operation.

Use/Application

• Used extensively in database applications.