data-structures - 斐波那契堆中的所有树都是二叉树吗？

Question

斐波那契堆是否可能包含一棵不是二叉树的树？如果是这样，这将如何发生？能给我举个例子吗？

Answer 1

是的，这可能发生。直观地说，原因是在斐波那契堆中，减少键操作可以通过从较大的树中切割子树来工作，从而导致两棵树（可能）不是二叉树。这与二项式堆不同，在二项式堆中，reduce-key 通过从其键一直减少到根的节点进行冒泡操作来工作。

看一个具体的例子，让我们在斐波那契堆中插入五个元素，比如 1、3、5、7 和 9。这给出了堆

1 - 3 - 5 - 7 - 9

现在，让我们做一个 dequeue-min，它提取 1。我们现在尝试将所有剩余的元素压缩在一起，合并树如下：

    3
   /|
  5 7
    |
    9

现在，假设我们对 9 的键进行减键操作，将键减至 6。为此，我们从其父节点中切出 9 并将其合并到顶部的树列表中，从而产生

   3 - 6
  /|
 5 7

现在根为 3 的树只包含 3 个元素，所以它不再是二叉树了。

希望这可以帮助！