作者justim (透明石油)
看板Prob_Solve
标题[问题] 费氏伫列的问题
时间Sat May 10 14:33:38 2008
最近在读有关 Fibonacci Heap 的资料 (Horowitz 那本书)，
读到 cascading cut 那节有点疑惑。照书中的描述是，若一
个 node 之前曾经失去过一个 sub-tree，之後再被移去一个
sub-tree 的话，那就要启动 cascading cut 的操作。
我的问题是：这样设计背後的理念是什麽？
书上用了一整段来说明，我浓缩一下：
那是为了保证每个 degree 为 k 的 min-tree 都至少
有 c^k 的 nodes (for some c, c > 1)。
请问我的理解是正确的吗？
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.116.247.169