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

### Like this:

Like Loading...

*Related*

This is the best post I’d ever seen on balanced trees, keep the good work, thanks

29 December 2007at12pmI’m becoming an admirer of this site π

1 January 2008at2pmThis is best work I’d ever seen on balanced trees, however the presentation lacks an order a bit

10 January 2008at10amprobably not the best π but definitely a good one

22 January 2008at11pmIsn’t there a bug in your sources?

It seems to me that in your function double_rotation_with_right you should use:

k->right = single_rotation_with_left(k3->right);

and not:

k->left = single_rotation_with_left(k3->right);

You can easilly test this out using with this example insertion sequence:

5, 10, 8

Obviously this will require balancing. To me it seems like your code will mess up the binary tree, creating a circular reference when you balance after having inserted the 8.

Proposed correct code:

Tree *double_rotation_with_right(Tree *k3)

{

//rotate between k1 & k2

k3->right = single_rotation_with_left(k3->right);

//rotate between k3 & k2

return single_rotation_with_right(k3);

}

2 May 2008at5pmI forgot to mention.

Other than the suspected bug mentioned above your post (and code) is really good. Good work. π

2 May 2008at5pmI fail to see this case clearly – i.e,

In the insert into tree snippet, will this condition be met – if (height(t->left) – height(t->right) == 2)?

All I see is this

new_node->height = 0; but no updates to the height for each node are done, so how will this work. Am I missing something here?

14 May 2008at8amI’m feel good after learning your source code than what I learned in the book. Good one.

4 June 2008at2pmdouble_rotation_with_right is definitely bugged like SverreN has posted, otherwise nice code.

16 January 2009at2pmraj, here it is:

t->height = MAX(height(t->left), height(t->right)) + 1;

at the end of the insert π

However, really nice work, thanks for the explanation!

30 January 2009at9pmThe delete function doesn’t work……..

it just wont do any rotation

24 May 2009at4pmThe code looks very similar to the implementation in “Data Structures and Algorithms in c” by Mark Allen Weiss.!!!!!

2 November 2009at4amSorry, but I think this implementation is wrong in that it does not actually use the AVL algorithm. It seems few people even understand it these days. It may well succeed in balancing the trees, but will be inefficient in both time and space. As I don’t like to see yet another source of AVL misinformation on the web, I write this explanation of what I think is wrong.

It is not necessary to store the height information in each node, only the “balance factor” (difference in left and right sub-tree heights). This potentially just 2 bits per node if you can squeeze them in somewhere. The AVL algorithm works inferring changes in height from changes in balance factor _only_ (and propagating those changes back up the tree). Most importantly, during insertion it does not require nodes that not on the search path to be inspected in order to obtain their height. This is likely to be expensive on modern memory architectures.

If you want to support operations that combine 2 trees (like append or union) then you do need to start out knowing their heights, but only of the whole trees. Again, heights of sub-trees can be inferred from balance factors alone so don’t need storing in each node.

Also insertion in AVL trees will require at most 1 rebalancing rotation (because combined effect of unbalancing/rebalancing leaves the height unchanged), so there’s a possible optimisation opportunity there that the code doesn’t currently exploit. This is not true for deletion BTW.

2 November 2009at6amCool post I will continue to look out for anymore of your future posts.

25 November 2009at1amcan somebody explain to me how are you guys using the pointers as methods?

for example how do you actually use the insert function as it seems to be a pointer it self….Thanks.

25 November 2009at9am