### kingofnumbers's blog

By kingofnumbers, 6 years ago, ,

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?

• +4

 » 6 years ago, # |   -13 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 update function, that is ~ p->sum = p->L->sum + p->val + p->R->val for each touched vertex.
 » 6 years ago, # |   0 Lazy update for Splay tree? You may want to read this: https://sites.google.com/site/kc97ble/container/splaytree-cpp-3
•  » » 6 years ago, # ^ |   0 this is not top-down splay tree, it's bottom-up splay tree.
•  » » » 6 years ago, # ^ |   0 no, this is top-down splay tree
•  » » » 6 years ago, # ^ |   0 I'm sorry, it's my mistake. I thought that this code is top-down and the other is bottom-up.
 » 6 years ago, # |   +4 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 :)
•  » » 6 years ago, # ^ |   +3 can you share code links, please? :)
 » 6 years ago, # |   +134 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
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 here u go, ur 100th upvote! ;)EDIT: looks like i helped u get even more than 100! ;)
•  » » 5 years ago, # ^ | ← Rev. 2 →   +24 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
 » 6 years ago, # |   +3 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).