问题标签 [leftist-tree]

关联

让我问这个问题的原因是：

这难道不是行不通吗，因为引用只在方法内部切换？

我正在为即将到来的一些技术面试而学习，并且正在阅读一两年前有关数据结构的演讲幻灯片。

我不清楚为什么左倾堆的最坏情况合并运行时间是 O(log n) 而对于倾斜堆它是 O(n)，当倾斜堆基本上以与左倾堆相同的方式合并时。

左派堆通过选择具有较小根的树并递归地将其右子树与较大的树合并来合并 A 和 B。然后它检查空路径长度，如果它违反左派结构属性，则交换它的两个子树。

倾斜堆做同样的事情，但每次递归合并 A 和 B 时都会盲目地交换它的两个子树。

为什么倾斜堆合并的最坏情况会变成 O(n)？是因为我们不能保证递归合并时的高度限制（因为它每次都在交换边）？这是否与弗洛伊德算法有关，即树中所有节点的高度之和以 O(n) 增长？

我已经实现了removeSelection一个从左派堆中删除特定节点的函数。该代码通过一个哈希表定位节点，该哈希表跟踪已插入堆中的键。然后该节点被渗透到堆的根deleteMin并被调用以删除它。代码似乎在调用的swapWithParent函数中失败了percolateUp，它会产生一个段错误。

这是要从堆上的 main 调用的函数：

percolateUp功能：

swapWithParent功能：

是否有任何地方我可能会取消引用 NULL 指针？我已经检查过了，但我似乎找不到错误。

下午好，我正在尝试实现左派堆，这是我的头文件和头文件的源文件

和源文件

但我收到这些错误，请帮助我为什么会出现这些错误？我已将函数声明为 const，但我没有修改它，所以有什么问题？我只是想定义这个函数，这就是我不会做的做，同样的问题也与root有关，为什么编译器说，我正在尝试更改root的值？isempthy（）函数只是检查是否（root == NULL），但它不会改变它的值，所以我真的困惑，如果我删除 const 关键字，我的代码会编译吗？它不会改变代码的主要行为吗？我是新来的，很抱歉发布这么大的代码，但为了使代码更清晰，我将头文件和源文件一起发布为了简化您的任务，请帮助我，我很高兴有这么好的网站。如果您的错误有帮助，我会很高兴：

左派堆为每个节点维护一个键和一个等级。节点的等级是沿着到叶子的最短路径中的节点数。

整棵树需要维护两个属性：

1. node.key < node.left.key && node.key < node.right.key
2. node.left.rank >= node.right.rank

我可以理解第一个属性，因为它是一个堆并且很自然。

但是第二个属性的目的是什么？为什么我们需要保持右边比左边短？

为了平衡目的？

我有一个（最小）左派堆，如下所示：

我被要求显示插入 21 的结果。我对左派堆的理解是，插入只是单个节点的合并，在这种情况下，应该将 21 与每个右父节点进行比较，直到它到达 16 的 NULL 子节点，并且应该自动放置在那里。我错了吗？它应该去别的地方吗？

我的实现在少量、可追溯的项目上表现正确。这个左派堆需要几秒钟才能插入 50,000 个项目，而倾斜堆需要几毫秒。

所以我相信我已经正确实施了算法，但效率不高。

Irrelevent(?) 代码省略。

因此，我设法使用以下代码获得了二进制左派堆的工作递归版本。

我想知道你们中的任何人是否可以帮助我弄清楚左派堆的 d 堆版本的逻辑和调整代码，这是一个具有 n 个子节点的左派堆。

任何帮助将不胜感激。

最近，我在阅读《Purely-functional-data-structures》一书时，来到 Leftist_tree 的“练习 3.2 直接定义插入而不是通过调用合并”。我实现了我的版本插入。

为了验证它是否有效，我测试了它和本书提供的合并功能。

然后我发现了一件有趣的事情。我使用列表["a";"b";"d";"g";"z";"e";"c"]作为输入来创建这棵树。而且这两种结果是不同的。对于合并方法，我得到了这样的树：

我实现的插入方法给了我这样的树：

我认为这两种方法之间有一些细节，即使我遵循“合并”的实现来设计“插入”版本。但后来我尝试了一个反向列表 ["c";"e";"z";"g";"d";"b";"a"] 它给了我两个leftist-tree-by-insert tree。这真的让我很困惑，以至于我不知道我的插入方法是对还是错。所以现在我有两个问题：

1. 如果我的插入方法是错误的？
2. leftist -tree-by-merge和leftist-tree-by-insert是相同的结构吗？我的意思是这个结果给了我一种幻觉，好像它们在某种意义上是平等的。

整个代码

16. 2015年10月更新

通过更精确地观察这两种实现，很容易发现区别在于合并一个基本树T (1, x, E, E)或插入一个元素x，我用图可以更清楚地表达。

所以我发现我的插入版本总是会使用更多的复杂性来完成他的工作，并且没有利用左派树的优势，或者它总是在更糟糕的情况下工作，即使这种树结构完全是“左派”。

如果我改变了一点，这两个代码将获得相同的结果。

所以对于我的第一个问题：我认为答案并不准确。它可以真正构建一棵左派树，但总是在糟糕的情况下工作。

第二个问题有点无意义（我不确定）。但这种情况仍然很有趣。例如，即使合并版本的工作效率更高，但是从列表中构造树而不需要像我提到的那样插入顺序 (["a";"b";"d";"g";"z"; "e";"c"], ["c";"e";"z";"g";"d";"b";"a"] ，如果顺序不重要，对我来说我认为它们是同一组。）合并功能无法选择更好的解决方案。（我认为 ["a";"b";"d";"g";"z";"e";"c"] 的树结构优于 ["c";"e";" z"；"g"；"d"；"b"；"a"

所以现在我的问题是：

1. 每个亚右脊为 Empty 的树形结构是好结构吗？
2. 如果是，我们可以总是以任何输入顺序构造它吗？

Tarjan 的“数据结构和网络算法”在最左边的堆中声明 heapify 函数如下：

q是我们想一起堆的堆队列。meld(h1, h2)是一个合并两个堆并恢复堆属性的函数。meld(h1, h2)具有复杂性O(logn)，其中n是两个堆中的节点总数。这使得一次通过队列的复杂性如下：

（等式 1）

这是合理的。我没有得到的是整个 heapify 的时间：

（等式 2）

k这是原始堆n的数量和它们包含的项目总数。前面还提到了两个约束：

（等式 3）

有人可以帮我理解 Eq. 2是派生的？（如何解释等式 2 中等式的左表达式）