AVL Tree Insertion

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?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//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;
	}
}
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.
Sure. I sit in the back left corner by the pencil sharpener in class.
Topic archived. No new replies allowed.