| Hide text Hide pseudo-code | |
|
The AVL-tree below is out of balance after the last insertion (in the model solution you can see the state before and after the insertion). Balance the tree by making a double rotation. |
// p is unbalanced, f is p's father
if (f->left == p) {
if (height(p.left) > height(p.right)) {
f->left = p->left->right; // LR-double rotation
p->left->right = f->left->left;
f->left->left = p->left;
p->left = f->left->right;
f->left->right = p;
} else { // height(p.left) < height(p.right)
f->left = p->right->left; // RL-double rotation
p->right->left = f->left->right;
f->left->right = p->right;
p->right = f->left->left;
f->left->left = p;
}
} else { // f->right == p
if (height(p.left) < height(p.right) {
f->right = p->right->left; // RL-double rotation
p->right->left = f->right->right;
f->right->right = p->right;
p->right = f->right->left;
f->right->left = p;
} else { // height(p.left) > height(p.right)
f->right = p->left->right; // LR-double rotation
p->left->right = f->right->left;
f->right->left = p->left;
p->left = f->right->right;
f->right->right = p;
}
}
|