DEV Community

Cover image for AVL Tree
Muhammad Usman
Muhammad Usman

Posted on

AVL Tree

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.


Python:

C++:


Complexities of Different Operations on an AVL Tree

Complexity


AVL Tree Applications

  • For indexing large records in databases
  • For searching in large databases

Top comments (0)