how do I balance my binary tree

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 who开发者_JAVA技巧le thing, I just want to include a function that will balance the tree. Any algorithms or ideas?

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.

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

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.

look for balanced trees like avl red black