Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

那编程复杂度呢？

Posted by TN at 2005-06-06 11:43:53
In Reply To:MS是treap比较快吧，不过也是有限的快。。。 Posted by:js05 at 2005-06-06 11:43:13

Followed by:

不考虑删除的话，MS差不多，都要左旋右旋的，但是SPLAY的删除很方便，比不同的BST还方便。。。 (0) js05 2005-06-06 11:45:05
- 可以这样理解，SPLAY的删除实际上就是插入。。。 (0) js05 2005-06-06 11:46:19
  - 这个怎么理解..... (0) palmtenor 2005-06-06 11:50:16
    - 看下面。。。 (0) js05 2005-06-06 11:51:26
- 可是我怎么听说Splay删除特麻烦...... (0) TN 2005-06-06 11:46:21
  - 怎么麻烦了，把删除的元素调整到跟，然后合并左右子树，怀疑你听的不是这个方法。。。 (0) js05 2005-06-06 11:47:34
    - 不是删除的时候也要展开一下么？ (0) palmtenor 2005-06-06 13:04:54
      - 删除的原理不同，那种删除是当成普通BST删除，然后再调整的。。。 (0) js05 2005-06-06 13:24:44
- 我看的那版splay还有什么zig...zag....太XX了..... (0) palmtenor 2005-06-06 11:46:49
  - 这个就是左旋右旋吧，不知道为什么叫这个名字。。。 (0) js05 2005-06-06 11:48:03
用RK删点法,treap的删除比插入还简单。。。 (0) zhougelin 2005-06-06 13:27:12
- 用RK删点法？ (0) palmtenor 2005-06-06 13:43:03
  - 同不理解，是不是什么把优先级搞小，然后调到顶的方法？ (0) js05 2005-06-06 14:01:57
    - 当然不是，删除不需要旋转 (0) zhougelin 2005-06-06 14:25:46
      - 确实诡异，我还是用我的SPLAY吧。。。 (0) js05 2005-06-06 14:32:31

Post your reply here:

Home Page Go Back To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator