While performing a rotation in an unbalanced binary search tree, we need to rotate the parent node[single rotation] if the imbalance is being caused in right-right or left-left. so the parent node can be easily accessed as it is being passed to the function.
void add_node(T data,Node<T>* &node){
if(this->root==nullptr){
Node<T>* new_node= new Node<T>(data);
this->root=new_node;
}
else{
if(data<node->m_data){
if(node->m_left!=nullptr){
add_node(data,node->m_left);
}else{
Node<T>* new_node= new Node<T>(data);
node->m_left=new_node;
rebalance(node);
}
}
if(data>node->m_data){
if(node->m_right!=nullptr){
add_node(data,node->m_right);
}else{
Node<T>* new_node= new Node<T>(data);
node->m_right=new_node;
rebalance(node);
}
}
}
}
But how do we access the ancestor node if we need to perform an LR or RL rotation?
Node<T>* rebalance(Node<T>* &node){
int bal_fact=balance_factor(node);
if(bal_fact>1){
if(balance_factor(node->m_left)>0){
node=ll_rotate(node);
}else{
node=lr_rotate(node);
}
}
if(bal_fact<-1){
if(balance_factor(node->m_right)>0){
node=rl_rotate(node);
}else{
node=rr_rotate(node);
}
}
return node;
}
Aucun commentaire:
Enregistrer un commentaire