Replies: 33 comments 9 replies
-
|
旋转的介绍好像咕咕咕了啊 |
Beta Was this translation helpful? Give feedback.
-
|
可以添加图解么....谢谢啦 |
Beta Was this translation helpful? Give feedback.
-
|
@Duliu-Killer 方便开个 issue 吗 |
Beta Was this translation helpful? Give feedback.
-
|
@Duliu-Killer 在这里 https://github.com/OI-wiki/OI-wiki/issues/new/choose |
Beta Was this translation helpful? Give feedback.
-
我也不会啊，所以才来OI-wiki找......当我啥也没说好了，不过还是谢谢您 |
Beta Was this translation helpful? Give feedback.
-
|
@Duliu-Killer 我是说，你把想要添加的内容开个 issue 说清楚。你点链接进去看看（ |
Beta Was this translation helpful? Give feedback.
-
哦抱歉我没明白，我去看一下 |
Beta Was this translation helpful? Give feedback.
-
写好了，谢谢 |
Beta Was this translation helpful? Give feedback.
-
|
是不是可以考虑给出一个Treap更快的函数式实现（ |
Beta Was this translation helpful? Give feedback.
-
|
无旋 Treap 建树那一块，前两种方法咋做到线性的？ |
Beta Was this translation helpful? Give feedback.
-
|
所以还是没人理我…… |
Beta Was this translation helpful? Give feedback.
-
|
del是不是写错了啊，应该只有删除成功的时候才 size[k]--，删掉一个不存在的元素不应该 size[k]-- |
Beta Was this translation helpful? Give feedback.
-
|
CCCCCCCCCCCCCCCCCCCCCCCOrz |
Beta Was this translation helpful? Give feedback.
-
|
为什么不提一下fhq大佬的大名( |
Beta Was this translation helpful? Give feedback.
-
|
无旋转的treap并不是严格的二叉搜索树,存在val[rchild] == val[root]的时候,但是并没有影响,split()总是能正确的切出来. |
Beta Was this translation helpful? Give feedback.
-
我的 pr 刚被 merge，现在的版本有了 |
Beta Was this translation helpful? Give feedback.
-
|
无旋 Treap 一开始格式崩了 |
Beta Was this translation helpful? Give feedback.
-
|
我记得以前的无旋 treap 的代码十分简洁，甚至不需要写注释。看看现在的代码被改成啥样了。 |
Beta Was this translation helpful? Give feedback.
-
你好，我是现在这个版本无旋 treap 的作者，如果改复杂了的话还是很抱歉的。如果你需要看原来版本的话，是可以在 github 上找到的，在这里。个人认为它们主要的思路以及实现方法没有差的很多。 老版本中，没有加入很多完成模板题所需要的函数（如 如果你有更简洁易懂的实现方法，也可以提交一个 pr 或者 issue。 |
Beta Was this translation helpful? Give feedback.
-
|
我认为新版的代码里面的 另外，有的函数的函数名缩写有点严重，比如 |
Beta Was this translation helpful? Give feedback.
-
按排名分裂这里的 命名这方面我感觉注释中讲清楚其实也问题不大，不过如果你觉得不够清晰可以交个 pr 。 |
Beta Was this translation helpful? Give feedback.
-
|
@ttzytt 我的写法与你的写法不太一样，我这边是分裂成两棵子树，如果有单取某个节点的需求再另行分裂。 |
Beta Was this translation helpful? Give feedback.
-
@renbaoshuo 我焯，佬啊，你这个博客是真滴牛皮。刚刚看了下你的代码，感觉你那样写也是比较简洁的，而且似乎跟按值分裂更统一（因为都分成两个）。而且现在无旋 treap 这里没有指针版，建议开个 pr 提交下。 不过我记得我当时写成分裂成三个好像是因为 treap 中可以有重复值，然后重复次数是 这种情况下，如果按照你的方法写： int Treap::getKth(int k) {
auto x = split(root, k - 1);
auto y = split(x.second, 1);
Treap::node *o = y.first;
root = merge(x.first, merge(y.first, y.second));
return o == nullptr ? 0 : o->val;
}这里的 |
Beta Was this translation helpful? Give feedback.
-
|
@ttzytt 这个不是很正常的写法嘛 …… 我记得我当年也是这么写的 …… |
Beta Was this translation helpful? Give feedback.
-
|
请问一下那个在文章最开始的Treap的实例图，是不是与
不太一样？ |
Beta Was this translation helpful? Give feedback.
-
|
这个好像确实，不过这里也说了是可以反过来的，之前画图的时候我可能没注意😂 |
Beta Was this translation helpful? Give feedback.
-
|
哦，明白了，谢谢您。 |
Beta Was this translation helpful? Give feedback.
-
|
对了，请问您用的什么软件画的图，非常漂亮，正好管理员说我的题解图太丑了。 |
Beta Was this translation helpful? Give feedback.
-
|
AxGlyph，不过正版是要钱的 |
Beta Was this translation helpful? Give feedback.
-
|
没有带交集无旋 Treap 合并吗？ |
Beta Was this translation helpful? Give feedback.
This comment has been hidden.
This comment has been hidden.
-
|
我也是这么想的 |
Beta Was this translation helpful? Give feedback.
-
Beta Was this translation helpful? Give feedback.
-
|
修复啦 |
Beta Was this translation helpful? Give feedback.
-
|
指针版代码，太好了 |
Beta Was this translation helpful? Give feedback.
-
|
“节点结构”的代码siz那里的空注释是怎么回事 |
Beta Was this translation helpful? Give feedback.
-
|
应该是前面的人忘记加上了，我开了个pr |
Beta Was this translation helpful? Give feedback.
-
|
现在不空了 |
Beta Was this translation helpful? Give feedback.
-
|
说一个小细节： |
Beta Was this translation helpful? Give feedback.
and others
-
https://oi-wiki.org/ds/treap/
Beta Was this translation helpful? Give feedback.
All reactions