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; } } |