-
February 28th, 2015, 07:38 AM
#1
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
-
February 28th, 2015, 10:03 AM
#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.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
February 28th, 2015, 11:29 PM
#3
Re: AVL tree
Originally Posted by 2kaud
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.
-
March 1st, 2015, 02:20 AM
#4
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,
a right-left rotation followed by right-right gives,
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.
-
March 1st, 2015, 02:25 AM
#5
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???
-
March 1st, 2015, 03:35 AM
#6
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.
-
March 1st, 2015, 05:04 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.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
March 1st, 2015, 05:07 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!
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only - not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums - and not via private messages!
C++23 Compiler: Microsoft VS2022 (17.6.5)
-
November 10th, 2017, 11:52 PM
#9
-
November 15th, 2017, 02:33 AM
#10
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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|