This content originally appeared on DEV Community and was authored by Muhammad Usman
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
AVL Tree Applications
- For indexing large records in databases
- For searching in large databases
This content originally appeared on DEV Community and was authored by Muhammad Usman
Muhammad Usman | Sciencx (2023-03-24T05:38:33+00:00) AVL Tree. Retrieved from https://www.scien.cx/2023/03/24/avl-tree/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.