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
Data Structures Blog 
This is the best post I’d ever seen on balanced trees, keep the good work, thanks
I’m becoming an admirer of this site 🙂
This is best work I’d ever seen on balanced trees, however the presentation lacks an order a bit
probably not the best 🙂 but definitely a good one
Isn’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);
}
I forgot to mention.
Other than the suspected bug mentioned above your post (and code) is really good. Good work. 🙂
I 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?
I’m feel good after learning your source code than what I learned in the book. Good one.
double_rotation_with_right is definitely bugged like SverreN has posted, otherwise nice code.
raj, 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!
The delete function doesn’t work……..
it just wont do any rotation
The code looks very similar to the implementation in “Data Structures and Algorithms in c” by Mark Allen Weiss.!!!!!
Sorry, 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.
Cool post I will continue to look out for anymore of your future posts.
can 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.