Balancing a Binary Tree (AVL)

algorithm computer-science binary-tree theory avl-tree
Gustavo Carreno picture Gustavo Carreno · Sep 25, 2008 · Viewed 36.6k times · Source

Ok, this is another one in the theory realm for the CS guys around.

In the 90's I did fairly well in implementing BST's. The only thing I could never get my head around was the intricacy of the algorithm to balance a Binary Tree (AVL).

Can you guys help me on this?

Answer

Konrad Rudolph picture Konrad Rudolph · Sep 25, 2008

I don't think it's good to post complete codes for node balancing algorithms here since they get quite big. However, the Wikipedia article on red-black trees contains a complete C implementation of the algorithm and the article on AVL trees has several links to high-quality implementations as well.

These two implementations are enough for most general-purpose scenarios.

Related questions

What is a plain English explanation of "Big O" notation?

I'd prefer as little formal definition as possible and simple mathematics.

Read More
How to determine the longest increasing subsequence using dynamic programming?

I have a set of integers. I want to find the longest increasing subsequence of that set using dynamic programming.

Read More
What exactly does big Ө notation represent?

I'm really confused about the differences between big O, big Omega, and big Theta notation. I understand that big O is the upper bound and big Omega is the lower bound, but what exactly does big Ө (theta) represent? I have …

Read More