第五部分 高级数据结构

​ B 树，这是为磁盘存储而专门设计的一类平衡搜索树。由于磁盘操作比随机存取存储器要慢得多，因此度量B 树的性能，不仅要考虑动态集合操作消耗了多少计算时间，而且还要考虑这些操作执行了多少次磁盘存取。对每个B 树操作，磁盘存取的次数随着B 树的高度增加。

​ 可合并堆的实现，它支持INSERT 、MINIMUM 、EXTRACT-MIN 和UNION 操作。

​ van Emde Boas 树的递归数据结构，当关键字是郁良范围内的整数时，排序算法可以超越O(nlgn) 时间的下界。使其支持动态集上的SEARCH 、INSERT 、DELETE 、MINIMUM 、MAXIMUN 、SUCCESSOR 和PREDECESSOR操作仅花费O(lgn) 时间。答

​ 用于不相交集合的一些数据结构。由n 个元素构成的全域被划分成若干动态集合。开始时，每个元素属千由其自身所构成的单元集合。操作UNION 将两个集合进行合并，而查询操作FIND-SET 则可以确定给定的元素当前所属的那个集合。

​ 其他高级数据结构：动态树、伸展树、持久数据结构、动态图数据结构。

第18章 B树

​ B 树是为磁盘或其他直接存取的辅助存储设备而设计的一种平衡搜索树。B 树类似于红黑树，但它们在降低磁盘I/0 操作数方面要更好一些。许多数据库系统使用B 树或者B 树的变种来存储信息。

​ 树与红黑树的不同之处在于B 树的结点可以有很多孩子，从数个到数千个。也就是说，一个B 树的“分支因子”可以相当大，尽管它通常依赖千所使用的磁盘单元的特性。B 树类似千红黑树，就是每棵含有n 个结点的B 树的高度为 $O(lgn)$。然而，一棵B 树的严格高度可能比一棵红黑树的高度要小许多，这是因为它的分支因子，也就是表示高度的对数的底数可以非常大。因此，我们也可以使用B 树在时间 $O(lgn)$ 内完成一些动态集合的操作。

18.1 B树的定义

一棵B 树T 是具有以下性质的有根树（根为T. root):

1. 每个结点x 有下面属性：
   a. x.n, 当前存储在结点x 中的关键字个数。
   b. x.n 个关键字本身 $x.key_1, x.key_2, \cdots, x.key_{x.n}$, 以非降序存放，使得 $x.key_1 \le \cdots \le x.key_{x.n}$
   c. x. leaf, 一个布尔值，如果x 是叶结点，则为TRUE; 如果x 为内部结点，则为FALSE 。
2. 每个内部结点x 还包含 x.n+1 个指向其孩子的指针 $x.c_1,x.c_2,\cdots,x.c_{x.n+1}$ 。叶结点没有孩子，所以它们的$c_i$ 属性没有定义。
3. 关键字 $x.key_i$ 对存储在各子树中的关键字范围加以分割：如果 $k_i$ 为任意一个存储在以 $x.c_i$ 为根的子树中的关键字，那么 $k_1\le x.key_1 \le k_2 \le x.key_2 \le \cdots \le x.key_{x.n} \le k_{x.n+1}$
4. 每个叶结点具有相同的深度，即树的高度h 。
5. 每个结点所包含的关键字个数有上界和下界。用一个被称为B 树的最小度数(minmum degree) 的固定整数$t \ge 2$ 来表示这些界：
   a. 除了根结点以外的每个结点必须至少有 t-1 个关键字。因此，除了根结点以外的每个内部结点至少有t 个孩子。如果树非空，根结点至少有一个关键字。
   b. 每个结点至多可包含 2t-1 个关键字。因此，一个内部结点至多可有2t 个孩子。当一个结点恰好有 2t-1 个关键字时，称该结点是满的(full) 。

​ t = 2 时的B 树是最简单的。每个内部结点有2 个、3 个或4 个孩子，即一棵2-3-4 树。然而在实际中， t 的值越大， B 树的高度就越小。

B 树的高度

