setting parent on AVL tree

Question

I am trying to implement an AVL tree and not sure about the best way to do insert and track each node's parent. This is educational so please do not suggest "use boost" :)

This compiles but I am not convinced of its correctness or that it is the best way. Specifically this

insert(someNumber,root,root);

Also, I will redo the height part when I rebalance and move up the tree.

I insert like this

myTree.insert(someNumber);

Here is the method. I am not sure what my second param should be here. I would have thought NULL but the compiler does not like that (different function definition).

void Tree::insert(int someNumber){
    insert(someNumber,root,root);
}

Here is my insert

void Tree::insert(int someNumber,Node*& subTreeRoot,Node*& parent){
    if(subTreeRoot==NULL)
    {
        subTreeRoot = new Node(someNumber,parent);
        if(subTreeRoot->myParent)   
    }
    else if (someNumber<subTreeRoot->myNumber)
    {
        if((subTreeRoot->right==NULL)||((subTreeRoot->left!=NULL)&&(subTreeRoot->right!=NULL)))
            subTreeRoot->height++;
        insert(someNumber,subTreeRoot->left,subTreeRoot);
    }
    else
    {
        if((subTreeRoot->left==NULL)||((subTreeRoot->left!=NULL)&&(subTreeRoot->right!=NULL)))
            subTreeRoot->height++;
        insert(someNumber,subTreeRoot->right,subTreeRoot);
    }
}

-

Answer 1

Since you are doing this for education, I would suggest that you work some cases out by hand, then code them into tests of the form

 Insert(6);
 Insert(11);
 // ...
 Insert(3);

 Node test = root;
 assert(root->height == 3);
 assert(root->value == 6);
 test = root->right;
 assert( ... );

the numbers are completely made up.

This will

1. Give you more than a feeling as to whether or not your code is working. (Hint: if your are not sure your code is working, it probably isn't)
2. Give you a place to start figuring out what is going wrong.
3. Develop the habit of testing. It is counterintuitive to some people that writing twice as much code (tests + code) is faster than just writing the code in the first place, but try it. Plus writing more code = more practice.

Answer 2

What's the difference between a Tree and a Node? (A Tree is only place holder for the root Node, nothing more. A node is sometimes said to have two subtrees. Tree and Node are no different. One class would suffice.)

Why don't just calculate the height whenever you need it? Much easier to program and proof correct. If performance is hurting you, you can always change the function to return a cached value.

A node should not know it's parent (in my opinion). So the insert function needs a parent parameter. After creating the new node compare the parents-childrens depths to see if you need to do any rotations. Programming the rotations is tricky: try, debug and test!

Node::insert(int number,Node * parent)
{
  //code
  left=new node(number);
  if (parent->left->depth() > parent->right->depth()+1)
    parent->rotate_tree_or_something();
  //
}