AVL Tree

Valentsea
Total
0
Shares

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

Complexity




AVL Tree Applications

  • For indexing large records in databases
  • For searching in large databases
Total
0
Shares
Valentsea

Understanding Containerization and Virtualization

Virtualization and containerization are becoming essential elements of contemporary computing and software development in the fast-paced technological world…

You May Also Like