2 Replies - 2193 Views - Last Post: 22 November 2011 - 02:00 PM

#1 sport10  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 181
  • Joined: 21-September 10

AVL Tree

Posted 22 November 2011 - 08:48 AM

Would this tree:
            70
          /    \
         49    80
        /  \   /
      27   65  78
     /  \ 
    6   33

\\Look like this when 65 is removed:

            49
          /    \
         27     80
        /  \   /  \
       6   33 70  78


This post has been edited by sport10: 22 November 2011 - 08:50 AM

Is This A Good Question/Topic? 0
  • +

Replies To: AVL Tree

#2 SwiftStriker00  Icon User is offline

  • No idea why my code works
  • member icon

Reputation: 433
  • View blog
  • Posts: 1,596
  • Joined: 25-December 08

Re: AVL Tree

Posted 22 November 2011 - 11:48 AM

Almost had it.

            49
          /    \
         27     78
        /  \   /  \
       6   33 70  80



AVL trees are just BST that balance themselves, remember :
left child is < than parent
right child is > than parent
Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10595
  • View blog
  • Posts: 39,240
  • Joined: 27-December 08

Re: AVL Tree

Posted 22 November 2011 - 02:00 PM

*Moved to Computer Science*

The reason SwiftStriker00's solution is correct is b/c the balancing constraint is applied recursively to the subtrees. After removing 65, the 49 tree is unbalanced, and thus must be rotated.

More on AVL Trees: http://www.dreaminco...-tree-tutorial/
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1