AVL Tree Rotations
struct Node *LLRotation(struct Node *ptr) {
struct Node *ptrL = ptr -> left;
struct Node *ptrLR = ptrL -> right;
ptrL -> right = ptr;
ptr -> left = ptrLR;
ptr -> height = nodeHeight(ptr);
ptrL -> height = nodeHeight(ptr -> left);
if (ptr == root)
root = ptrL;
return ptrL;
}
struct Node *RRRotation(struct Node *ptr) {
struct Node *ptrR = ptr -> right;
struct Node *ptrRL = ptrR -> left;
ptrR -> left = ptr;
ptr -> right = ptrRL;
ptr -> height = nodeHeight(ptr);
ptrR -> height = nodeHeight(ptr -> right);
if (ptr == root)
root = ptrR;
return ptrR;
}
struct Node *LRRotation(struct Node *ptr) {
struct Node *ptrL = ptr -> left;
struct Node *ptrLR = ptrL -> right;
ptrL -> right = ptrLR -> left;
ptr -> left = ptrLR -> right;
ptrLR -> left = ptrL;
ptrLR -> right = ptr;
ptr -> height = nodeHeight(ptr);
ptrL -> height = nodeHeight(ptrL);
ptrLR -> height = nodeHeight(ptrLR);
if (ptr == root)
root = ptrLR;
return ptrLR;
}
struct Node *RLRotation(struct Node *ptr) {
struct Node *ptrR = ptr -> right;
struct Node *ptrRL = ptrR -> left;
ptrR -> left = ptrRL -> right;
ptr -> right = ptrRL -> left;
ptrRL -> left = ptr;
ptrRL -> right = ptrR;
ptr -> height = nodeHeight(ptr);
ptrR -> height = nodeHeight(ptrR);
ptrRL -> height = nodeHeight(ptrRL);
if (ptr == root)
root = ptrRL;
return ptrRL;
}
Contributed by Nitin Ranganath
Last modified 3yr ago