When inserting node z, we search down the tree for the proper place for z. For each node x on this path, add 1 to x.rank if z is inserted within x’s left subtree, and leave x.rank unchanged if z is inserted within x’s right subtree. Similarly when deleting, subtract 1 from x.rank whenever the spliced-out node had been in x’s left subtree.
We also need to handle the rotations that occur during the fixup procedures for insertion and deletion. Consider a left rotation on node x, where the pre-rotation right child of x is y (so that x becomes y’s left child after the left rotation).We leave x.rank unchanged, and letting r = y.rank before the rotation, we set y.rank = r + x.rank. Right rotations are handled in an analogous manner.
正确的官方答案