Introduction
AVL Tree is a kind of binary search tree. Different from binary search tree is, it is self-balanced. The heights of two child subtress of node differ by at most one. Because of this, another name of AVL Tree is height-balanced.
These are self-adjusting, height-balanced binary search trees and are named after the inventors: Adelson-Velskii and Landis. A balanced binary search tree has Theta(lg n) height and hence Theta(lg n) worst case lookup and insertion times. However, ordinary binary search trees have a bad worst case. When sorted data is inserted, the binary search tree is very unbalanced, essentially more of a linear list, with Theta(n) height and thus Theta(n) worst case insertion and lookup times. AVL trees overcome this problem.
Definitions
The height of a binary tree is the maximum path length from the root to a leaf. A single-node binary tree has height 0, and an empty binary tree has height -1. As another example, the following binary tree has height 3.
7
/ \\
3 12
/ / \\
2 10 20
/ \\
9 11
```An **AVL tree** is a binary search tree in which every node is **height balanced**, that is, the difference in the heights of its two subtrees is at most 1.
The **balance factor** of a node is the height of its right subtree minus the height of its left subtree.
i.e.
** B.F. = rightHeight - leftHeight**
An equivalent definition, then, for an AVL tree is that it is a binary search tree in which each node has a balance factor of -1, 0, or +1. Note that a balance factor of -1 means that the subtree is left-heavy, and a balance factor of +1 means that the subtree is right-heavy. For example, in the following AVL tree, note that the root node with balance factor +1 has a right subtree of height 1 more than the height of the left subtree. (The balance factors are shown at the top of each node.)
+1 (3-2)
30
/ \\
-1 (0-1) 0 (2-2)
22 62
/ / \\
0 +1 -1
5 44 95
\\ /
0 0
51 77
-1
100
/ \\
-2 -1
70 150
/ \\ / \\
+1 0 +1 0
30 80 130 180
/ \\ \\
0 -1 0
10 40 140
/
0
36
**Operations on AVL tree**
Inserting a New Item
--------------------
Deleting a node from AVL Tree
Deleting the node works the same way, when we delete the node, if it upsets the balance, it will have to re-balance. Eg. Consider the tree