Thread: AVL tree insertion

  1. #1
    Registered User
    Join Date
    Nov 2010
    Posts
    44

    AVL tree insertion

    Hello,

    I have a problem with implementing the insertion in AVL tree.

    I have coded everything except the insert method. I have some other methods about the preorder, postorder etc, I managed to create the code about height, which will help me balance the tree every time I put new value in it

    I have the height and I have the code for a simple insertion in binary search tree.

    the insertion I've coded uses simple loops, basically what I'm doing is I create the new node and check every time its value, if it's bigger I change the current pointer to go to right, else left, until it reaches a NULL value which means that it's the end and we need to put the new node there

    but what about balancing?

    I know that in AVL we have 4 different cases at most, please correct me if I'm wrong

    So we have

    a) left rotation

    for example if we have

    Code:
    a
     \
      b
       \
        c
    the height difference is 2 so it will be
    Code:
      b
     / \
    a   c
    b) right rotation

    Code:
       c
       /
      b
     /
    a
    the height difference is -2 so it will be

    Code:
      b
     / \
    a   c
    c) left right rotation

    here I'm not 100% sure.. if I understand it correctly I need to find every time the node where the height difference has a difference of 2, then if the right subtree is left heavy then we need to make a right rotation to the subtree and a left to the root node

    d) right left rotation, again I'm not 100% sure, here it's the opposite, if the left subtree is right heavy we need to make a left rotation to the left subtree and right to the root node

    Is it just these 4 cases, or is there anything more? The problem is that I don't know how to make the code for the rebalancing...

    I don't have any parent nodes.. just left and right...

    I've heard recursion works well in AVL, but I don't know how to use it here..

    any suggestions on how to move from a simple BST insertion method to an AVL insertion method?

    thanks in advance
    Last edited by nik; 12-04-2010 at 12:16 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM