AVL Tree

Rumman Ansari   Software Engineer   2023-03-27   6989 Share
☰ Table of Contents

Table of Content:

  • AVL tree is a height-balanced tree.
  • It is a self-balancing binary search tree.
  • AVL tree is another balanced binary search tree.
  • It was invented by Adelson-Velskii and Landis.
  • AVL trees have a faster retrieval.
  • It takes O(logn) time for addition and deletion operation.
  • In AVL tree, heights of left and right subtree cannot be more than one for all nodes.


    • avl tree

  • The above tree is AVL tree because the difference between heights of left and right subtrees for every node is less than or equal to 1.


    avl tree not

  • The above tree is not AVL because the difference between the heights of the left and right subtrees for 9 and 19 is greater than 1.
  • It checks the height of the left and right subtree and assures that the difference is not more than 1. The difference is called the balance factor.
‹ Previous -   Extended Binary Tree
‹ Next