问题标签 [treap]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
0 回答
86 浏览

c - 具有多个相等键的平衡搜索树(Treap)

我必须创建一个具有多个相等键的平衡搜索树。我实现了我需要的功能:

我遇到的问题是从树中删除(stergere)一个节点。如果我尝试删除唯一键,它可以工作,但如果我尝试删除非唯一键,它会崩溃。

它有效,但是:

它不是。

我应该如何修改这个功能?

0 投票
2 回答
1127 浏览

algorithm - 如何为 Treap 节点生成随机优先级?

在我在网上看到的大多数示例中,都认为有某种外部随机数生成器会产生随机(不同的!)优先级。

据我回忆,有一种方法可以实际随机生成优先级,并且在将它们插入到treap 中以解开可能的优先级冲突时。

那我有两个问题:

  1. treaps 是否真的需要使其优先级完全不同,或者只需要比较可能最终被比较的节点的优先级?也就是说,如果我有两个具有优先级的节点,p但我可以确保它们永远不会以任何方式相遇,那么让它们具有相同的优先级会有问题吗?
  2. 我应该如何在我的陷阱中生成和解开优先级?

谢谢

编辑:这是我在说什么的描述:

问题 8.12 @随机算法

现在让我们分析实现一个trap操作所需的随机位数。假设我们从单位区间 [0,1] 中均匀地随机选取每个优先级 Pi。然后,每个 Pi 的二进制表示可以生成为(可能是无限的)位序列,这些位序列是无偏掷硬币的结果。这个想法是在这个序列中只生成与解决不同优先级之间的比较所需的一样多的位。假设我们只生成了treap T 中元素优先级的二进制表示的一些前缀。现在,在插入项目y 时,我们将其优先级Py 与其他优先级进行比较以确定y 应该如何旋转。在将 Py 与一些 PI 进行比较时。如果他们当前的部分二进制表示可以解决比较,那么我们就完成了。否则。它们具有相同的部分二进制表示,我们不断为每个生成更多位,直到它们首先不同。

0 投票
3 回答
103 浏览

c++ - 将指针传递给函数和将指针的引用传递给函数有什么区别?

所以,我有一个结构

然后,有

明白的是这个功能:

据我了解,我们将ttotsplit()作为指向结构的指针传递,而不是将指针的两个引用传递给相同类型的结构。为什么我们不能只传递指针而不是它们的引用?这有什么意义吗?

0 投票
0 回答
36 浏览

data-structures - 此代码如何生成随机数?

我现在正在学习treap,我遇到了一个实现,其中那个家伙使用了一些奇怪的方式来生成优先级的随机数。我无法得到它。有人介意解释一下它是如何工作的。

0 投票
1 回答
1875 浏览

c++ - 哪种数据结构最适合实现字典?

我必须编写一个字典程序作为数据结构和算法本科课程的学期项目,并且我希望找到最合适的解决方案(数据结构)来解决这个问题。

我考虑使用哈希表trie。有人建议我使用陷阱,但还没有能够调查它们。

我的数据库有大约 10 万个不同的单词及其含义。该程序预计提供的基本功能是插入更新删除搜索单词/定义。如果我设法挤入自动完成拼写纠正,那将是一个额外的好处。

所以,我的问题是,请记住我的要求,哪种数据结构最适合我的目的。当我说“最佳”时,我要求的是具有最佳运行时复杂性和低成本(内存要求)的数据结构。

另外,我希望能够有一个算法,它返回所有以给定前缀开头的单词。例如,假设我进行了一个函数调用,它应该返回一个以,等dictionary.getWordsStartingWith("fic")开头的所有单词的列表。我知道如果我将字典实现为 trie,我可以做到这一点,我可以做到这一点,但这可能吗用哈希表来做?ficfictionfictitiousfickle

0 投票
0 回答
67 浏览

c++ - 在一些特殊的未知情况下出现段错误,让我抓狂

我已经调试了一整天,我真的完全迷失了。帮助!我在 Visual Studio 本地测试了大量案例。它工作正常。但是在我们学校的在线裁判系统上,有几个案例报告了RE(exitcode 6),这意味着一个段故障问题。我真的不知道在这些案例中发生了什么,所有随机案例都在本地完美运行。我检查了可能导致段错误的问题列表。我只是无法解决,所以请帮忙。它真的让我发疯。

注意:这是一个陷阱。数据结构中有更多代码,但其余代码正常,因此我尝试提取所有相关代码。我确定该treapNode* treap::deleteNode(valueType value)函数触发了段错误问题。如果您发现有任何遗漏,请告诉我。

我真的很抱歉它看起来这么长......对我的编码有什么建议吗?我真的很感激!

- - - - - - - - - -更新 - - - - - - - - - - -

好的,我会把我所有的代码放在这里,这样你就更容易了。顺便说一句,我无法访问类似 UNIX 的平台...

-------------------更新输入格式----------------

一个例子:

oj 承诺不插入已经存在的数字,也不删除不存在的等级。

0 投票
1 回答
356 浏览

c++ - treap 如何帮助更新这个有序队列?

我无法理解这个解决HackerRank问题的方法。请参阅下面的解决方案代码,显然是由 Kimiyuki Onaka 提供的。

问题是:给定一个唯一数字列表,以及m类型为 " move the current ith to jth elements (l,r) to the beginning" 的查询,返回数字的最终排列。

Onaka 建议使用treap 数据结构(同时维护优先级和二分查找)可以帮助解决O(m log n). 由于我不精通 C++,我尝试过但未能概念化如何使用陷阱。我的理解是,要解决问题,您需要log时间访问当前ith to jth元素以及log当前第一个元素和整体顺序的时间更新。但我看不出如何概念化它。

理想情况下,我想用文字解释它是如何完成的。或者,只是解释 Onaka 的代码在做什么。

谢谢!

0 投票
1 回答
1049 浏览

algorithm - 在实践中哪个更快:Treap 或 Splay 树?

我已经学习了TreapSplay ,并使用它们解决了一些问题。
理论上,它们的平均复杂度为O(log n),但在最坏的情况下,Treap 的复杂度为O(n),而Splay 树的平均复杂度为 O (log n)

Treap在哪种情况下会出现最坏的情况(因为它的优先级是随机选择的),并且Treap真的比Splay 慢吗?我已经使用 Splay treeTreap解决了 SPOJ 上的一些任务,使用Treap的解决方案比使用 Splay tree的解决方案要快一些(大约0.2s)。那么哪个实际上更快,我应该主要使用哪个以及何时使用?

0 投票
1 回答
601 浏览

data-structures - trep数据结构的用处是什么?

我目前正在研究高级数据结构,我遇到了一种叫做 Treap 的奇怪数据结构。我了解 Treap 是什么,但我似乎无法在有效的用例场景中找到它的实用性。

为什么要使用这样的数据结构以及在什么类型的问题/条件下最好使用陷阱?

我发现自己更喜欢使用哈希映射、最小/最大堆、二叉搜索树或平衡二叉搜索树,但我不知道为什么要使用 treap。

0 投票
1 回答
44 浏览

c++ - treap 中的旋转是否会违反它的堆排序或二叉搜索树的顺序?

我不确定我是否可以违反treap 的堆排序,或者它是具有左和/或右旋转方法的二叉搜索树结构。

这是左旋转的代码

和右旋转

我希望这些轮换不会违反堆排序和二叉搜索树的结构。