AVL trees?

[noRulez]

Im wondering if anyone in this board knows a bit about AVL trees? My problem is short, but...in my mind...not simple. Im 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 its right subtree minus the depth of its 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.

 

[quwiltw]

Originally posted by noRulez
But how do you get the depth of either subtree?

Its been a while, but I dont recall you having to. Since each node maintains its current skew state (right-high, left-high, or none), as you go back up the insertion stack, youll fix the skews as you go. If the right subtree has grown and it was left high, now its none, if it was none, now its right-high, etc. If you post what code you have so far, Ill take a look at it.

 

[noRulez]

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, Im not sure how to fix that...it just happens when I copy and paste out of the vis c++ ide

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 its left child to NULL
        tempNode->rc = NULL;      //set its right child to NULL
        tempNode->key = keyVal;  //set its key to what was passed in
		tempNode->skew = 0;      //all leafs have a skew of zero
        if(this->head == NULL){     //if its 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;  
    }
}

 

[quwiltw]

Yeah, I dont 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 Id 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.

 

[noRulez]

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 cant 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 isnt 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.

 

[quwiltw]

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 nodes 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)