AVL Tree Insertion

[natekelsey]

I'm using my insertion algorithm from my binary search tree and I'm unsure of where I would put my updateHeight() and rebalance() functions. I know with AVL trees that the height is updated after every insertion and if the difference in subtree heights is >= 2 then I need to rebalance the tree. Am I putting them in the right spots or am I still off on my thought process?

//Recursive insert function
void avlTree::insert(Node*& n, int item)
{
	// If node is null, create a new node with input data
	if(n==nullptr)
	{
		n=new Node(item);
		cout<<item<<" has been inserted into the Tree."<<endl;
	}
	else
	{
		// Check to see if data being inserted is < current node->data
		if(item < (n->data))
		{
			// recursive call with left child node input node
			insert((n->left), item);
			rebalance(n);
			//updateHeight
		}
		// Check to see if data being inserted is > current node->data
		else if(item > (n->data))
		{
			// recursive call with left child node input node
			insert((n->right), item);
			rebalance(n);
			//updateHeight()
		}
		else
			// If item is a duplicate, output duplicate message
			cout<<item<<" is a duplicate"<<endl;
	}
}

[derked27]

Hey Nate,
I am pretty sure I am in your class at UVU since I have the same assignment. I was wondering if you could help me. I understand how the AVL trees work on paper, but I am having a hard time implementing the assignment.

[natekelsey]

Sure. I sit in the back left corner by the pencil sharpener in class.