Tree

树结构

有根树

有根树（Rooted Tree）是一种特殊的树结构，它明确指定了树中的一个节点作为 根节点（Root） 。一旦确定了根节点，树中所有其他节点之间的关系（如父子、祖先、后代等）也就随之确定了。在计算机科学和数据结构的背景下，当我们提到“树（Tree）”时， 默认指的几乎都是有根树（Rooted Tree） 。

由于树是特殊的图，因此在图论中，当讨论到最小生成树（MST）时，我们才会讨论到无根树。

二叉树

二叉树（Binary Tree） 是一种特殊的树结构：每个节点最多只能有两个子节点。一个节点左边的叫左子树（left subtree），右边的叫右子树（right subtree）。

遍历

针对二叉树的特殊结构，有三种独有的遍历术语：前序遍历、中序遍历、后序遍历。

前序遍历

前序遍历的访问顺序被精确定义为：

\[ \text{访问根节点} \rightarrow \text{遍历左子树} \rightarrow \text{遍历右子树} \]

.

中序遍历

中序遍历的访问顺序被精确定义为：

\[ \text{遍历左子树} \rightarrow \text{访问根节点} \rightarrow \text{遍历右子树} \]

因此中序遍历是二叉树独有的一种遍历方式，同时也产生了前驱和后继的独有概念。前驱和后继参见BST的相关章节。

后序遍历

后序遍历的访问顺序被精确定义为：

\[ \text{遍历左子树} \rightarrow \text{遍历右子树} \rightarrow \text{访问根节点} \]

在计算机内存操作中，这是删除或销毁一棵树的最安全方式，因为它总是先处理子节点，最后才处理父节点，从而可以保证在处理父节点的时候，其所有依赖的子节点都已被清理或释放，避免悬空指针。

后序遍历适用于需要先计算子节点属性再汇总到父节点的场景（例如，计算每棵子树的高度、权重或路径）。

完全二叉树

完全二叉树（Complete Binary Tree） 除了最底层，其他层的节点都是满的，而且最底层的节点都靠左填充。这使得由于没有空隙，我们可以用数组来紧凑地存储它，而不需要指针。

数组下标从0开始的话：

