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?
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).