问题标签 [treap]

我正在用Java 构建一个trap 类。下面是我将新节点添加到 treap 的函数。过程是：向下遍历treap的底部（同时将路径中的每个节点添加到本地堆栈）首先只担心BST结构，然后，一旦到达底部，我将通过旋转重新建立堆不变量，利用我建立的堆栈。

听起来它应该可以工作，但我不断收到 EmptyStackException。一旦调用私有“reheap”函数，就会发生此异常。

add 函数适用于添加到 treap 的第一个节点，例如，如果我这样做了：testTree.add (4 ,19); 但是在第二次添加节点时失败，就像我然后调用： testTree.add (2 ,31);

这是完整的错误：

130——指在add函数底部调用reheap 137——指私有reheap函数的while循环 220——指我尝试在main中添加新节点。

我试过改变 reheap 函数中的条件，但无济于事。

在第二次调用（testTree.add (2 ,31); ）之后，我应该得到一个结构（ Node(2, null, Node(4)) ）的陷阱。<-- 这当然是在重新堆放之后。

我正在创建一个陷阱，我想知道哪个随机数生成器最适合在插入时生成优先级。

数据集长约 6000 条。

我正在修改提供给我们的现有模板类（主要是声明的没有定义的方法）。预定义的生成器std::default_random_engine仅生成伪随机数。我想知道，这个生成器是否足够，如果没有，有什么替代方案？数据将一次性从文件中读取。

随机数生成器声明为：

仅在包装类的构造函数中创建时使用

我希望尽可能少地发生碰撞。是否std::default_random_engine* generator_;足以实现没有碰撞，或者是否需要其他发电机？

编辑：我更喜欢均匀分布，或者接近它的东西。然而，正态分布也可能起作用。

指向生成器的指针在给定的代码中，乍一看它并没有作为缺陷出现。

我在将 Treapnode 插入 treap 时遇到问题。它接受 3 个参数。添加（E键，P优先级，treapnode x）。我已经尝试了很多事情并不断收到空指针异常。

我尝试在左右树中检查 null 情况。

我正在尝试使用 Treap 数据结构实现动态图。

这是节点结构：

当我想将相邻节点添加到特定节点时，

1. 我搜索节点，然后 vector<int> neighbourNode通过updateNode()以下方式将相邻节点添加到搜索节点。

searchAddress->neighbourNode.push_back(x);

但是我的教授说，vector<int> neighbourNode在节点中存储地址。

1. 它会减少我的 TreapNode 大小吗？
2. 如何存储地址和访问它？我在 TreapNode 类中尝试过这种方式，但它给出了neighbourNodeundefine 错误。

int* neighbourNodeAddress = neighbourNode.data()

谁能帮我 ？

据说 Treap 的高度按顺序是对数的。但是在按顺序对给定键(1,2),(1,3),(3,4),(4,5)执行在线插入时，treap 的高度是输入的顺序。

所以最坏情况的复杂性变成了线性的。有什么建议么。

我想通过向树中添加元素来构建一个随机搜索树。从链接中的伪代码工作：

我已经走到了这一步：

看这个旋转：

我想分配 E3._right = G7。但是，我如何连接连接到 G7 的任何东西，即它是 E3 的父级？

任何帮助都非常感谢，我一直以这种方式坐了很久......

您好，所以我正在研究我的 treap 方法，该方法需要一个 Stack 来跟踪它经过的节点列表，并通过在最后执行一个旋转列表来维护堆属性。但是，当我运行此代码时，它会为我的旋转方法提供 nullPointerException()。不知道我做错了什么。这是我的节点和 Treap 类的链接。 我的节点和 Treap 类代码

Valgrind 在实现 Treap 数据结构时会在该程序中抛出错误。无法弄清楚如何解决这个问题。试图写一个析构函数，没有任何改变。为简单起见，不包括其余代码。错误出现在这部分代码中。

///////////////////////////////////////// ////////////////