斐波那契堆中的所有樹都是二叉樹嗎？

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個元素，所以它不是一個二叉樹了。

希望這會有所幫助！