AVL trees?

N

noRulez

Newcomer
Joined
Aug 2, 2002
Messages
15
Location
Kansas, God Bless America
I'm wondering if anyone in this board knows a bit about AVL trees? My problem is short, but...in my mind...not simple. I'm having trouble figuring out how to update the skews of all the nodes after I do an insert. I have been through at least 200 web pages and none of them go into depth on this subject. They will tell you that the skew of the node is equal to the depth of it's right subtree minus the depth of it's left subtree. But how do you get the depth of either subtree? I am just wondering if anyone knows of a clean and simple way to update all the skews after an insert :)

Thanks in advance.
 
noRulez said:
But how do you get the depth of either subtree?
Click to expand...
It's been a while, but I don't recall you having to. Since each node maintains it's current skew state (right-high, left-high, or none), as you go back up the insertion stack, you'll fix the skews as you go. If the right subtree has grown and it was left high, now it's none, if it was none, now it's right-high, etc. If you post what code you have so far, I'll take a look at it.
 
This is what I have so far without any rotations. It might actually be working...I think. Let me know if you see anything wrong with it. Sorry about the spacing, I'm not sure how to fix that...it just happens when I copy and paste out of the vis c++ ide

Code: 
template <class T>
avlTree<T>::treeNode* avlTree<T>::insertNode(treeNode *tempNode, T keyVal){
	if(tempNode == NULL){     //means you have found a spot in the tree
        tempNode = new treeNode;  //create a new node for it
        tempNode->lc = NULL;      //set it's left child to NULL
        tempNode->rc = NULL;      //set it's right child to NULL
        tempNode->key = keyVal;  //set it's key to what was passed in
		tempNode->skew = 0;      //all leafs have a skew of zero
        if(this->head == NULL){     //if it's the first time, set head value
            head = tempNode;
        }
		return tempNode;
    }
	else{
        if(keyVal<tempNode->key){       //move down the left side of tree
			int befSkewLC;
			if(tempNode->lc==NULL){
				befSkewLC=3;
			}
			else befSkewLC = tempNode->lc->skew;
            tempNode->lc = insertNode(tempNode->lc,keyVal);
			if(befSkewLC==0){
				tempNode->skew -= 1;
			}
			else if(befSkewLC==3){
				if(tempNode->rc!=NULL)
					tempNode->skew = 0;
				else
					tempNode->skew=-1;
			}
		}
        else{                           //move down the right side of tree
			int befSkewRC;
			if(tempNode->rc==NULL){
				befSkewRC=3;
			}
			else befSkewRC = tempNode->rc->skew;
            tempNode->rc = insertNode(tempNode->rc,keyVal);
			if(befSkewRC==0){
				tempNode->skew += 1;
			}
			else if(befSkewRC==3){
				if(tempNode->lc!=NULL)
					tempNode->skew = 0;
				else
					tempNode->skew=1;
			}
		}

        return tempNode;  
    }
}
 
Yeah, I don't understand your numeric skews. For any given node, I think you only need to know whether that node is right-high, left-high, or balanced. I also think I'd combine the skew-setting with the rotation code. If I remember correctly, I used pretty much the same insertion code for an AVL tree as a BST and just handled the null root differently (setting a balanced skew) as well as adding a call to a to RightTreeGrew or LeftTreeGrew as appropriate to handle the skew setting and rotation. I essentially split the insertion from the subsequent rotation/skew-setting.
 
Well, I have verified that my skew-setting after an insert works perfectly. Oh, -1 = left high, 1 = right high, 0 = balanced. Those are my numeric skews. My only problem now is that I can't figure out how to reset the skews after a rotation.

My attempt so far has been to recurse down to the bottom, set the leafs to null, and then work my way up trying to use some sort of logical comparison of the leafs to figure out what the skew for the parent is, but that isn't working so far. Actually, it works for most cases...but not all. Hmmm...any ideas on that?

Oh, and I set a skew to 3 to signify that it was a NULL pointer.
 
Since rotations occur at the lowest level necessary so should the skew resetting. No traversal of the entire tree should be necessary. It should be logically based off of what the node's skew was before the insertion, what subtree grew, and the direction of the rotation. (ie. LeftHigh, left subtree grew, right rotation=> balanced or Balanced, right subtree grew, no rotation, Right-High)
 
Back
Top