CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

1. Junior Member
Join Date
Feb 2015
Posts
21

## AVL tree

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

2. ## Re: AVL tree

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.

3. Junior Member
Join Date
Feb 2015
Posts
21

## Re: AVL tree

Originally Posted by 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.
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
Last edited by tonsonson; March 1st, 2015 at 01:06 AM.

4. Member +
Join Date
Jul 2013
Posts
576

## Re: AVL tree

Originally Posted by tonsonson
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,

Code:
```     A
V
L```
a right-left rotation followed by right-right gives,
Code:
```      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.
Last edited by razzle; March 1st, 2015 at 02:29 AM.

5. Junior Member
Join Date
Feb 2015
Posts
21

## Re: AVL tree

=.=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???

6. Member +
Join Date
Jul 2013
Posts
576

## Re: AVL tree

Originally Posted by 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???
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.
Last edited by razzle; March 1st, 2015 at 04:38 AM.

7. ## Re: AVL tree

Originally Posted by tonsonson
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.
Last edited by 2kaud; March 1st, 2015 at 05:22 AM.

8. ## Re: AVL tree

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!

9. Junior Member
Join Date
Nov 2017
Posts
1

## Re: AVL tree

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

10. Member
Join Date
Aug 2017
Posts
38

## Re: AVL tree

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.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•