how do I balance my binary tree

Question

Hi,

I already have a working binary tree database. Unfortunately, it needs to have the ability to balance itself. I don't want to rewrite the whole thing, I just want to include a function that will balance the tree. Any algorithms or ideas?

Answer 1

look for balanced trees like avl red black

Answer 2

AVL and RedBlack trees are self balancing trees. You can traverse your original tree and insert the nodes in these trees. Afterwards you can keep the new tree and discard your original tree.

Answer 3

I have found the Stanford libavl tutorial quite helpful.

Check out the examples in AVL tree wiki.

Also, try to play with the AVL tree animations available in the web, such as

• http://www.cs.jhu.edu/~goodrich/dsa/trees/avltree.html or

• http://www.strille.net/works/media_technology_projects/avl-tree_2001/ or

• http://www.site.uottawa.ca/~stan/csi2514/applets/avl/BT.html

Answer 4

AVL and Red-Black trees are balanced binary trees. I have an implementation of AVL trees. Look here. It supports insertion and search. Deletion is not implemented yet.