6 / 6 Binary Search Trees, Rotations & Balance

Single Or Double Reversed

The AVL rebalance routine picks between one rotation and two. The //@requires line on rotate_right is the real contract from the lecture notes.

tree* rotate_right(tree* T)
//@requires T != NULL && T->left != NULL;
{ ... }

tree* rebalance_right(tree* T) {
  if (height(T->right) - height(T->left) == 2) {
    if (height(T->right->left) > height(T->right->right)) {   // comparison reversed
      T = rotate_left(T);
    } else {
      T->right = rotate_right(T->right);
      T = rotate_left(T);
    }
  } else {
    fix_height(T);
  }
  return T;
}

Insert 30, then 40, then 50 into an empty tree. What happens during the third insert?

A

The keys stay correctly ordered but the subtree keeps height 3 instead of 2, so lookups are slower and nothing crashes.

B

rotate_right is called on the node holding 40, whose left child is NULL, so the contract is violated and the code dereferences a null pointer.

C

Nothing goes wrong. Two rotations in opposite directions cancel, so the result is the same tree a single left rotation would have produced.

D

No rotation runs, because the height difference at 30 is 1, not 2.