Language: EN FI

Exercises > Double rotation

These exercises demonstrate the content of the ByTheMark service. These are meant for private individuals for learning data structures and algorithms. If you want to try out more content, you can register to the ByTheMark Personal free of charge.

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

  Last modified Tue Mar 01 20:54:04 EET 2011