如果 $ n \ge 1$ , 那么对任意一棵包含n 个关键宇、高度为h 、最小度数 $t \ge 2$ 的B 树T, 有 $h \le log_t\frac{n+1}{2}$

18.2 B树上的基本操作

​ 搜索一棵B 树和搜索一棵二叉搜索树很相似，只是在每个结点所做的不是二叉或者”两路”分支选择，而是根据结点的孩子数做多路分支选择。更严格地说，对每个内部结点x, 做的是一个(x.n+1) 路的分支选择。

​ B-TREE-SEARCH 是定义在二叉搜索树上的TREE-SEARCH 过程的一个直接推广。它的输入是一个指向某子树根结点x 的指针，以及要在该子树中搜索的一个关键字k 。因此，顶层调用的形式为B-TREE-SEARCH(T. root, k) 。如果k 在B 树中，那么B-TREE-SEARCH 返回的是由结点y 和使得 $y.key_i=k$ 的下标i 组成的有序对(y, i); 否则，过程返回NIL 。

B-TREE-SEARCH(x, k)
  i = 1
  while i <= x.n and k > x. key[i]
    i=i+l
  if i <= x.n and k == x.key[i]
    return (x, i)
  else if x.leaf
    return NIL
  else
    DISK-READ(x, c[i])
    return B-TREE-SEARCH(x.c[i], k)

算法分析

​ 就像二叉搜索树的TREE-SEARCH 过程一样，在递归过程中所遇到的结点构成了一条从树根向下的简单路径。因此，由B-TREE-SEARCH 过程访问的磁盘页面数为 $O(h) = O(log_tn)$ ,其中h 为B 树的高， n 为B 树中所含关键字个数。由于 $x.n\lt2t$, 所以第2~3 行的while 循环在每个结点中花费的时间为 $O(t)$ , 总的CPU 时间为$O(th) = O(tlog_tn)$ 。

创建一棵空的B 树

​ 为构造一棵B 树T, 先用B-TREE-CREATE 来创建一个空的根结点，然后调用B-TREEINSERT来添加新的关键字。

B-TREE-CREATE(T)
 // 分配磁盘页
 x = ALLOCATE-NODE()
 x.leaf = TRUE
 x.n = 0
 DISK-WRITE(x)
 T.root = x

向B 树中插入一个关键字