• 父节点：\((i-1)//2\)
• 左孩子：\(2i+1\)
• 右孩子：\(2i+2\)

数组下标从1开始的话：

• 父节点：\(i//2\)
• 左孩子：\(2i\)
• 右孩子：\(2i+1\)

下面这个是一个合格的完全二叉树：

        A
      /   \
     B     C
    / \   /
   D   E F

下面这个则不是完全二叉树：（从右边开始长，D左边是空的）

        A
      /   \
     B     C
      \   
       D

.

满二叉树

满二叉树（Full Binary Tree） 每一层的节点数都达到最大值。

例如：

       A
      /   \
     B     C
    / \    / \
   D  E  F   G

满二叉树 ⊂ 完全二叉树 ⊂ 普通二叉树

BST

二叉搜索树（Binary Search Tree） 是一种特殊的二叉树，它具有以下关键性质，使得其在查找、插入和删除操作上效率较高：

• 对于树中任一节点，如果左子树不为空，那么左子树上所有节点都小于该节点的值
• 对于树中任一节点，如果右子树不为空，那么右子树上所有节点都大于该节点的值
• 任一节点的左子树和右子树也必须是二叉搜索树

简单来说就是左边小、右边大。因此通过中序遍历，可以得到一个升序的序列，这也是用来验证一棵树是否是BST的常见方法。

BST 的所有基本操作（查找、插入、删除）的时间复杂度都与树的高度成正比：

操作	平均时间复杂度	最坏时间复杂度
查找	\(O(\log n)\)	\(O(n)\)
插入	\(O(\log n)\)	\(O(n)\)
删除	\(O(\log n)\)	\(O(n)\)

其中最坏情况是，当元素按升序或降序插入时，BST 会退化成一个 链表 ，此时高度为 \(n\)，操作的最坏时间复杂度为 \(O(n)\)。

前驱与后继

前驱（Predecessor）与后继（Susccessor） 是二叉树的独有概念，他们都是建立在中序遍历之上的。

当一个二叉树进行中序遍历后，节点 \(x\) 的前驱是中序遍历序列中紧邻在 \(x\) 之前的那个节点，节点 \(x\) 的后继是中序遍历序列中紧邻在 \(x\) 之后的那个节点。

在BST中，前驱就是树中键值小于 \(x\) 键值的所有节点中，键值最大的那个节点；后继就是树中键值大于 \(x\) 键值的所有节点中，键值最小的那个节点。具体的内容请参见BST和BBST的相关内容。

LCA 最小公共祖先

最小公共祖先（Lowest Common Ancestor, LCA）的意思是：给定树中的两个节点 \(u\) 和 \(v\)，它们的最小公共祖先 \(LCA(u, v)\) 是树中同时是 \(u\) 和 \(v\) 的 祖先 ，并且距离根节点 最远 （即深度最大）的那个节点。

LCA并不是BST的独有概念，在所有有根树中都适用。但是在BST中，因为BST的有序性，使得查找LCA非常高效。

其核心思路是：从根节点开始，如果两个目标节点 \(p\) 和 \(q\) 分别位于当前节点的左右子树，则当前节点即为 LCA；如果都小于当前节点，则向左子树递归；如果都大于当前节点，则向右子树递归。

BBST

BST在构建时不会调整自身结构，因而如果按顺序插入有序的数据（例如 \(10, 15, 20\)），树会退化为一条链表：

\[ \begin{array}{c} 10 \\ \backslash \\ 15 \\ \backslash \\ 20 \end{array} \]

在这种情况下，搜索、插入和删除操作的时间复杂度从最优的 \(O(\log N)\) 退化到了最坏的 \(O(N)\) 。

AVL Tree

AVL 树通过检查每个节点的 平衡因子 来判断是否失衡。

平衡因子 (Balance Factor) = 左子树的高度 - 右子树的高度

对于一棵 AVL 树中的任意节点，其平衡因子 \(BF\) 必须满足：

\[ |BF| \le 1 \quad \text{或} \quad -1 \le BF \le 1 \]

• \(BF = 1\): 左子树比右子树高 1 层（左重）。
• \(BF = 0\): 左右子树高度相等。
• \(BF = -1\): 右子树比左子树高 1 层（右重）。

当 \(|BF| > 1\) 时，树失衡，需要进行旋转操作来重新平衡。

旋转

旋转是 AVL 树保持平衡的核心机制。它只改变局部节点之间的父子关系，不影响更高层级的连接。旋转操作主要有两种：右旋 (Right Rotation) 和 左旋 (Left Rotation) 。

这里要注意，旋转只改变局部关系，而不影响更高层级的关系，所以只有要旋转的对象是root的时候，整棵树才会旋转。

例：

        2
       / \
      0   7
     / \ / \
   -1  1 5  9
         /
        4
       /
      3

这棵树右侧太深，我们对7进行旋转；由于旋转只改变局部关系，因此我们只看node 7的部分：

     7
    / \
   5   9
  /
 4
/
3

这里我们把要旋转的7称为x，那么有：

RightRotate(x):
    y = x.left
    x.left = y.right
    y.right = x

由于这里y.right不存在，所以旋转后如下：

      5
     / \
    4   7
   /   / \
  3   (空) 9

把新的局部根节点5接回原本的tree：

         2
       /  \
      0    5
     / \  / \
   -1  1  4  7
            / \
           3   9

这样就得到了旋转后的tree。

四种失衡

根据失衡发生的位置，可以分为四种类型，其中 \(x\) 是离插入/删除节点最近的、且 \(|BF|>1\) 的祖先节点。

当左子树过重且失衡发生在左子树的时候，称为LL型失衡，这种情况需要右旋：

            50
           /  \
         30    70
        / \
      20  40
     /
   10
  /
 5

当右子树过重且失衡发生在右子树的时候，称为RR型失衡，这种情况需要左旋：

       30
      /  \
    20    40
           \
            50
              \
               60
                 \
                  70

当左子树过重，但失衡发生在右子树时，称为LR型失衡，这种情况需要先对y左旋再对x右旋：

           50
          /  \
        30    70
       / \
     20  40
         /
        35
          \
           37

当右子树过重，但失衡发生在左子树时，称为RL型失衡，这种情况需要先对y右旋再对x左旋：

        40
       /  \
     20    60
           / \
         50   70
           \
            55
             \
              53

.

红黑树

CLRS13

insert, fixup

红黑树是一种特殊的BST，因此BST的性质在红黑树中也是可以使用的。

注意RB Tree中的叶子节点指的是NIL（Null）节点，也称为 哨兵节点（Sentinel Node）。

红黑树必须满足以下要求：

1. 每个节点要么是红色，要么是黑色
2. Root是黑色
3. NIL节点是黑色
4. 如果一个节点是红色的，那么他的两个子节点都是黑色的
5. 从任意一个节点到其所有叶子节点的路径上，黑色节点的数量相同，这一数量称为该节点的 黑高（Black Height）。

OS-SELECT

基于 红黑树 （一种 BBST）的数据结构，称为 顺序统计树 （Order-Statistic Tree）。该树在每个节点上额外存储了其 子树的大小 。使用此信息，查找第 \(k\) 小的元素的操作（即 \(\text{OS-SELECT}\)）可以在 \(O(\log n)\) 时间内完成。

从逻辑上看，OS-SELECT是一个经典的递归过程：

OS-SELECT(x, i):
    r = x.left.size + 1
    if i == r:
        return x
    elif i < r:
        return OS-SELECT(x.left, i)  // 递归调用
    else:
        return OS-SELECT(x.right, i - r) // 递归调用

由于 \(\text{OS-SELECT}\) 是一种 尾递归 （Tail Recursion）形式（每次调用时，函数要么返回，要么在末尾进行一次对自身的新调用），它可以很方便地转换为迭代实现，这是 CLRS 中常用的方式，以避免深层递归带来的栈溢出风险和函数调用开销。

OS-SELECT(T, i):
    x = T.root
    while x != NIL:
        r = x.left.size + 1
        if i == r:
            return x  // 找到并返回
        elif i < r:
            x = x.left  // 移动到左子树
        else:
            i = i - r   // 更新目标秩
            x = x.right // 移动到右子树
    return NIL

.

堆

二叉堆

二叉堆在结构上是完全二叉树，因此可以用数组存储。

数组下标从0开始的话：

• 父节点：\((i-1)//2\)
• 左孩子：\(2i+1\)
• 右孩子：\(2i+2\)

数组下标从1开始的话：

• 父节点：\(i//2\)
• 左孩子：\(2i\)
• 右孩子：\(2i+1\)

上图展示了二叉堆的树结构和数组存储。

二叉堆分为最大堆（Max Heap）和最小堆（Min Heap）：

• 在最大堆中，任何一个父节点的值，都大于或等于它的左、右孩子节点的值。堆顶（根节点）是整个堆中的最大元素。
• 在最小堆中，任何一个父节点的值，都小于或等于它的左、右孩子节点的值。堆顶（根节点）是整个堆中的最小元素。

二叉堆的高效在于它维护顺序的方式。我们不需要让整个数组有序，只需要维持父子之间的关系即可。

---

核心操作

下面我们以最小堆为例，讲解二叉堆的核心操作。在python的实现中，heapq默认采用的是最小堆，最大堆则可以通过存储相反数来实现。

（1）Find-Min (获取最小值)

这是二叉堆最简单的操作。根据堆序性，小顶堆的根节点永远是整个堆中最小的元素。在数组表示中，它永远位于索引 0。

• 复杂度： \(O(1)\)

---

（2）Delete-Min (删除最小值)

删除堆顶元素，并重新恢复堆序性。这个过程通过下沉 (Sift Down) 来实现。

• 逻辑步骤：
  1. 移除： 移除索引 0 的元素（这就是我们要返回的最小值）。
  2. 替补： 将数组 最后一个元素 （也就是堆中最深、最右的叶子节点）移动到索引 0 填补空缺。
  3. 比较： 将新的根节点与它的左、右孩子进行比较。
  4. 交换（下沉）： 如果根节点比孩子节点大，就将它与较小的那个孩子交换（确保最小的浮上来）。
  5. 重复： 重复步骤 3-4，直到该节点比它的两个孩子都小，或者该节点已经沉到了叶子节点位置。
• 复杂度： \(O(\log n)\)。因为最坏情况是从树根沉到树底，路径长度为树高。

---

（3）Decrease-Key (降低键值)

如果某个节点的值变小，那么我们就需要让它一路上浮（Sift Up），直到重新满足最小堆的性质。

• 前提： 你通常需要一个额外的机制（如哈希表）来快速知道目标元素在堆数组中的当前索引位置 \(i\)。
• 逻辑步骤：
  1. 修改： 将索引 \(i\) 处的元素值减小。
  2. 判断： 因为变小了，它可能比它的父节点更小，违反了堆序性。
  3. 交换（上浮）： 如果它比父节点小，就和父节点交换。
  4. 重复： 重复比较和交换，直到它比父节点大，或者它已经变成了根节点。
• 复杂度： \(O(\log n)\)。最坏情况是从底部浮到根部。

值得注意的是，我们一般只统计Decrease-Key的时间复杂度，因为Increase-Key本质上就是执行Sift Down操作，这一点在上面的Delete-Min

---

（4）Insert (插入)

插入新元素，本质上是 Decrease-Key 的一种特殊形式（或者说依赖相同的“上浮”机制）。

• 逻辑步骤：
  1. 添加： 将新元素放到数组的 末尾 （也就是堆的最后一个叶子节点之后），保持完全二叉树的形状。
  2. 上浮： 执行与 Decrease-Key 相同的上浮逻辑，如果新节点比父节点小，就不断交换上去。
• 复杂度： \(O(\log n)\)。

---

（5）Make-Heap (建堆)

给定一个无序数组，将其转化为符合堆序性的二叉堆。

我们可以通过最小化堆MIN-HEAPIFY操作来实现建堆。MIN-HEAPIFY(A, i) 的任务是：假设左右子树已经是堆了，但根节点 \(i\) 可能太大，不符合最小堆性质，要把 \(i\) “沉”到合适的位置。其核心思路就是：

1. 假设节点i的左右子树已经是堆，然而i太大，需要下沉
2. 先选出i, i的左孩子，i的右孩子这三者中最小值
3. 如果最小值不是i，则交换i和最小值，然后对交换后的再次使用MIN-HEAPIFY。

伪代码如下：

MIN-HEAPIFY(A, i)
    l = LEFT(i)
    r = RIGHT(i)
    if l <= A.heap-size and A[l] < A[i]
        smallest = l
    else smallest = i
    if r <= A.heap-size and A[r] < A[smallest]
        smallest = r
    if smallest != i
        exchange A[i] with A[smallest]
        MIN-HEAPIFY(A, smallest)

熟悉上述操作后，建堆就很好理解了：我们对所有非叶子节点执行MIN-HEAPIFY操作：

BUILD-MIN-HEAP(A)
    A.heap-size = A.length
    for i = floor(A.length/2) downto 1
        MIN-HEAPIFY(A, i)

循环的起点设在 floor(A.length/2)，这正是 最后一个有孩子的节点 （也就是最后一个非叶子节点）。从这里开始downto 1（自底向上）进行倒序遍历，这是建堆成功的绝对前提。

最后我们来分析时间复杂度，MIN-HEAPIFY是O(logN)，所有非叶子节点是(1/2)N，似乎看起来是O(NlogN)，然而，我们必须意识到，我们在进行倒序遍历的时候，最开始遍历的那个特别小的堆，其高度很低，但却占据了总数的一半！所以我们需要把每一层的节点数量正确的加起来：

\[ T(n) = \sum (\text{节点数} \times \text{下沉高度}) \]

总开销公式为：

\[ T(n) = n \times \sum_{h=0}^{\log n} \frac{h}{2^{h+1}} \]

上式右边是一个级数求和公式，其结果收敛于1，因此：

\[ T(n) = n \times 1 = O(n) \]

这个结论非常重要，一定要记住：二叉堆建堆的时间复杂度是O(n)。

---

（6）Meld (合并)

将两个二叉堆 \(H_1\) 和 \(H_2\) 合并成一个新的二叉堆。这是二叉堆的弱点。 由于二叉堆是紧凑的数组结构，你不能像链表那样简单地通过改变指针来合并。标准的做法通常是：将其中一个堆的所有元素取出来，Insert 到另一个堆中；或者将两个数组拼接后重新运行 Make-Heap。

• 复杂度： \(O(n)\) (其中 \(n\) 是总元素个数)。

如果你需要频繁合并堆，二叉堆不是好选择。 左偏树 (Leftist Heap) 、二项堆 (Binomial Heap) 或 斐波那契堆 (Fibonacci Heap) 可以将 Meld 操作优化到 \(O(\log n)\) 甚至 \(O(1)\)。

斐波那契堆

斐波那契堆 (Fibonacci Heap) 是一种计算机科学中用于实现优先队列 (Priority Queue) 的高级数据结构。它由 Michael Fredman 和 Robert Tarjan 在 1984 年发明。之所以叫“斐波那契堆”，是因为在分析其时间复杂度时，斐波那契数（Fibonacci numbers）起到了关键作用。

我们可以看到，斐波那契堆在理论实现上是最高效的堆实现方式，这也是为什么算法教材一定会讲斐波那契堆的原因。然而在实践中，几乎所有的主流用法都是默认使用Binary Heap（二叉堆） 的，这是因为二叉堆可以用数组直接存储，而不需要像链表那样存一大堆指针。由于指针操作的存在，在实际使用中，特别是数据量并非巨大时，斐波那契堆甚至跑不过最简单的二叉堆。

值得注意的是Paring Heap，在很多实践中表现非常好，因此是二叉堆之外少有的实践中还会被使用的实现方法。它的结构比斐波那契堆简单得多，虽然理论上 Decrease-Key 是 \(O(\log \log n)\)（比斐波那契堆的 \(O(1)\) 差一点），但在实际测试中，它往往跑得比斐波那契堆快。

---

我们来简单看一下斐波那契堆（Fibonacci Heap） 是什么，和二叉堆有什么区别。

二叉堆是一颗具备严格大小关系的树，而斐波那契堆实质上是一堆树的集合（森林）。每棵树都不一定是二叉树，每个节点可以有任意多个孩子。所有树的根节点通过双向链表串在一起（根链表，Root List），我们只需要手中时刻掌握最小的根节点指针（min pointer）。

在二叉堆中，我们每次插入或者删除，都要重新调整堆，来保证他是一颗符合堆性质的完全二叉树。而斐波那契堆则采用了不同的策略：只有在EXTRACT-MIN时才进行整理，这叫做懒惰策略。

斐波那契堆不需要遵从完全二叉树的要求，但是依然需要遵从堆性质：根节点（最小堆时）小于等于或（最大堆时）大于等于子节点。换言之，斐波那契堆可以不是完全二叉树，并且可以包含多棵树：

我们把所有树的根节点存储在一个双向链表中，即根链表（Root List）。我们记录最小节点的位置（Min Pointer），实现O(1)的FIND-MIN。

不仅如此，实际上斐波那契堆在每一颗树的每一层中，依然用一个双向链表，将所有的兄弟们连接起来，从而获得一个兄弟链表（Sibling List）。

如此一来，对于INSERT操作，我们直接创建一个新节点，插入到根链表中，通常是直接插在MIN-POINTER旁边；如果比MIN-POINTER小，就让min指针指向新插入的节点。这样一来，INSERT就能O(1)实现。

对于UNION操作，由于两个斐波那契堆H1和H2有两个根列表，那么我们只要把H1的尾巴断开，连在H2的头上；然后把H2的尾巴断开，连在H1的投上；接着对比H1.min和H2.min，让更小的那个成为新的min指针指向的对象，合并就完成了，耗时O(1)。

总结来说：

• 插入：直接把新的节点扔到根链表里，因此是O(1)
• 合并：把两个堆的根链表串起来就不管了，所以是O(1)
• Decrease-Key：某个节点的值变小的时候，不进行交换上浮操作，而是直接把该节点从它的父节点下面剪断（Cut），把它变成一颗独立的树，扔到根链表中。因此该操作是O(1) amortized。

这三点的优化便是斐波那契堆的特长所在。

---

Decrease-Key

这里特别提一下Decrease-Key操作。 首先回顾一下度数（degree）的概念：度数就是直接的孩子的数量，一个根节点如果直接与3个孩子相连，那么该根节点的度数就是3。注意，孙子、重孙子都不算在度数中。这其实是图论中的概念，树就是特殊的图。

如果我们随意Cut，那么有没有可能会出现这么一种情况：孙子都Cut没了，但是孩子都还在，导致树的节点数量大大减少，但是根节点的度数一点都没减少？

为了避免Cut可能导致的这种畸形，在Cut的时候，我们采用级联剪切（Cascading Cut） 的方式：作为一个中间层的父节点，在你自己被剪断之前，你只被允许弄丢 1 个孩子。 当根节点的孩子A的孩子被剪掉后，我们立马标记A为marked。这个时候，如果我们继续剪掉A的孩子，那么由于A已经被标记为marked，此时我们就必须把A剪掉，移出根节点。

如下图所示：

我们对5进行Decrease-Key操作，然后因为5不再比4大（这里注意，一般要比4小了才切，但是做图的这个网站中等于的情况也会切掉，按照一般理论标准的话等于的情况是不用切的），所以这里就把原本的5给Cut掉了，然后根据级联剪切的规则，我们要把被切掉的元素的parent进行mark，如图所示，涂成了黑色，代表mark：

在级联剪切的规则下，一颗度数为k的树，拥有最少的节点记为\(N_k\)。假设你是一个度数为 \(k\) 的节点。你有 \(k\) 个孩子，按时间顺序排列为 \(y_1, y_2, ..., y_k\)。根据斐波那契堆的合并规则，当第 \(i\) 个孩子 \(y_i\) 链接到你身上时，你已经有 \(i-1\) 个孩子了。所以 \(y_i\) 当时的度数肯定 \(\ge i-1\)。级联剪切规则规定： 孩子最多只能失去 1 个自己的孩子 （否则它就被剪跑了，不在你名下了）。所以，还在你名下的第 \(i\) 个孩子 \(y_i\)，现在的度数至少是 \((i-1) - 1 = \mathbf{i-2}\)。

我们要算总人数 \(N_k\)，就是把所有孩子的最少节点数加起来，再加上你自己（1个）。孩子的度数序列大概是这样的（最小情况）：

• \(y_1\) (原本度0 \(\to\) 现度0)：节点数 \(N_0\)
• \(y_2\) (原本度1 \(\to\) 现度0)：节点数 \(N_0\)
• \(y_3\) (原本度2 \(\to\) 现度1)：节点数 \(N_1\)
• \(y_4\) (原本度3 \(\to\) 现度2)：节点数 \(N_2\)
• ...
• \(y_k\) (原本度\(k-1\) \(\to\) 现度\(k-2\))：节点数 \(N_{k-2}\)

公式：

\[ N_k = 1 + N_0 + N_0 + N_1 + N_2 + ... + N_{k-2} \]

让我们从小到大算一下 \(N_k\) 的值，会发现如下规律：

\[ N_k = N_{k-1} + N_{k-2} \]

而这正是斐波那契数列的定义。因此，这种堆的构造方式才被命名为斐波那契堆。

最后我们来看一下时间复杂度：根据级联剪切规则，当父节点失去第一个孩子的时候就要mark，打mark的时候我们存硬币，并保持O(1)。当级联剪切发生时，我们会消耗掉之前mark时存的钱来抵消开销。因此，无论剪切链条有多长（最差情况是每剪掉一个就触发另一个被剪掉，导致logN的消耗），都通过mark时的存款付掉了，进而实现了Decrease-Key的O(1) Amortized时间复杂度。

---

Extract-Min

接下来我们来看一下Extract-Min。在执行EXTRACT-MIN时，我们实际上就是要从根链表和要删除的对象的孩子节点中，选出最小的那个，作为新的最小值：

然而，在之前的INSERT和UNION操作中，由于插入时直接创建了一个新的根节点，此时森林可能已经变得异常庞大，比如如下图所示：

这个时候EXTRACT-MIN后找下一个最小值会很慢，假如N个节点都没有孩子，那么找到下一个最小值的效率将退化到O(N)。为了提升效率，斐波那契堆会同时做两件事情：

• 合并整理，把没孩子的、孩子少的合并为新的树
• 选出新的最小值（或最大值）

我们对场上候选的N个节点进行合并整理，这个过程有点像连连看：只要两棵树的度数相同，他们就必须合并。核心公式：\(k + k \rightarrow k+1\)：

• 度数 0 + 度数 0 \(\rightarrow\) 合并成 度数 1 的树。
• 度数 1 + 度数 1 \(\rightarrow\) 合并成 度数 2 的树。
• 度数 2 + 度数 2 \(\rightarrow\) 合并成 度数 3 的树。
• ...以此类推。

为此，我们需要设置一个辅助Bucket数组A：

• A[0]：专门暂存度数 0 的树。
• A[1]：专门暂存度数 1 的树。
• A[2]：专门暂存度数 2 的树。
• ...

这里要注意，Bucket数组的大小通常设置为64就足够处理天文数字级的数据了。如果我们从来不执行Decrease-Key，那么斐波那契堆就会退化为二项堆（Binomial Heap），度数为 \(k\) 的树，节点数严格等于 \(2^k\)。如果你有 \(N\) 个节点，你的最大度数 \(D_{max} = \log_2 N\)。而如果进行了剪切，一棵度数为 \(k\) 的树，至少包含 \(F_{k+2} \approx \phi^k\) 个节点（其中 \(\phi = 1.618\) 是黄金分割率）。

推导：

\[ N \ge 1.618^{D_{max}} \]

两边取对数：

\[ D_{max} \le \log_{1.618} N \]

因此，无论是底数为 2（二项树）还是底数为 1.618（斐波那契树），只要节点数是指数级增长的，度数（高度）就必然是 \(O(\log N)\) 级别的。这就是为什么我们在合并之后，剩下的树的数量（也就是 Bucket 的最大下标）只有 \(\log N\) 这么少。

总而言之，Extract-Min操作不仅仅是找到下一个最小的值，还要顺便整理整个森林。合并整理操作的唯一停止标准是：当我们遍历完根链表中所有的节点（包括原来的根和新晋升的孩子），并且保证辅助数组 A（Bucket）中，每一个度数（格子）至多只有一棵树时，合并才算结束。

这个过程非常像是2048游戏，假设有32个度数为0的节点，那么整个合并过程将会如下进行：

• 先把0合并为1
• 再把0合并为1，这个时候有2个1，那么就把2个1合并为2
• 再把0合并为1，再把0合并为1，这个时候有2个1，合并为2，因为已经有2，一起合并为4
• ……以此类推

对于N个节点，最坏情况我们将花费O(N)。然而由于我们每次插入都只花了O(1)，所以合并的时间复杂度可以被摊销为0，所有的合并费用都被插入时的存款抵消了。如果你对摊销不熟悉，这里可以这么理解：就是因为INSERT操作，才导致0度的树一大堆，造成了合并的麻烦。所以EXTRACT-MIN的工作量取决于之前插入操作的多少。

综上所述，我们只需要关注合并完成后的查找下一个最小值。由于bucket的大小为logN，因此搜索的时间复杂度自然就是O(logN)。所以总的时间复杂度就是：0 + O(logN) = O(logN)。

生成示例

示例一： 使用Insert和Extract-Min操作，你能生成一个root list包含五个节点，并且degrees分别是4，3，2，1，0的斐波那契堆吗？

解：

只要先插入32个数字，然后执行一次extract-min，就可以得到题目中要求的内容。在合并整理的过程中，很像2048游戏：

在斐波那契堆（经过合并整理后）中，度数（Degree）和树的大小（Size）有严格的数学对应关系，即 \(2^k\)：

• 度数 4 的树，必然包含 \(2^4 = \mathbf{16}\) 个节点。
• 度数 3 的树，必然包含 \(2^3 = \mathbf{8}\) 个节点。
• 度数 2 的树，必然包含 \(2^2 = \mathbf{4}\) 个节点。
• 度数 1 的树，必然包含 \(2^1 = \mathbf{2}\) 个节点。
• 度数 0 的树，必然包含 \(2^0 = \mathbf{1}\) 个节点。

要把这些树同时留在堆里，你需要多少个节点？把上面的数字加起来：

\[ 16 + 8 + 4 + 2 + 1 = \mathbf{31} \]

这就意味着，在操作全部结束后，堆里必须恰好剩下 31 个节点。如果想要最终看到那种完美的合并形态， 最后一步操作必须是 Extract-Min 。因为如果最后一步是 Insert，新插入的节点会作为一个度数为 0 的散乱节点挂在旁边，破坏你想要得到的完美序列（比如变成 4, 3, 2, 1, 0, 0 ）。

换句话说，既然最后要剩 31 个节点，且最后一步必须是Extract-Min，那么在执行Extract-Min之前，必须先拥有32个节点。

---

示例二： 我们可以看到，生成的这个结果中，degree=4的tree root node，有4个孩子，这4个孩子分别的degree是0、1、2、3。请说明，为什么在执行了更多的Extract-Min操作后，该性质依然可以保持不变：一个度数为 \(k\) 的节点，它的子节点的度数应该是 \(0, 1, 2, \dots, k-1\)。也就是说，每种度数的孩子各有一个。

答：

斐波那契堆在Extract-Min操作后会进行合并，合并依据是将两个根节点度数相同的树进行合并，合并的目标是根链表中没有重复的度数。这个过程就像是游戏2048，当我们把2个0度的根的树合并时，可以得到1个1度的根的树；然后我们把2个1度的根的树合并时，会得到1个2度的根的树，这个树是由刚才的2个1度的树合并而来的，合并方式是一个1度的根连接到另一个根下面，所以这个2度的根的树是原本的1度的根的树下面接了一个1度的根的树，从而拥有了1个1度的根的树（也就是刚刚接上来的那棵树）加上自己本来的孩子，也就是0度的一个孩子。以此类推，每当我们合并两颗相同度数的根的树的时候，都是这样的一个合并过程：一个相同度数的树被连接到了根下面。所以当两个度数为K的根的树合并时，新的度数为K+1的树相当于增加了一个度数为K的子树，因此题目中所说的性质是正确的，并且无论进行多少次Extract-Min都可以保留。

---

问题三： 生成一个包含0、1、2、3、4、5度数的fibonacci heap，让每个树都尽可能满，说出每个树的size。然后假设这六棵树都承受了最大可能的Decrease-Key操作，并且这些操作不改变每棵树的根的度数，请说出如何得到这样的堆，以及这样的堆的每个树的size是多少。

和上面的回答一样，我们先插入64个node，然后执行一次Extract-Min，这样就可以得到满的符合要求的fibonacci heap。

每棵树的size如下：

• 0-degree root tree: 1
• 1-degree root tree: 2
• 2-degree root tree: 4
• 3-degree root tree: 8
• 4-degree root tree: 16
• 5-degree root tree: 32

接着，我们进行Decrease-Key操作。要想保持根的度数的同时，又尽可能多地进行Decrease-Key操作，我们的目标就是让每一个根的孩子都变成黑色marked状态。

我们省略掉那些因Decrease-Key操作而被Cut后连接到原本的根链表的节点。

可以看到，每一棵树的 Size如下：

• Degree 0: Size 1
• Degree 1: Size 2
• Degree 2: Size 3
• Degree 3: Size 5
• Degree 4: Size 8
• Degree 5: Size 13

这恰好是斐波那契数列。通过上例，我们可以直观地看到为什么说decrease-key操作后原本的树的size会是个斐波那契数列。

增强树

增强数据结构（Augmented Data Structure） 的核心思想是：在现有的数据结构（如 BST、Red-Black Tree）的每个节点上，额外存储一些辅助信息，从而在不改变原有操作渐进复杂度的前提下，支持更多高效的查询操作。

增强的一般方法论（对应 CLRS 第14章）可以总结为以下四步：

1. 选择基础数据结构（如红黑树）
2. 确定要维护的额外信息（如子树大小 size）
3. 验证额外信息可以在基本操作中被高效维护（插入、删除、旋转时能在 \(O(\log n)\) 内更新）
4. 利用额外信息开发新操作（如 OS-SELECT、OS-RANK）

Order-Statistic Tree

顺序统计树（Order-Statistic Tree） 是增强红黑树的经典例子。它在每个节点 \(x\) 上额外存储 \(x.size\)，表示以 \(x\) 为根的子树中节点的总数（包括 \(x\) 自身）。

           [26, size=7]
          /              \
    [17, size=3]      [41, size=3]
    /        \         /        \
[14, s=1] [21, s=1] [30, s=1] [47, s=1]

借助 size 属性，可以支持以下两个操作：

操作	功能	时间复杂度
OS-SELECT(x, i)	查找以 \(x\) 为根的子树中第 \(i\) 小的元素	\(O(\log n)\)
OS-RANK(T, x)	返回节点 \(x\) 在整棵树中的排名（中序遍历位置）	\(O(\log n)\)

OS-SELECT 的详细伪代码已在上文红黑树章节的 OS-SELECT 部分给出。OS-RANK 的思路则是从节点 \(x\) 出发，沿着路径向上走到根节点，逐步累加左侧的节点数量。

维护 size 属性的关键在于：在插入、删除时沿路径更新 \(O(\log n)\) 个节点的 size；在旋转时只需对旋转涉及的两个节点重新计算 size，代价为 \(O(1)\)。因此增强不会改变红黑树的渐进复杂度。

Interval Tree

区间树（Interval Tree） 是另一个增强红黑树的例子。每个节点存储一个区间 \([low, high]\)，并额外维护 \(max\)，即以该节点为根的子树中所有区间右端点的最大值。借助 \(max\) 属性，可以在 \(O(\log n)\) 时间内查找与给定区间重叠的区间。

B-Tree

B-Tree（B树） 是一种自平衡的多路搜索树，专为磁盘存储和数据库系统设计。与二叉树不同，B-Tree 的每个节点可以包含多个键（key）和多个子节点，从而大幅降低树的高度，减少磁盘 I/O 次数。

定义与性质

一棵最小度数（minimum degree） 为 \(t\)（\(t \ge 2\)）的 B-Tree 满足以下性质：

1. 所有叶子节点在同一层（完美平衡）
2. 每个节点最多包含 \(2t - 1\) 个键
3. 每个非根的内部节点至少包含 \(t - 1\) 个键
4. 根节点至少包含 1 个键（除非树为空）
5. 一个包含 \(k\) 个键的内部节点恰好有 \(k + 1\) 个子节点
6. 节点内的键按升序排列，且满足搜索树性质：子节点 \(c_i\) 中所有键 $< key_i < $ 子节点 \(c_{i+1}\) 中所有键

以 \(t = 2\) 的 B-Tree（也称 2-3-4 树）为例：

                    [16]
                   /    \
           [4, 8]        [20, 24]
          / |   \       /   |    \
       [1,2] [5,6] [9,10] [17,18] [21,22] [25,26]

为什么适合磁盘存储

磁盘读写的最小单位是一个磁盘页（page），通常为 4KB。B-Tree 将 \(t\) 设置为较大值（例如 \(t = 1000\)），使得每个节点恰好占满一个磁盘页。这样一来：

• 树的高度为 \(O(\log_t n)\)，远小于二叉树的 \(O(\log_2 n)\)
• 含有 \(n = 10^9\) 个键、\(t = 1000\) 时，树高仅为 3，即查找一个键最多只需 3 次磁盘 I/O

核心操作

Search（查找）： 从根节点开始，在当前节点的键数组中用线性搜索（或二分搜索）找到合适的位置，若命中则返回，否则递归进入对应的子节点。每层访问一个节点，因此磁盘 I/O 次数为 \(O(h)\)。

Insert（插入）： B-Tree 的插入是自顶向下进行的。如果沿途遇到满节点（包含 \(2t-1\) 个键），就先进行分裂（Split）：将满节点一分为二，中间键提升到父节点。这样保证插入时目标叶子节点一定有空间。

Delete（删除）： 删除操作较复杂，需要处理三种情况：从叶子删除、从内部节点删除（用前驱或后继替换）、以及节点键数不足时的合并（Merge）或借位（Borrow）操作。

复杂度

操作	时间复杂度	磁盘 I/O
查找	\(O(t \log_t n)\)	\(O(\log_t n)\)
插入	\(O(t \log_t n)\)	\(O(\log_t n)\)
删除	\(O(t \log_t n)\)	\(O(\log_t n)\)
空间	\(O(n)\)	-

其中 \(t\) 是每个节点内做线性搜索的代价（若使用二分搜索则为 \(\log t\)），\(\log_t n\) 是树的高度。在实际数据库系统中，\(t\) 是常数，因此操作的时间复杂度可以视为 \(O(\log n)\)。

B-Tree 的变体 B+ Tree 在数据库中更为常见：所有数据只存储在叶子节点，内部节点只存索引；叶子节点之间通过链表相连，方便范围查询。

Segment Tree

线段树（Segment Tree） 是一种用于处理区间查询（Range Query） 与单点更新（Point Update） 问题的树形数据结构。它可以在 \(O(\log n)\) 时间内完成区间求和、区间最值等查询，同时支持高效的元素修改。

基本思想

给定一个长度为 \(n\) 的数组，线段树是一棵完全二叉树（通常用数组存储），其中：

• 每个叶子节点存储原数组中的一个元素
• 每个内部节点存储其对应区间的聚合结果（如区间和、区间最小值等）

以数组 [2, 1, 5, 3, 4] 为例，构建区间和线段树：

                  [15]              -> 区间 [0,4] 的和
                /      \
            [8]          [7]        -> [0,2] 和 [3,4]
           /   \        /   \
        [3]    [5]    [3]    [4]    -> [0,1] [2,2] [3,3] [4,4]
       /   \
     [2]   [1]                      -> [0,0] [1,1]

Python 实现

class SegmentTree:
    def __init__(self, data):
        self.n = len(data)
        self.tree = [0] * (4 * self.n)  # 开4倍空间
        self._build(data, 1, 0, self.n - 1)

    def _build(self, data, node, start, end):
        """建树：O(n)"""
        if start == end:
            self.tree[node] = data[start]
            return
        mid = (start + end) // 2
        self._build(data, 2 * node, start, mid)
        self._build(data, 2 * node + 1, mid + 1, end)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def update(self, idx, val, node=1, start=0, end=None):
        """单点更新：将 data[idx] 修改为 val，O(log n)"""
        if end is None:
            end = self.n - 1
        if start == end:
            self.tree[node] = val
            return
        mid = (start + end) // 2
        if idx <= mid:
            self.update(idx, val, 2 * node, start, mid)
        else:
            self.update(idx, val, 2 * node + 1, mid + 1, end)
        self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1]

    def query(self, l, r, node=1, start=0, end=None):
        """区间查询：返回 [l, r] 的区间和，O(log n)"""
        if end is None:
            end = self.n - 1
        if r < start or end < l:
            return 0  # 完全不相交
        if l <= start and end <= r:
            return self.tree[node]  # 完全包含
        mid = (start + end) // 2
        left_sum = self.query(l, r, 2 * node, start, mid)
        right_sum = self.query(l, r, 2 * node + 1, mid + 1, end)
        return left_sum + right_sum


# 使用示例
data = [2, 1, 5, 3, 4]
seg = SegmentTree(data)
print(seg.query(1, 3))   # 输出 9 (1 + 5 + 3)
seg.update(2, 10)         # 将 data[2] 从 5 改为 10
print(seg.query(1, 3))   # 输出 14 (1 + 10 + 3)

复杂度

操作	时间复杂度
建树 Build	\(O(n)\)
单点更新 Update	\(O(\log n)\)
区间查询 Query	\(O(\log n)\)
空间	\(O(n)\)（数组开 \(4n\)）

Lazy Propagation

当需要进行区间更新（如将 \([l, r]\) 内所有元素加上一个值）时，朴素做法需要逐个更新 \(O(n)\) 个叶子节点。懒标记（Lazy Propagation） 通过延迟更新来解决这个问题：对于被完全覆盖的区间，只在该节点上打一个"待更新"标记，等到下次查询或更新需要深入该节点的子节点时，才将标记下推（pushdown）。这样区间更新的复杂度也降为 \(O(\log n)\)。

Van Emde Boas Tree

Van Emde Boas Tree（vEB 树） 是一种支持在整数域上进行高效操作的数据结构。当元素取值范围（universe）为 \(\{0, 1, \dots, u-1\}\) 时，vEB 树可以在 \(O(\log \log u)\) 时间内完成 predecessor、successor、insert、delete 等操作。

核心思想

vEB 树的关键在于递归分块。将 universe \(\{0, \dots, u-1\}\) 分成 \(\sqrt{u}\) 个大小为 \(\sqrt{u}\) 的块（cluster），并维护一个大小为 \(\sqrt{u}\) 的摘要结构（summary），记录哪些 cluster 是非空的。summary 本身也是一棵 vEB 树。

对于一个元素 \(x\)：

• 它属于第 \(\lfloor x / \sqrt{u} \rfloor\) 个 cluster（称为 high(x)）
• 它在 cluster 内的位置为 \(x \mod \sqrt{u}\)（称为 low(x)）

递归的深度为 \(\log \log u\)：\(u \to \sqrt{u} \to u^{1/4} \to u^{1/8} \to \cdots \to 2\)，每一层只做 \(O(1)\) 的工作，因此总时间为 \(O(\log \log u)\)。

操作与复杂度

操作	时间复杂度
Insert	\(O(\log \log u)\)
Delete	\(O(\log \log u)\)
Successor / Predecessor	\(O(\log \log u)\)
Find-Min / Find-Max	\(O(1)\)
空间	\(O(u)\)

适用场景

vEB 树的优势在于当 \(u\) 不太大且需要频繁执行 predecessor/successor 查询时，\(O(\log \log u)\) 显著优于平衡 BST 的 \(O(\log n)\)。但其空间消耗为 \(O(u)\)，当 universe 很大时不实用。实践中可以用哈希表替代数组存储 cluster（即 x-fast trie 或 y-fast trie）来缓解空间问题。

与其他结构的对比：

• 平衡 BST（如红黑树）：\(O(\log n)\)，适用于一般场景，空间 \(O(n)\)
• vEB 树：\(O(\log \log u)\)，适用于整数域且 \(u\) 可控的场景，空间 \(O(u)\)
• 哈希表：\(O(1)\) 查找，但不支持 predecessor/successor

Fenwick Tree

Fenwick Tree，也称为树状数组（Binary Indexed Tree, BIT），是一种利用位运算（bit manipulation） 来高效处理前缀和查询（prefix sum query） 和单点更新（point update） 的数据结构。它的功能与线段树有重叠，但实现更简洁、常数更小。

核心思想：lowbit

Fenwick Tree 的精髓在于 lowbit 操作，即取一个正整数二进制表示中最低位的 1：

\[ \text{lowbit}(x) = x \ \& \ (-x) \]

例如：\(\text{lowbit}(6) = \text{lowbit}(110_2) = 010_2 = 2\)。

Fenwick Tree 用一个数组 tree[1..n] 来存储信息，其中 tree[i] 存储的是原数组中从 \(i - \text{lowbit}(i) + 1\) 到 \(i\) 这一段的和。每个位置管辖的区间长度恰好是 lowbit(i)。

索引 i (二进制)   lowbit(i)   管辖区间
  1   (0001)         1        [1, 1]
  2   (0010)         2        [1, 2]
  3   (0011)         1        [3, 3]
  4   (0100)         4        [1, 4]
  5   (0101)         1        [5, 5]
  6   (0110)         2        [5, 6]
  7   (0111)         1        [7, 7]
  8   (1000)         8        [1, 8]

• 前缀和查询 query(i)： 从位置 \(i\) 开始，不断减去 \(\text{lowbit}(i)\)，沿途累加 tree[i]，直到 \(i = 0\)。每次跳跃都消去最低位的 1，因此最多跳 \(O(\log n)\) 次。
• 单点更新 update(i, delta)： 从位置 \(i\) 开始，不断加上 \(\text{lowbit}(i)\)，沿途更新 tree[i]，直到 \(i > n\)。同理最多跳 \(O(\log n)\) 次。

Python 实现

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)  # 下标从1开始

    def update(self, i, delta):
        """单点更新：将位置 i 的值加上 delta，O(log n)"""
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)  # i += lowbit(i)

    def query(self, i):
        """前缀和查询：返回 [1, i] 的前缀和，O(log n)"""
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)  # i -= lowbit(i)
        return s

    def range_query(self, l, r):
        """区间查询：返回 [l, r] 的区间和"""
        return self.query(r) - self.query(l - 1)

    @classmethod
    def from_array(cls, arr):
        """从数组建树，O(n)"""
        n = len(arr)
        bit = cls(n)
        bit.tree[1:] = arr[:]
        for i in range(1, n + 1):
            j = i + (i & (-i))
            if j <= n:
                bit.tree[j] += bit.tree[i]
        return bit


