An AVL (adelson-velskii-landis) tree also known as balanced tree is a binary search tree with a *balance condition*.

The balance condition is that for every node in the tree, the height of left and right subtrees can differ by at most 1. The condition ensures that the depth of the tree is O(log N).

9 9 / \ / \ / \ / \ / \ / \ 5 15 5 15 / \ / / \ / \ 2 6 / 2 6 / \ 13 13 20 / / / / 12 12 fig1:BST but fig2:BST and is balanced(AVL) tree not balanced tree

as the node 15 in fig1 is out of balance because height of left sub tree is 2 and height of right sub tree is 0.

You might be wondering how to compute height, here it is

height(Tree) = MAX(height(left-sub-tree), height(right-sub-tree)) + 1;

for example, height(9) = MAX(height(5), height(15)) + 1;

height(5) = MAX(height(2), height(6)) + 1 = 1;

height(15) = MAX(height(13), -1) + 1 = 2

so, height(5) = MAX(1, 2) + 1 = 3;

Maintaining height information of each node is necessary to check the balancing condition in AVL (balanced) tree.

So, here is the AVL (balanced) tree node representation

struct Tree { Tree * left, Tree * right; int element; int height; };

Here are the operations which are possible on Balanced (AVL) tree ADT,

1)Make Empty

2)Height

3)Find

4)FindMin

5)FindMax

6)Insert

7)Delete

Please referĀ http://www.refcode.net/2013/02/balanced-avl-binary-search-trees.html