8

在论文Purely Functional Data Structures的第 6.3.1 章中,说:

然后,每当我们从一个新元素和一个秩为 0...r-1 的树段创建新树时,我们只需将新元素与段中的第一个根(即秩 0 树的根)进行比较)。较小的元素成为新的根,较大的元素成为根的 0 级子元素。

  1. T0' 是新树的等级为 0
  2. T0..T(r-1) 是 0 到 r-1 级的原始树
  3. 较小的元素成为新的根,较大的元素成为根的 0 级子元素

问题是第 3 步导致两棵 1 级树,这与二项式堆冲突。

我是不是误会了?

4

1 回答 1

4

我们正在创建一个等级为 r 的树。秩为 r 的树的结构是一个根节点,其 r 个子节点的秩为 0..r-1。

您引用的部分是什么意思。

  1. 当我们得到一个新元素 x 时,我们将它与 T0 中的元素进行比较
  2. 我们创建一个包含两个比较元素中较大者的等级为 0 的新树 T0'
  3. 我们创建一个新节点 T 包含两个比较元素中较小的一个,并以 T0',T1,T2...T(r-1) 作为子节点

现在 T 是秩为 r 的二叉树,它是堆顺序的。

于 2011-11-23T10:20:14.197 回答