In this tutorial, you will learn what an avl tree is. Also, you will find working examples of various operations performed on an avl tree in C++ and Python.
AVL tree is a self-balancing binary search tree in which each node maintains extra information called a balance factor whose value is either -1, 0 or +1.
AVL tree got its name after its inventor Georgy Adelson-Velsky and Landis.
Balance Factor
Balance factor of a node in an AVL tree is the difference between the height of the left subtree and that of the right subtree of that node.
Balance Factor = (Height of Left Subtree – Height of Right Subtree) or (Height of Right Subtree – Height of Left Subtree)
The self balancing property of an avl tree is maintained by the balance factor. The value of balance factor should always be -1, 0 or +1.
Complexities of Different Operations on an AVL Tree
AVL Tree Applications
- For indexing large records in databases
- For searching in large databases