# 使用示例
data = [2, 1, 5, 3, 4]
bit = FenwickTree.from_array(data)
print(bit.range_query(2, 4))  # 输出 9 (1 + 5 + 3)
bit.update(3, 5)               # 将位置3的值加5（5 -> 10）
print(bit.range_query(2, 4))  # 输出 14 (1 + 10 + 3)

复杂度

操作	时间复杂度
建树 Build	\(O(n)\)
单点更新 Update	\(O(\log n)\)
前缀和查询 Query	\(O(\log n)\)
区间查询 Range Query	\(O(\log n)\)
空间	\(O(n)\)

Fenwick Tree vs Segment Tree

对比维度	Fenwick Tree	Segment Tree
实现复杂度	非常简洁（约20行）	较复杂（需递归或迭代建树）
常数大小	小，实际运行更快	较大
空间	\(O(n)\)	\(O(4n)\)
支持的操作	前缀和查询 + 单点更新	任意区间查询 + 区间更新（配合 Lazy Propagation）
区间更新	需要差分数组技巧，扩展性有限	原生支持（Lazy Propagation）
适用场景	前缀和、逆序对计数、离散化后的频率统计	区间最值、区间修改等更复杂的区间操作

简单来说：如果只需要前缀和 + 单点更新，优先选择 Fenwick Tree，代码短且跑得快；如果需要区间更新或非加法的区间查询（如区间最值），则使用 Segment Tree。

附录：经典练习

二叉树基础

树的直径

最大深度

最小深度

平衡二叉树

翻转二叉树

合并二叉树

从遍历序列构造二叉树

LCA 最近公共祖先

---

评论