data-structures - 在斐波那契堆中标记一些节点的目的是什么？

Question

此 picture来自 Wikipedia article有三个用蓝色标记的斐波那契堆节点。在此数据结构中标记某些节点的目的是什么？

Answer 1

直观地说，斐波那契堆维护了一组不同顺序的树，在发生删除分钟时将它们合并。构建斐波那契堆的希望是每棵树都拥有大量节点。每棵树中的节点越多，需要存储在树中的树的数量就越少，因此在每个删除分钟上合并树所花费的时间就越少。

同时，斐波那契堆尝试尽可能快地进行减键操作。为此，斐波那契堆允许从其他树中“切出”子树并向上移回根。这使得减少键更快，但使每棵树包含更少的节点(并且还增加了树的数量)。因此，在设计结构中存在基本张力。

为了让它起作用，斐波那契堆中树的形状必须受到一定的限制。直觉上，斐波那契堆中的树是 binomial trees允许失去少数 child 。具体来说，Fibonacci 堆中的每棵树最多可以丢失两个子树，然后该树需要在后面的步骤“重新处理”。斐波那契堆中的标记步骤允许数据结构计算到目前为止丢失了多少 child 。一个未标记的节点没有丢失任何 child ，而一个标记的节点丢失了一个 child 。一旦一个标记节点失去了另一个 child ，它就失去了两个 child ，因此需要移回根列表进行重新处理。

许多介绍性算法教科书都记录了为什么这样做的细节。这并不明显，这应该有效，而且数学有点棘手。

希望这提供了一个有用的直觉!