​ B 树中插入像二叉搜索树中一样，要查找插入新关键字的叶结点的位置。然而，在B 树中，不能简单地创建一个新的叶结点，然后将其插入，因为这样得到的树将不再是合法的B 树。相反，我们是将新的关键字插入一个已经存在的叶结点上。由于不能将关键字插入一个满的叶结点，故引入一个操作，将一个满的结点y(有 $2t-1$ 个关键字）按其中间关键字(median key)$y.key$, 分裂(split) 为两个各含 $t-1$ 个关键字的结点。中间关键字被提升到 y 的父结点，以标识两棵新树的划分点。但是如果y 的父结点也是满的，就必须在插入新的关键字之前将其分裂，最终满结点的分裂会沿着树向上传播。

​ 与一棵二叉搜索树一样，可以在从树根到叶子这个单程向下过程中将一个新的关键字插入B树中。为了做到这一点，我们并不是等到找出插入过程中实际要分裂的满结点时才做分裂。相反，当沿着树往下查找新的关键字所属位置时，就分裂沿途遇到的每个满结点（包括叶结点本身）。因此，每当要分裂一个满结点y 时，就能确保它的父结点不是满的。

分裂B 树中的结点

​ 过程B-TREE-SPLIT-CHILD 的输入是一个非满的内部结点x( 假定在主存中）和一个使 $x.c_i$（也假定在主存中）为x 的满子结点的下标i 。该过程把这个子结点分裂成两个，并调整x, 使之包含多出来的孩子。要分裂一个满的根，首先要让根成为一个新的空根结点的孩子，这样才能使用B-TREE-SPLIT-CHILD。树的高度因此增加1; 分裂是树长高的唯一途径。

B-TREE-SPLIT-CHILD(x, i)
  z = ALLOCATE-NODE()
  y = x.c[i]
  z.leaf = y.leaf
  z.n = t - 1
  for j = 1 to t - 1
    z.key[j] = y.key[j+t]
  if not y.leaf
    for j = 1 to t
      Z.c[j] = y.c[j+t]
  y.n = t - 1
  for j = x.n + 1 downto i + 1
    X.c[j+1]= X.c[j]
  x.c[i+1] = z
  for j = x.n downto i
    x.key[j+1] = x.key[j];
  x.key[i] = x.key[t];
  x.n = x.n + 1
  DISK-WRITE(y)
  DISK-WRITE(z)
  DISK-WRITE(x)

以沿树单程下行方式向B 树插入关键字

​ 在一棵高度为h 的B 树T 中，以沿树单程下行方式插入一个关键字 k 的操作需要O(h) 次磁盘存取。所需要的CPU 时间为 $O(th) =O(t\:log_tn)$ 。过程B-TREE-INSERT 利用 B-TREE-SPLITCHILD来保证递归始终不会降至一个满结点上。

​ 过程通过调用B-TREE-INSERT-NONFULL 完成将关键字k 插入以非满的根结点为根的树中。B-TREE-INSERT-NONFULL 在需要时沿树向下递归，在必要时通过调用B-TREE-SPLIT-CHILD 来保证任何时刻它所递归处理的结点都是非满的。

B-TREE-INSERT-NONFULL(x, k)
  i = x.n
  if x.leaf
    while i >= 1 and k < x.key[i]
      x.key[i+1] = x.key[i]
      i = i-1
    x.key[i+1] = k
    x.n = x.n + 1
    DISK-WRITE(x)
  else
    while i >= 1 and k < x. key[i]
      i = i - 1
    i = i + 1
    DISK-READ(x.c[i])
    if x.c[i].n == 2t - 1
      B-TREE-SPLIT-CHILD(x, i)
      if k > x. key[i]
        i = i + 1
    B-TREE-INSERT-NONFULL(x. c[i], k)

B-TREE-INSERT(T, k)
  r = T.root
  if r.n == 2t - 1
    s = ALLOCATE-NODE()
    T.root = s
    s.leaf= FALSE
    s.n = 0
    s.c[1] = r
    B-TREE-SPLIT-CHILD(s, 1)
    B-TREE-INSERT-NONFULL(s, k)
  else
    B-TREE-INSERT-NONFULL(r, k)

向B 树中插入关键字

18.3 从B树中删除关键字

​ 过程B-TREE-DELETE 从以x 为根的子树中删除关键字k 。我们设计的这个过程必须保证无论何时，结点x 递归调用自身时， x 中关键字个数至少为最小度数t 。注意到，这个条件要求比通常B 树中的最少关键字个数多一个以上，使得有时在递归下降至子结点之前，需要把一个关键字移到子结点中。这个加强的条件允许在一趟下降过程中，就可以将一个关键字从树中删除，无需任何“向上回溯”（有一个例外，后面会解释）。对下面的B 树上删除操作的规定应当这样理解，如果根结点x 成为一个不含任何关键字的内部结点，那么x 就要被删除， x 的唯一孩子 $x.c_1$ 成为树的新根，从而树的高度降低1, 同压囡时也维持树根必须包含至少一个关键字的性质（除非树是空的）。

删除操作工作流程：

1. 如果关键字k 在结点x 中，并且x 是叶结点，则从x 中删除k 。

2. 如果关键字k 在结点x 中，并且x 是内部结点，则做以下操作：

a. 如果结点x 中前于K 的子结点y 至少包含t 个关键字，则找出k 在以y 为根的子树中的前驱 k’ 。递归地删除k’ 并在x 中用k’ 代替k 。（找到k’并删除它可在沿树下降的单过程中完成。）
b. 对称地，如果y 有少于 t 个关键字，则检查结点x 中后于k 的子结点z 。如果z 至少有t个关键字，则找出k 在以z 为根的子树中的后继k’ 。递归地删除k’ 并在x 中用k’代替k 。（找到k’ 并删除它可在沿树下降的单过程中完成。）
c. 否则，如果y 和z 都只含有 t-1 个关键字，则将K 和z 的全部合并进y, 这样x 就失去了k 和指向z 的指针，并且y 现在包含2t-1 个关键字。然后释放z 并递归地从y 中删除k 。

3. 如果关键字k 当前不在内部结点x 中，则确定必包含k 的子树的根 $x.c_i$ (如果K 确实在树中）。如果 $x.c_i$ 只有t-1 个关键字，必须执行步骤3a 或3b 来保证降至一个至少包含t 个关键字的结点。然后，通过对x 的某个合适的子结点进行递归而结束。

a. 如果 $x.c_i$ 只含有t — 1 个关键字，但是它的一个相邻的兄弟至少包含t 个关键字，则将x中的某一个关键字降至 $x.c_i$ 中，将 $x.c_i$ 的相邻左兄弟或右兄弟的一个关键字升至x, 将该兄弟中相应的孩子指针移到 $x.c_i$ 中，这样就使得 $x.c_i$ 增加了一个额外的关键字。
b. 如果 $x.c_i$ 以及 $x.c_i$ 的所有相邻兄弟都只包含 t-1 个关键字，则将 $x.c_i$ 与一个兄弟合并，即将x 的一个关键字移至新合并的结点，使之成为该结点的中间关键字。

​ 尽管这个过程看起来很复杂，但对一棵高度为h 的B 树，它只需要O(h) 次磁盘操作，因为在递归调用该过程之间，仅需 $O(1)$ 次对 DISK-READ 和 DISK-WRITE 的调用。所需CPU 时间为 $O(th) =O(t\:log_tn)$ 。

从一棵B树中删除关键字

B树中结点的合并

​ B树的结点的合并基于如下情况调用：内结点x的第i个子结点y和第i+1个子结点z的关键字数都是t-1，此时需要把内结点x的第i个关键字下移与y和z的合并，形成一个结点y。

B-TREE-MERGE-CHILD(x, i, y, z)
 y.n = 2t -1
 for j = t + 1 to 2t - 1
   y.key[j] = z.key[j-t]
 y.key[t] = x.key[i]
 if not y.leaf
   for j = t + 1 to 2t - 1
     y.c[j] = z.c[j-t]
 for j = i + 1 to x.n
   x.c[j] = x.c[j+1]
 x.n = x.n - 1
 FREE-NODE(z)
 DISK-WRITE(y)
 DISK-WRITE(z)
 DISK-WRITE(x)

转移到左边或右边的子结点

// y向z借节点，将x.k[i]下降至y，将z的最小关键字上升至x的i处
B-TREE-SHIFT-TO-LEFT-CHILD(x,i,y,z)
 y.n = y.n + 1
 y.key[y.n] = x.key[i]
 x.key[i] = z.key[1]
 z.n = z.n - 1
 j = 1
 while j <= z.n
   z.key[j] = z.key[j+1]
   j = j + 1
 if not z.leaf
   y.c[y.n+1] = z.c[1]
   j = 1
   while j <= n[z]+1
     z.c[j] = z.c[j+1]
     j = j + 1
 DISK-WRITE(y)
 DISK-WRITE(z)
 DISK-WRITE(x)

// z向y借节点，将x.k[i]下降至z，将y的最大关键字上升至x的i处
B-TREE-SHIFT-TO-RIGHT-CHILD(x,i,y,z)
  z.n = z.n - 1
  j = z.n
  while j > 1
    z.key[j] = z.key[j-1]
    j = j -1
  z.key[1] = x.key[i]
  x.key[i] = y.key[y.n]
  if not z.leaf
    j = z.n
    while j > 0
      z.c[j + 1] = z.c[j]
      j = j - 1
    z.c[1] = y.c[y.n+1]
  y.n = y.n - 1
  DISK-WRITE(y)
  DISK-WRITE(z)
  DISK-WRITE(x)

查找前驱或后继

B-TREE-SEARCH-PREDECESSOR(y)
  x = y
  i = x.n
  while not x.leaf
    DISK_READ(x.c[i+1])
    x = x.c[i+1]
    i = x.n
  return x.key[i]

B-TREE-SEARCH-SUCCESSOR(z)
  x = z
  while not x.leaf
    DISK_READ(x.c[1])
    x = x.c[1]
  return x.key[1]

删除子过程B-TREE-DELETE-NONONE (x, k)。

B-TREE-DELETE-NONONE (x, k)
  i = 1
  while i <= x.n and k > x.key[i]
    i = i + 1
  if x.leaf                                      // Cases 1
    if k = x.key[i]
      for j = i + 1 to x.n
        x.key[j-1] = x.key[j]
      x.n = x.n - 1
      DISK-WRITE(x)
    else
      print "error: the key does not exist"
  else
    DISK-READ(x.c[i])
    y = x.c[i]
    if i <= x.n
      DISK-READ(x.c[i+1])
      z = x.c[i+1]
    if k == x.key[i]                             // Cases 2
      if y.n > t-1                               // Cases 2a
        k′ = B-TREE-SEARCH-PREDECESSOR(y)
        B-TREE-DELETE-NONONE(y, k′)
        x.key[i] = k′
      else if z.n > t - 1                        // Cases 2b
        k′ = B-TREE-SEARCH-SUCCESSOR(z)
        B-TREE-DELETE-NONONE (z, k′)
        x.key[i] = k′
      else
        B-TREE-MERGE-CHILD(x, i, y, z)           // Cases 2c
        B-TREE-DELETE-NONONE (y, k)
    else                                         // Cases 3
      if i > 1
        DISK-READ(x.c[i-1])
        p = x.c[i-1]
      if y.n == t-1
        if i > 1 and p.n > t - 1                 // Cases 3a
          B-TREE-SHIFT-TO-RIGHT-CHILD(x,i-1,p,y)
        else if i <= x.n and z.n > t-1           // Cases 3a
          B-TREE-SHIFT-TO-LEFT-CHILD(x,i,y,z)
        else if i > 1                            // Cases 3b
          B-TREE-MERGE-CHILD(x,i-1,p,y)
          y = p
        else
          B-TREE-MERGE-CHILD(x,i,y,z)           // Cases 3b
      B-TREE-DELETE-NONONE (y, k)

B树的删除

B-TREE-DELETE(T,k)
  r = T.root
  if r.n == 1
    DISK_READ(r.c[1])
    DISK_READ(r.c[2])
    y = r.c[1]
    z = r.c[2]
    if y.n == z.n == t-1              ▹ Cases 2c or 3b
      B-TREE-MERGE-CHILD(r, 1, y, z) 
      T.root = y
      FREE-NODE(r)
      r = y
  B-TREE-DELETE-NONONE(r, k)

{collapse}
{collapse-item label=“B树的 Java实现” }

public class BTree {
    static class BNode {
        public boolean leaf;
        public LinkedList<Integer> key;
        public LinkedList<BNode> child;

        public BNode() {
            this(false);
        }

        public BNode(boolean leaf) {
            this.leaf = leaf;
            this.key = new LinkedList<>();
            this.child = new LinkedList<>();
        }

        @Override
        public String toString() {
            return "BNode [key=" + key + ", leaf=" + leaf + "]";
        }
    }

    public int n;
    private BNode root;

    public BTree() {
        this.n = 3;
        this.root = new BNode(true);
    }

    private BNode search(BNode node, int k) {
        int size = node.key.size();
        // 寻找位置
        int i = 0;
        while (i < size && k > node.key.get(i)) {
            i++;
        }
        if (i < size && node.key.get(i) == k)
            return node;
        if (node.leaf)
            return null;
        return search(node.child.get(i), k);
    }

    public BNode search(int k) {
        return search(root, k);
    }

    private void splitChild(BNode parent, int i) {
        BNode left = parent.child.get(i);
        BNode right = new BNode(left.leaf);

        int mid = n / 2;
        Integer cPk = left.key.get(mid);

        // 复制后半部分 key
        for (int j = mid + 1; j < n; j++) {
            right.key.addFirst(left.key.pollLast());
        }
        // 删除放入父节点的元素
        left.key.pollLast();

        // 不是叶节点，复制后半部分 child
        if (!right.leaf) {
            for (int j = mid + 1; j <= n; j++) {
                right.child.addFirst(left.child.pollLast());
            }
        }
        // 放入非满父节点
        parent.key.add(i, cPk);
        parent.child.add(i + 1, right);
    }

    private void insertNonfull(BNode node, int k) {
        int i = node.key.size() - 1;
        // 寻找位置
        while (i >= 0 && k < node.key.get(i)) {
            i--;
        }
        i++;

        if (node.leaf) {
            // 叶节点插入数据
            node.key.add(i, k);
        } else {
            if (node.child.get(i).key.size() == n) {
                // 子元素分裂
                splitChild(node, i);
                if (k > node.key.get(i)) {
                    i++;
                }
            }
            insertNonfull(node.child.get(i), k);
        }
    }

    public void insert(int key) {
        BNode r = this.root;
        if (r.key.size() == this.n) {
            BNode nextRoot = new BNode();
            this.root = nextRoot;
            nextRoot.child.add(r);
            splitChild(nextRoot, 0);
            r = nextRoot;
        }
        insertNonfull(r, key);
    }

    private int searchPredecessor(BNode left) {
        // 左孩子最大值
        BNode t = left;
        int i = left.key.size();
        while (!t.leaf) {
            t = t.child.get(i);
            i = t.key.size();
        }
        return t.key.get(i - 1);
    }

    private int searchSuccessor(BNode right) {
        // 右孩子的最小值
        BNode t = right;
        while (!t.leaf) {
            t = t.child.get(0);
        }
        return t.key.get(0);
    }

    private void mergeChild(BNode parent, int i, BNode left, BNode right) {
        // 加入父节点Key
        left.key.add(parent.key.get(i));
        // 删除
        parent.key.remove(i);
        parent.child.remove(i + 1);
        // 加入右节点
        left.key.addAll(right.key);
        if (!left.leaf) {
            left.child.addAll(right.child);
        }
    }

    // left向 right借节点，将 parent.key[i]下降至 left
    private void shiftLeftChild(BNode parent, int i, BNode left, BNode right) {
        left.key.add(parent.key.get(i));
        parent.key.set(i, right.key.pollFirst());
        if (!left.leaf) {
            left.child.add(right.child.pollFirst());
        }
    }

    // right向 left 借节点，将 parent.key[i]下降至 right
    private void shiftRightChild(BNode parent, int i, BNode left, BNode right) {
        right.key.add(0, parent.key.get(i));
        parent.key.set(i, left.key.pollLast());
        if (!right.leaf) {
            right.child.add(0, left.child.pollLast());
        }
    }

    private void deleteNonone(BNode node, int k) {
        int i = 0;
        int size = node.key.size();
        while (i < size && k > node.key.get(i)) {
            i++;
        }
        if (node.leaf) {
            if (i < size && k == node.key.get(i)) {
                node.key.remove(i);
            } else {
                System.out.println("Key dose not exist !");
            }
        } else {
            BNode left = node.child.get(i), right = null;
            if(i < node.key.size()){
                right = node.child.get(i + 1);
            }
            if (i < node.key.size() && k == node.key.get(i)) { // Cases 2
                // 在节点中
                if (left.key.size() > n / 2) { // Cases 2a
                    Integer pre = searchPredecessor(left);
                    deleteNonone(left, pre);
                    node.key.set(i, pre);
                } else if (right.key.size() > n / 2) { // Cases 2b
                    Integer suc = searchSuccessor(right);
                    deleteNonone(right, suc);
                    node.key.set(i, suc);
                } else {
                    mergeChild(node, i, left, right); // Cases 2c
                    deleteNonone(left, k);
                }
            } else { // Cases 3
                BNode preLeft = null;
                if (i > 0) {
                    preLeft = node.child.get(i - 1);
                }
                if (left.key.size() == n / 2) {
                    if (i > 0 && preLeft.key.size() > n / 2) { // Cases 3a
                        shiftRightChild(node, i - 1, preLeft, left);
                    } else if (i < size && right.key.size() > n / 2) { // Cases 3a
                        shiftLeftChild(node, i, left, right);
                    } else if (i > 0) { // Cases 3b
                        mergeChild(node, i - 1, preLeft, left);
                        left = preLeft;
                    } else { // Cases 3b
                        mergeChild(node, i, left, right);
                    }
                }
                deleteNonone(left, k);
            }
        }
    }

    public void delete(int key) {
        BNode r = this.root;
        if (r.key.size() == 1) {
            BNode left = r.child.get(0);
            BNode right = r.child.get(1);
            if (left.key.size() == right.key.size()
                    && left.key.size() == n / 2) {
                mergeChild(r, 0, left, right);
                this.root = left;
                r = left;
            }
        }
        deleteNonone(r, key);
    }

    public void printLayer() {
        Queue<BNode> queue = new LinkedList<>();
        queue.offer(this.root);
        boolean isDo = true;
        while (isDo) {
            isDo = false;
            int size = queue.size();
            for (int j = 0; j < size; j++) {
                BNode node = queue.poll();
                if (node == null) {
                    System.out.print("null,");
                } else {
                    System.out.print(node.key.toString() + ",");
                    queue.addAll(node.child);
                    if (!node.child.isEmpty()) {
                        isDo = true;
                    }
                }
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        BTree bTree = new BTree();

        int[] no = new int[] { 12, 45, 9, 78, 60, 55, 58, 56, 57 };
        for (int i : no) {
            bTree.insert(i);
        }
        bTree.printLayer();
        bTree.delete(45);
        bTree.printLayer();
    }
}

第十九章 斐波那契堆*

​ 斐波那契堆数据结构有两种用途。第一种，它支持一系列操作，这些操作构成了所谓的”可合并堆＂。第二种，斐波那契堆的一些操作可以在常数摊还时间内完成，这使得这种数据结构非常适合于需要频繁调用这些操作的应用。

可合井堆

可合井堆(mergeable heap)是支持以下5 种操作的一种数据结构，其中每个元素都有一个关键字：

• MAKE-HEAP(): 创建和返回一个新的不含任何元素的堆。
• INSERT( $H, x$ ): 将一个已填入关键字的元素x 插入堆H 中。
• MINIMUM( $H$ ) : 返回一个指向堆H 中具有最小关键字元素的指针。
• EXTRACT-MIN( $H$ ): 从堆H 中删除最小关键字的元素，并返回一个指向该元素的指针。
• UNION( $H_1, H_2$ ）：创建并返回一个包含堆凡和堆几中所有元素的新堆。堆凡和堆H2由这一操作“销毁"。

斐波那契堆还支持以下两种操作：

• DECREASE-KEY( $H, x, k$ ): 将堆H 中元素x 的关键字赋予新值k 。假定新值k 不大千当前的关键字。
• DELETE( $H, x$ ): 从堆H 中删除元素x 。

19.1 斐波那契堆结构

​ 一个斐波那契堆是一系列具有最小堆序(min-heap ordered) 的有根树的集合。也就是说，每棵树均遵循最小堆性质(min-heap property): 每个结点的关键字大千或等于它的父结点的关键字。

​

​ 如图19-2(b) 所示，每个结点x 包含一个指向它父结点的指针 x.p 和一个指向它的某一个孩子的指针 x.child 。x 的所有孩子被链接成一个环形的双向链表，称为x 的孩子链表(child list) 。孩子链表中的每个孩子y 均有指针 y.left 和 y.right, 分别指向y 的左兄弟和右兄弟。如果y 是仅有的一个孩子，则 y.left = y.right = y 。孩子链表中各兄弟出现的次序是任意的。

​ 每个结点有另外两个属性。把结点x 的孩子链表中的孩子数目储存在 x.degree。布尔值属性 x.mark 指示结点x 自从上一次成为另一个结点的孩子后，是否失去过孩子。新产生的结点是未被标记的，并且当结点x 成为另一个结点的孩子时，它便成为未被标记结点。

​ 在斐波那契堆中，所有树的根都用其 left 和 right 指针链成一个环形的双链表，该双链表称为斐波那契堆的根链表(root list) 。因此，指针 H.min 指向根链表中关键字最小的那个结点。根链表中的树次序可以任意。

环形双向链表应用在斐波那契堆中有两个优点:

• 可以在O(1) 时间内从一个环形双向链表的任何位置插入一个结点或删除一个结点
• 给定两个这种链表，可以用O(1) 时间把它们链接成一个环形双向链表

第二十一章 用千不相交集合的数据结构

21.1 不相交集合的操作

​ 一个不相交集合数据结构(disjoint-set data structure) 维护了一个不相交动态集的集合 $S={S_i, S_2 …， S_k}$ 。我们用一个代表(representative) 来标识每个集合，它是这个集合的某个成员。在一些应用中，我们不关心哪个成员被用来作为代表，仅仅关心的是 2 次查询动态集合的代表中，如果这些查询没有修改动态集合，则这两次查询应该得到相同的答案。其他一些应用可能会需要一个预先说明的规则来选择代表，比如选择这个集合中最小的成员（当然假设集合中的元素能被比较次序）。
​ 如同我们已经探讨过的动态集合的其他实现，用一个对象表示一个集合的每个元素。设x表示一个对象，我们希望支持以下三个操作：

• MAKE-SET(x) : 建立一个新的集合，它的唯一成员（因而为代表）是x。因为各个集合是不相交的，故x 不会出现在别的某个集合中。
• UNION(x, y): 将包含x 和y 的两个动态集合（表示为$S_x$ 和 $S_y$) 合并成一个新的集合，即这两个集合的并集。假定在操作之前这两个集合是不相交的。虽然UNION 的很多实现中特别地选择 $S_x$ 和 $S_y$ 的代表作为新的代表，然而结果集的代表可以是 $S_x \cup S_y$ 的任何成员。由于我们要求各个集合不相交，故要“消除“原有的集合$S_x$ 和 $S_y$, 即把它们从集合中删除。实际上，我们经常把其中一个集合的元素并入另一个集合中，来代替删除操作。
• FIND-SET(x): 返回一个指针，这个指针指向包含x 的（唯一）集合的代表。我们使用两个参数来分析不相交集合数据结构的运行时间：一个参数是n, 表示
• MAKE-SET 操作的次数；另一个是m, 表示MAKE-SET 、UNION 和FIND-SET 操作的总次数。因为各个集合是不相交的，所以每个UNION 操作减少一个集合。因此， n-1 次UNION 操作后，只有一个集合留下来。也就是说， UNION 操作的次数至多是 n-1 。也要注意到，由千
• MAKE-SET 操作被包含在总操作次数m 中，因此有m~n。这里我们假设n 个MAKE-SET 操作总是最先执行的n 个操作。

21.2 不相交集合的链表表示

​ 如下图所示：每个集合用一个自己的链表来表示。每个集合的对象包含head 属性和tail 属性， head 属性指向表的第一个对象， tail 属性指向表的最后一个对象。链表中的每个对象都包含一个集合成员、一个指向链表中下一个对象的指针和一个指回到集合对象的指针。在每个链表中，对象可以以任意的次序出现。代表是链表中第一个对象的集合成员。

21.3 不相交集合森林

​ 在一个不相交集合更快的实现中，我们使用有根树来表示集合，树中每个结点包含一个成林(disjoint-set forest) 中，每个成员仅指向它的父结点。每棵树的根包含集合的代表，并且是其自己的父结点。正如我们将要看到的那样，虽然使用这种表示的直接算法并不比使用链表表示的算法快，但通过引入两种启发式策略("按秩合并”和“路径压缩＂），我们能得到一个渐近最优的不相交集合数据结构。