1

CLRS の Introduction to Algorithms 3rd edition P.525 で、サイズ (x) の下限を分析すると、「ノードに子を追加してもノードのサイズを減らすことができないため、Sk の値が増加するため」と引用した文があります。 k" で単調に。しかし実際には、Sk が k に対して単調に増加するとは限らないことを示す反例を示すことができると思います。次のグラフでは、key=1 のノードの次数は 2 で、次数が 2 のノードは他にありません。つまり、S2=8 です。同様に、Ｓ３＝６である。しかし、現在、S3 は S2 より小さく、つまり、Sk は k に対して単調に増加していません。

2 - 0 - 4 - 2 - 5 - 8 - 7 -  1
            |               /  \
            8              2    9
                              / | \
                             10 14 16
                             |  |
                             11 15

ヒープは、一連のカットとカスケード カットを実行することにより、順不同の二項サブツリーから派生できます。

上記の構造が有効なフィボナッチ ヒープかどうかを知りたいです。もしそうなら、それは有効な反例でもあります。

4

1 に答える 1

2

S kは、すべての可能なフィボナッチ ヒープ内のすべての次数 k サブツリーが少なくとも S k 個の子孫を持つように、最大​​の下限として定義されます。

于 2011-09-03T15:45:11.810 に答える