Saturday, April 25, 2009

AVL tree Explanation

hey i m here to tell my difficulty in AVL tree regarding abt Left of right rotatin and right of left rotation...

wht is difficult for me to indentify tree which has to be solved by using Left of right or Right of left rotation..?

When you insert or delete a node, you first have to determine which is the node where imbalance first occurs |left subtree height - right subtree height| > 1. Then to preserve the inorder invariance (to preserve the "order" in the tree) you may have to perform a single rotation or a double rotation of the tree, to rebalance it.
This is best explained by looking at different cases as examples. Any good book on data structures is useful - I found Goodrich and Tamassia to be good.
The following tutorial is also useful.
http://fortheloot.com/public/AVLTreeTutorial.rtf
Also checkout the Wiki page.
http://en.wikipedia.org/wiki/Tree_rotation

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.