AVL Tree: Balanced Binary Search Tree
☰Fullscreen
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.
- 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.
- 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.
