Making an AVL Tree

This is a discussion on Making an AVL Tree within the C Programming forums, part of the General Programming Boards category; Hello, I need some guidance regarding AVL Trees. So far, I have created a binary tree library. For the next ...

  1. #1
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Posts
    306

    Making an AVL Tree

    Hello,

    I need some guidance regarding AVL Trees. So far, I have created a binary tree library. For the next step, I want to use this btree source code to make it into an AVL tree. I have studied Prelude's AVL Tutorial on her webpage and I understand the rotations part. However, I need some assistance on how to know when to do a rotation. I know I need to add a "balance" variable to each node. Also that I need to modify my insert function to automatically perform rotations. I plan to insert normally, then do a tree traversal that will update balance factors. When out of balance is detected I run a rotation but how do I know which one is needed (single, double, left, right) ?

    This whole thing is confusing as heck.

  2. #2
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    You know how to rotate based on how the balance factors are set. My tutorial describes all of this, including the specific cases you need to look for and how to respond to them. What in particular are you having trouble with?

    >This whole thing is confusing as heck.
    It's a complicated data structure, what did you expect?
    My best code is written with the delete key.

  3. #3
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Posts
    306
    Hi Prelude.

    Your tutorial is awesome I learned a lot from it. I want to use the bounded balance factors method as it seems a fair bit easier (I can worry about efficency later). My first problem is exactly how to figure out the balance factors for each node. I have a function Tree_traversal that allows a function to be passed in that will be called in either pre, post or inorder, eh, order. Could I use this function to update the balance factors? Or do I need to create a specific function for rebalance(Tree *)?

    I'm sure if I spend enough time with your tut, I could do this. I understand all the the code, it's pretty simple for me. However, I don't want to cut and paste I want to create my own version using my already written library of code.

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >My first problem is exactly how to figure out the balance factors for each node.
    The most straightforward way is to do it after you insert each node. Walk back up the path and adjust balance factors.

    >Could I use this function to update the balance factors?
    It probably wouldn't be worth it.
    My best code is written with the delete key.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,266
    Bear in mind that you never actually calculate the entire balance factor for a node from scratch. You only ever need to adjust it acording to the changes that you make to the tree which you know affected the balance by a certain amount.

    You wont really find it any easier rebalancing as an second pass either. You would either end up rebalancing the entire tree or you follow the path down where the node you inserted goes. However during insertion you do the same thing so you may as well just rebalance the node after each recursive call.

    There are two ways to do an AVL tree though. One is to store a balance factor in each node, the other is to store the height in each node.

    My website doesn't really explain the algorithms as such yet, but the fairly well written and hopefully understandable implementations (if I do say so myself) are there for you to study. (Link in sig)
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  6. #6
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Posts
    306
    Ok, so far I've got all the rotation functions written and tested. Took me a couple hours of debugging though. I added a height member to my nodes. Next I would like to modify my insertion function so that it will update the heights. After that, I can worry about checking balances and how to call the right rotations.

    Code:
    void BSTree_add(struct Tree *pTree, int value)
    {
      if (Tree_isempty(pTree))
      {
        Tree_setrootvalue(pTree, value);
      }
      else
      {
        if (value <= Tree_getrootvalue(pTree))
        {
          BSTree_add(Tree_getlefttree(pTree), value);
        }
        else
        {
          BSTree_add(Tree_getrighttree(pTree), value);
        }
      }
    }
    Where/how to set height member?

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,266
    Ok cool.
    I think probably the next step is to do some drawings on paper of the unbalanced tree cases, and then draw what the rotation will change it to, and then step through what has changed and write the code to do it. At least that's the kind of thing that helped me when I was doing it. It'll definitely help to refer to Prelude's article as well though to make sure you stay on track.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Posts
    306
    On prelude's website:
    Code:
    if (lh - rh >= 2 )
    Is supposed to know when a tree is out of balance?
    What about this tree?
    Code:
    1, 2
     \
      2, 1
       \
        3, 0
    Lets see, I know I need to perform a left rotation at (1), but I don't think that condition above would be true. Let's see: LH = -1, RH = 1. (-1 - 1) == 0. Am I missing something?

  9. #9
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Posts
    306
    [EDIT]

    WOOT!

    Got it completely working now! I thought I'd never be able to do it.

    Thanks for writing such a great tutorial prelude: even if I didn't use your code (and I realised my framework was overly-complex) the concepts were described in general enough terms that I was able to figure it out.

    [/EDIT]

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. please help with binary tree, urgent.
    By slickestting in forum C Programming
    Replies: 2
    Last Post: 07-22-2007, 07:55 PM
  2. Balancing a tree (AVL Tree)
    By BoneXXX in forum C Programming
    Replies: 20
    Last Post: 04-12-2007, 01:15 PM
  3. Tree traversal
    By recluse in forum C Programming
    Replies: 4
    Last Post: 12-05-2004, 03:00 PM
  4. 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
  5. read records fron file into a binary tree
    By Kirsten in forum C Programming
    Replies: 1
    Last Post: 04-23-2002, 02:48 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21