c++ - 如何在Leonardo堆中找到root的左右孩子？

Question

根据这篇文章，树的根在位置 L(k) - 1。Ltk-1 子树的根在位置 L(k - 1) - 1。Ltk-2 子树的根在位置 L(k) - 2。

有人可以帮我理解这个吗？我正在尝试实现平滑排序。

Answer 1

假设您有一个存储在数组中的 k 阶 Leonardo 堆，并且您递归地进行布局，以便始终布局较大的子树，然后是较小的子树，然后是根节点。这意味着数组中总共有 L(k) 个节点，位置编号为 0、1、2、3...、L(k) - 1。它看起来像这样：

+---------------------------+----------------------+------+
|    Tree of order k - 1    | Tree of order k - 2  | root |
+---------------------------+----------------------+------+

请注意，根在最后，所以它位于 L(k) - 1 位置，因为我们使用的是零索引。

那么这两个子树在哪里呢？好吧，k - 2 阶的子树就在根节点之前。它的布局方式是它的根在最右边。因此，为了找到它的根，我们去到整棵树的根（位置 L(k) - 1）并后退一步到达位置 L(k) - 2。

那么k-1阶的子树呢？好吧，请注意它舒适地位于我们代表的前面。它的根节点将位于该块的末尾，位于位置 L(k - 1) - 1 处（类似于我们较大的 k 阶树的根在位置 L(k) - 1 处。）

希望你喜欢我的文章！:-)