单选题：Which one of the following statements is FALSE?
Which one of the following statements is FALSE? @[B](3)
A. For red-black trees, the total time for $$m$$ consecutive insertions in a tree of $$n$$ nodes is $$O(n+m)$$.
B. To obtain $$O(1)$$ armortized time for the function **decrease-key**, the potential function used for Fibonacci heaps is $$\Phi(H)=t(H) + m(H)$$, where $$t(H)$$ is the number of trees in the root list of heap $$H$$, and $$m(H)$$ is the number of marked nodes in $$H$$.
C. Let $$S(x)$$ be the number of descendants of $$x$$ ($$x$$ included). If the potential function used for splay tree is $$\Phi(T) = \sum_{x\in T}\log S(x)$$ , then the amortized cost of one splay operation is $$O(\log n)$$.
D. In the potential method, the amortized cost of an operation is equal to the actual cost plus the increase in potential due to this operation.
A.For red-black trees, the total time for $$m$$ consecutive insertions in a tree of $$n$$ nodes is $$O(n+m)$$.
B.To obtain $$O(1)$$ armortized time for the function **decrease-key**, the potential function used for Fibonacci heaps is $$\Phi(H)=t(H) + m(H)$$, where $$t(H)$$ is the number of trees in the root list of heap $$H$$, and $$m(H)$$ is the number of marked nodes in $$H$$.
C.Let $$S(x)$$ be the number of descendants of $$x$$ ($$x$$ included). If the potential function used for splay tree is $$\Phi(T) = \sum_{x\in T}\log S(x)$$ , then the amortized cost of one splay operation is $$O(\log n)$$.
D.In the potential method, the amortized cost of an operation is equal to the actual cost plus the increase in potential due to this operation.
答案：B
A. For red-black trees, the total time for $$m$$ consecutive insertions in a tree of $$n$$ nodes is $$O(n+m)$$.
B. To obtain $$O(1)$$ armortized time for the function **decrease-key**, the potential function used for Fibonacci heaps is $$\Phi(H)=t(H) + m(H)$$, where $$t(H)$$ is the number of trees in the root list of heap $$H$$, and $$m(H)$$ is the number of marked nodes in $$H$$.
C. Let $$S(x)$$ be the number of descendants of $$x$$ ($$x$$ included). If the potential function used for splay tree is $$\Phi(T) = \sum_{x\in T}\log S(x)$$ , then the amortized cost of one splay operation is $$O(\log n)$$.
D. In the potential method, the amortized cost of an operation is equal to the actual cost plus the increase in potential due to this operation.
A.For red-black trees, the total time for $$m$$ consecutive insertions in a tree of $$n$$ nodes is $$O(n+m)$$.
B.To obtain $$O(1)$$ armortized time for the function **decrease-key**, the potential function used for Fibonacci heaps is $$\Phi(H)=t(H) + m(H)$$, where $$t(H)$$ is the number of trees in the root list of heap $$H$$, and $$m(H)$$ is the number of marked nodes in $$H$$.
C.Let $$S(x)$$ be the number of descendants of $$x$$ ($$x$$ included). If the potential function used for splay tree is $$\Phi(T) = \sum_{x\in T}\log S(x)$$ , then the amortized cost of one splay operation is $$O(\log n)$$.
D.In the potential method, the amortized cost of an operation is equal to the actual cost plus the increase in potential due to this operation.
答案：B