[SOLVED] On a Splay tree (top-down splaying version), how do I maintain node invariants?

On a Splay tree (top-down splaying version), how do I maintain node invariants?

I am trying to implement a Splay tree with top-down splaying, like the one described here (http://www.nocow.cn/index.php/Code:Splay_Tree/C) (first one). I have already implemented a bottom-up splaying version which also maintains the subtree-size at each node where the subtree is root at that node (ie, size = 1 + left->size + right->size).

As with each splaying operation, I was moving a node upward to root, it wasn't necessary to update all the ancestors with each rotation. But now in the top-down version, I don't understand how to maintain this subtree-size value at each node (and other kinds of invariants) without recursively updating ancestors with each rotation.

In short, how can I maintain subtree-size at each node when I'm doing a top-down splay operation? (It would be nice to have a modified version of the splay operation described on the page mentioned above)

Solution