kingofnumbers's blog

By kingofnumbers, 6 years ago, In English,

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?

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it -13 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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, # ^ |
      Vote: I like it +3 Vote: I do not like it

    can you share code links, please? :)

»
6 years ago, # |
  Vote: I like it +134 Vote: I do not like it

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, # |
  Vote: I like it +3 Vote: I do not like it

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