AVL tree

[tonsonson]

it is the solution ,but I dont know the steps,this is not homework,i just do the exercise, i have tried but it can't work

[2kaud]

Basically an AVL tree is a binary tree where the difference in heights of a node's subtrees are no more than 1. If this height difference exceeds 1 by either insertion or deletion then the subtrees are rotated in order to maintain the balance.

There are various internet sites that describe avl trees. eg
http://en.wikipedia.org/wiki/AVL_tree
http://pages.cs.wisc.edu/~ealexand/c...ees/index.html
http://www.dcs.gla.ac.uk/~pat/52233/...VLTrees1x1.pdf

and plenty of other sites.

[tonsonson]

Basically an AVL tree is a binary tree where the difference in heights of a node's subtrees are no more than 1. If this height difference exceeds 1 by either insertion or deletion then the subtrees are rotated in order to maintain the balance.

There are various internet sites that describe avl trees. eg
http://en.wikipedia.org/wiki/AVL_tree
http://pages.cs.wisc.edu/~ealexand/c...ees/index.html
http://www.dcs.gla.ac.uk/~pat/52233/...VLTrees1x1.pdf
and plenty of other sites.

I know how to draw simple AVL tree ,but this question is really hard,i cant get the idea after i look for the website u have given,I have tried many may times but still cant get the ans,can u draw out te step so I can understand?thanks so much

[razzle]

I dont know the steps

The steps are described here,

http://en.wikipedia.org/wiki/AVL_tree

In your example, when you have inserted A-V-L you have this,

     A
          V
       L

a right-left rotation followed by right-right gives,

      L
   A    V

so you insert nodes like you would in an ordinary sorted tree and when any of the four rotation cases apply you carry them out.

[tonsonson]

=.=oh my god...I know how to rotate...but I am saying that I dont know how to apply to this question,this question is much tricky....can u try first???

[razzle]

=.=oh my god...I know how to rotate...but I am saying that I dont know how to apply to this question,this question is much tricky....can u try first???

People here are not mind readers. It's your responsibility to clearly explain what's your problem so people don't have to guess.

If you know how AVL rotation works then you should have no problems with this specific input because you just apply them systematically as you do on every input. So obviously you don't know how to rotate and what you're lacking most likely is the element of recursion that's involved.

If you just want to check this input then why don't you simply use one of the AVL simulators you can easily find on the net? This one for example,

https://www.cs.usfca.edu/~galles/vis...n/AVLtree.html

Just enter the letters one by one in the input field in the upper left corner (press the insert button after each letter) and watch the tree grow AVL style.

[2kaud]

I know how to rotate...but I am saying that I dont know how to apply to this question,this question is much tricky....can u try first???

If you know the rules of constructing an AVL tree and you know how to apply appropriate rotation recursively across the tree, then you know how to create a correct AVL tree. If you are not generating the expected tree then either you are not understanding rotation properly or you are not applying it correctly.

Sorry to not be more helpful but this is something you have to slog at until you 'get it'. I well remember when I was doing AVL trees as part of my degree spending several hours in an empty lecture theatre drawing in chalk all these trees all over the boards, rubbing them out and re-drawing them until I got it right. I sympathise.

[2kaud]

use one of the AVL simulators you can easily find on the net? This one for example,

https://www.cs.usfca.edu/~galles/vis...n/AVLtree.html

Just enter the letters one by one in the input field in the upper left corner (press the insert button after each letter) and watch the tree grow AVL style.

That's real good! I hadn't seem something like that before. Some one's university project no doubt!

[NNcNannara]

See http://nncnannara.net/Html/English/sets/index.html for the source code to AVL Trees in C#.

[Priya456]

An AVL tree is a variant of the binary search tree. Like a binary search tree, it is made up of a "root" and "leaf" nodes. Every node has at most two children, where the left child is less than the parent and the right child is greater.

But binary search trees can either be unbalanced or balanced. A tree is balanced if the depths of its left subtree and right subtree differ by at most 1. An AVL tree balances itself after every operation. An AVL has much faster operations because it's always balanced. AVL trees were the first self-balancing tree structures.