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
elseif(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.