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)
You're probably looking for that implementation?
http://www.link.cs.cmu.edu/link/ftp-site/splaying/top-down-size-splay.c