C++/AVL tree

Advertisement


Question
hye..i'm a beginner in c++.so my knowledge about avl tree coding is almost zero.so can u help me with this? can u tell me the basic idea about avl tree? thanks :))

Answer
Hello ara

An AVL tree is a tree that keeps itself balanced. That means that for any node, the depth of the node's left subtree is identical to, or within +-1 of the depth of the node's right subtree. Why is that important? It is important, because without balancing, operations on the tree will become less efficient. The most unbalanced tree is actually a linked list. Searching in a linked list is slow compared to a well balanced tree. You probably know that you need at most N comparisons to find a particular item in a list of N elements. In a properly balanced tree, you need at most log(base2)(N) comparisons to find an element in a tree of N elements.

For example, with 1024 elements, you need at most 1024 comparisons to find a particular element in a linked list, but only at most 10 comparisons to find the element in a balanced tree.

Each node in the AVL tree has a number, called a balance number, which is the difference in depths between the left and right subtree.

After a new node is inserted, or removed, the balance numbers are updated, and if the magnitude of any balance number is 2, the tree is rebalanced.

The rebalancing is complicated and I have not done it in a long time.

If you need to implement an AVL tree, I can help you do that, but I will not do it all for you because as I said, it is complicated. First write code for a regular tree. If you show me that, then I will know you are serious and I will help you more.

To learn more, see
http://en.wikipedia.org/wiki/AVL_tree
and also look at the external links mentioned at the bottom of the page. They lead to many useful animations and explanations.

Good luck and best regards
Zlatko

C++

All Answers


Answers by Expert:


Ask Experts

Volunteer


Zlatko

Expertise

No longer taking questions.

Experience

No longer taking questions.

Education/Credentials
No longer taking questions.

©2016 About.com. All rights reserved.