AVL tree
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 10 of 10

Thread: AVL tree

  1. #1
    Join Date
    Feb 2015
    Posts
    21

    AVL tree

    Name:  11.jpg
Views: 211
Size:  9.2 KB
    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
    Name:  12.jpg
Views: 205
Size:  9.0 KB

  2. #2
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,835

    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++17 Compiler: Microsoft VS2017 (15.4.4)

  3. #3
    Join Date
    Feb 2015
    Posts
    21

    Re: AVL tree

    Quote Originally Posted by 2kaud View Post
    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. #4
    Join Date
    Jul 2013
    Posts
    576

    Re: AVL tree

    Quote Originally Posted by tonsonson View Post
    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. #5
    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. #6
    Join Date
    Jul 2013
    Posts
    576

    Re: AVL tree

    Quote Originally Posted by tonsonson View Post
    =.=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. #7
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,835

    Re: AVL tree

    Quote Originally Posted by tonsonson View Post
    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++17 Compiler: Microsoft VS2017 (15.4.4)

  8. #8
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,835

    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++17 Compiler: Microsoft VS2017 (15.4.4)

  9. #9
    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. #10
    Join Date
    Aug 2017
    Posts
    32

    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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This a Codeguru.com survey!


On-Demand Webinars (sponsored)