What’s AVL Tree
AVL tree has been named after two persons Adelson-Velskii and Landis. These two had devised a technique to make the tree balanced.
Let’s Start!
Let the input data for making binary tree: 3, 4, 5, 7, 9, 14, 15, 16, 17, 18, 20
We get following result from the input:
Problem
You can observe from the Fig. 1 that it has become a linked list.
And we know that the linked list searches are N/2, where N is number of nodes.
Solution
We have to make this BST balanced at every node, which in return known as AVL tree.
AVL tree searches are log(N) (log with base 2) which is far less than the searches in linked list.
The balance of a node in a binary tree is defined as the height of its left subtree minus height of its right subtree.
If we weigh the BST of Fig 1 on the balance, from the root, both of its sides will be equal as the number of nodes in the right subtree and left subtree are equal. If you have such a balanced binary search tree with one lakh nodes, there will need of only 20 comparisons to find a number. The levels of this tree are 20. We have also used the formula log(100,000) (log with base 2).
Properties of AVL Tree
- Height of the left and right subtrees may differ by at most 1.
- Height of an empty tree is defined to be (–1).
The depth of a binary tree is the maximum level of its leaves, i.e., the height of the tree.
Examples of AVL Tree
Following figure shows an AVL Tree:
As you can see that the balance at every node is 1, 0, or -1. So it’s balanced tree and will be called an AVL tree.
Following figure isn’t AVL Tree:
As you can see in Fig 3, the balance at node “6” is “2”. So, it’s not balanced and will not be called an AVL tree.
See another example to understand AVL tree more clearly:
In Fig 4, every node has a balance of 1, 0, or -1. So, this is also an AVL tree.
REFERENCE: CS301 Handouts (page 214 to 223)