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

Question

Fibonacci堆可能包含不是二叉树的树吗？如果是这样，这将如何发生？你能给个例子吗？

Answer 1

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

要查看一个具体的例子，让我们插入五行成斐波那契堆，说，1，3，5，7和9。这给出了堆

1 - 3 - 5 - 7 - 9 

现在，让我们做一个dequeue-分钟，其提取1.我们现在尝试压缩所有剩余的元素结合在一起，它融合了树如下：

3 
    /| 
    5 7 
    | 
    9 

现在，假设我们做的下降键操作以减少9的关键为了做到这一点，我们从其父母中减去9，并将其合并到顶部的树木列表中，得到

3 - 6 
    /| 
5 7 

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

希望这会有所帮助！