cpppro

Balanced (AVL) Binary Search Trees

In C Tidbits, Data Structures in C/C++ on December 28, 2007 at 6:55 pm

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

 

 

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

  2. I’m becoming an admirer of this site πŸ™‚

  3. This is best work I’d ever seen on balanced trees, however the presentation lacks an order a bit

  4. probably not the best πŸ™‚ but definitely a good one

  5. 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);
    }

  6. I forgot to mention.

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

  7. 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?

  8. I’m feel good after learning your source code than what I learned in the book. Good one.

  9. double_rotation_with_right is definitely bugged like SverreN has posted, otherwise nice code.

  10. 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!

  11. The delete function doesn’t work……..
    it just wont do any rotation

  12. The code looks very similar to the implementation in “Data Structures and Algorithms in c” by Mark Allen Weiss.!!!!!

  13. 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.

  14. Cool post I will continue to look out for anymore of your future posts.

  15. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: