hello,

recently I started to learn the top down method of splay trees I found this pdf talking about it, I also found this code and I managed to understand it very well.

now I want for each node in splay tree let's say node A to store the number of nodes in its subtree let's call it sum(A), the hard part is to compute sum(A) for each node during top-down splaying since sum(A) depands on the values of sum(L) and sum(R) (where L and R are children of A) so sum values must be computed from bottom to up while the method of splaying is top-down that's my problem.

actually after I learnt top-down method of splaying I want to solve ORDERSET using this method so I need to store sum values for nodes so how it can be done?

I am not sure I understand what the problem is, but if you want to add some extra field to vertexes, you can just modify rotation procedures adding calls of

updatefunction, that is ~`p->sum = p->L->sum + p->val + p->R->val`

for each touched vertex.Lazy update for Splay tree? You may want to read this: https://sites.google.com/site/kc97ble/container/splaytree-cpp-3

this is not top-down splay tree, it's bottom-up splay tree.

no, this is top-down splay tree

I'm sorry, it's my mistake. I thought that this code is top-down and the other is bottom-up.

What are the advantages of top-down splay tree over bottom-up one? Actually I know none of them. But I've seen indy256 and WJMZBMR's implementation of bottom-up splay tree and they look really simple (and short) to me. So please enlighten us. Thank you :)

can you share code links, please? :)

The code is right there in the same FTP site where you found the top-down splaying.

www.link.cs.cmu.edu/link/ftp-site/splaying/top-down-size-splay.c

---D. Sleator

here u go, ur 100th upvote! ;)

EDIT: looks like i helped u get even more than 100! ;)

Fun Fact: Darooha is also the co-inventor with Tarjan of Splay Trees and Link-cut Trees :D http://en.wikipedia.org/wiki/Daniel_Sleator

It is my new splay tree source code (top-down, lazy update), which support modify (a element), sum (range), and reverse (range) queries. https://sites.google.com/site/kc97ble/container/splaytree-cpp-5-lazyupdate I wrote it yesterday, in 48 minutes (and got AC in a problem).