树算法
算法 

二叉搜索树

搜索树结构支持许多动态结合操作，包括SEARCH、MINMUM、MAXIMUX、PREDECESSOR、SUCCESSOR、INSERT、DELETE等。

二叉搜索树的性质如下： 设 x 是二叉搜索树的一个结点，如果 y 是 x 左子树中的一个结点，那么 $y.key \leq x.key$，如果y是x右子树的一个结点，那么 $y.key \geq x.key$

中序遍历： 输出的子树根的关键字位于其左子树的关键字和右子树关键字之间 先序遍历： 输出的根的关键字在其左右子树关键字之前 后序遍历： 输出的根的关键字在其左右子树关键字之后

二叉树的中序遍历算法如下：

INORDER-TREE-WALK(x)
    if (x!=NIL)
        INORDER-TREE-WALK(x.left)
        print x.key
        INORDER-TREE-WALK(x.right)

查询

使用如下递归算法在二叉搜索树中查找一个具有给定关键字的结点：

TREE-SEARCH(x,k)
    if x == NIL or k == x.key
        return x
    if k < x.key
        return TREE-SEARCH(x.left, key)
    else
        return TREE-SEARCH(x.right, key)

查找过程从树根开始，并沿着这棵树中的一条简单路径向下进行。对于每个遇到的结点x，经比较关键字k与x.key。若两个值相等，返回结果。若k小于x.key，继续查找x的左子树；若k大于x.key，继续查找x的右子树。

还可以采用迭代方式代替递归，因为迭代的效率要高得多：

ITERATIVE-TREE-SEARCH(x,k)
    while x != NIL and k != x.key
        if k < x.key
            x = x.left
        else 
            x = x.right
    return x

最大关键字最小关键字

如果结点x没有左子树，那么由于x右子树中的每个关键字都至少大于或等于x.key，则以x为根的子树中的最小关键字是x.key。 如果结点x有左子树，那么由于其右子树中没有关键字小于x.key，且在左子树中的每个关键字不大于x.key，则以x为根的子树中的最小关键字一定在x.left的子树中：

TREE-MINMUM(x)
    while x.left != NIL
        x = x.left
    return x

TREE-MAXMUM(x)
    while x.right != NIL
        x = x.right
    return x

后继和前驱

结点x的后继是大于x.key最小关键字的结点，前驱是小于x.key的最大关键字结点。

TREE-SUCCESSOR(x)
    if x.right != NIL
        return TREE-MINMUM(x.right)
    y = x.p
    while y != NIL and x == y.right
        x = y
        y = y.p
    return y

如果结点x的右子树非空，那么x的后继是x右子树的最左结点。如果x在右子树为空并有一个后继y，那么y就是x的最底层的祖先，并且y的左孩子也是x的一个祖先。

插入

插入和删除操作会引起二叉搜索树集合的变化，一定要修改数据结构来反映这个变化。 算法从树根开始，指针x记录了一条向下的简单路径，并查找要替换的输入项z的NIL，然后将z插入NIL的位置。

TREE-INSERT(T,z)
    y = NIL
    x = T.root
    while x != NIL
        y = x
        if z.key < x.key
            x = x.left
        else
            x - x.right
    z.p = y
    if y == NIL
        T.root = z
    elseif z.key < y.key
        y.left = z
    else 
        y.right = z

删除

从一棵二叉搜索树中删除一个结点 z 的整个策略分为三种基本情况：

  1. 如果 z 没有孩子结点，那么只是简单将其删除，并将 z 结点的父结点指向 z 的指针用 NIL 替换
  2. 如果 z 只有一个孩子结点，那么将该孩子结点提升到树 z 的位置，并修改 z 的父结点，用 z 的孩子替换 z
  3. 如果z 有两个孩子，那么找到 z 的后继 y ，并让 y 占据树中 z 的位置。z 原来的右子树成为 y 的新右子树，z 的左子树成为 y 的新左子树。

第3种情况比较复杂，与 y 是否是 z 的右孩子相关。

  • 如果 z 没有左孩子，那么用其右孩子来替换 z
  • 如果 z 仅有一个孩子且为左孩子，那么用左孩子替换 z
  • 如果 z 既有左孩子又有右孩子。需要查找 z 的后继 y，这个后继位于z 的右子树中并且没有左孩子。现在需要将 y 移出原来的位置进行拼接，并替换树种的 z
  • 如果 y 是 z 的右孩子，那么用 y 替换 z，并留下 y 的右孩子。
  • y 在 z 的右子树中，但并不是 z 的右孩子。先用 y 的右孩子替换 y，然后再用 y 替换 z。

定义一个移动子树的过程，将一个子树替换为另一个子树：

TRANSPLANT(T,u,v)
    if u.p == NIL
        T.root = v
    elseif u == u.p.left
        u.p.left = v
    else
        u.p.right = v
    if v != NIL
        v.p = u.p

从搜索二叉树中中删除结点 z 的伪代码如下：

TREE-DELETE(T,z)
    if z.left == NIL
        TRANSPLANT(T,z,z.right)
    else z.right == NIL
        TRANSPLANT(T,z,z.left)
    else 
        y = TREE-MINMUM(T, y, y.right)
        if y.p != z
            TRANSPLANT(T, y, y.right)
            y.right = z.right
            y.right.p = y
        TRANSPALAN(T, z, y)
        y.left = z.left
        y.left.p = y

在高度为 $h$ 的二叉搜索树上，实现动态集合操作 INSERT 和 DELETE 的运行时间为 $O(h)$.

随机构建二叉搜索树

二叉搜索树上的每个基本操作都能在 $O(h)$ 时间内完成。然而，随着元素的插入和删除，二叉搜索树的高度也在变化。如果n个关键字按照严格递增的次序插入，那么这棵树一定是高度为n-1的一条链。但是当n个不同的关键字随机构建二叉搜索树时，期望高度时 $O(\lg n)$。

二叉搜索树的高度较低时，集合操作执行会比较快。但是，如果树的高度较高时，这些集合操作可能并不比在链表上快。因此，引入了平衡搜索树。

Trie 树

红黑树

红黑树是许多平衡所搜树中的一种，可以保证在最坏情况下基本动态集合操作时间复杂度为 $O(\lg n)$

红黑树的性质

每个结点上有一个存储位是用来表示结点颜色的，可以是RED或BLACK。通过对任何一条从根到叶子的简单路径上各个结点颜色的约束，使红黑树没有一条路径会比其他路径长出2倍，因而是近似平衡的。

红黑树满足如下性质：

  1. 每个结点不是红色，就是黑色
  2. 根结点是黑色的
  3. 每个叶结点是黑色的
  4. 如果一个结点是红色的，则它的两个子结点是黑色的
  5. 对每个结点，从该结点到其后代所有叶节点的简单路径上，均包含相同数目的黑色结点。

为了便于表示红黑树代码中的边界条件，使用一个哨兵T.nil来代表NIL

黑高 从某个结点（不含该结点）出发到达一个叶结点的任意一条简单路径上的黑色结点个数。

旋转

搜索树操作 TREE-INSERT 和 TREE-DELETE 在红黑树上执行时，可能会违法红黑树的性质，为了维护这些性质，需要改变树中某些结点的颜色以及指针结构

指针结构的修改是通过旋转来完成的。旋转分为左旋和右旋。 左旋：当在结点 $x$ 上做左旋时（$x$ 是右孩子不是T.nil 结点的树内任意结点），假设它的右孩子为 $y$。左旋使得 $y$ 成为该子树的根结点， $x$ 成为 $y$ 的左孩子，$y$ 的左孩子成为 $x$ 的右孩子。

LEFT-ROTATE(T,x)
    y = x.right
    x.right = y.left
    if y.left != T.nil
        y.left.p = x
    y.p = x.p
    if x.p == T.nil
        T.root = y
    elseif x == x.p.left
        x.p.left = y
    else
        x.p.right = y
    y.left = x
    x.p = y

右旋与左旋是对称的。当在结点 $y$ 上做左旋时（$y$ 是左孩子不是T.nil 结点的树内任意结点），假设它的左孩子为 $y$。左旋使得 $x$ 成为该子树的根结点， $y$ 成为 $x$ 的右孩子，$x$ 的右孩子成为 $y$ 的左孩子。

RIGHT-ROTATE(T, y)
    x = y.left
    y.left = x.right
    if x.left != T.nil
        x.left.p = y
    x.p = y.p
    if y.p == T.nil
        T.root = x
    elseif y == y.p.left
        y.p.left = x
    else 
        y.p.right = x
    x.right = y
    y.p = x

插入

可以在 $O(\lg n)$ 时间内完成向一棵 $n$ 个结点的红黑树中插入一个新结点。插入同普通二叉搜索树相同，只是将插入的结点着为红色。

RB-INSERT(T,z)
    y = T.nil
    x = T.root
    while x != T.nil
        y = x
        if z.key < x.key
            x = x.left
        else 
            x = x.right
    z.p = y
    if y == T.nil
        T.root = z
    elseif z.key < y.key
        y.left = z
    else 
        y.right = z
    z.left = T.nil
    z.right = T.nil
    z.color = RED
    RB-INSERT-FIXUP(T,z)

为保证红黑树的性质，需要对结点重新着色并旋转。

RB-INSERT-FIXUP(T,z)
    // z.p == T.nil 
    while z.p.color == RED
        if z.p == z.p.p.left
            y = z.p.p.right
            if y.color == RED              // case 1
                z.p.color = BLACK
                y.color = BLACK
                z.p.p.color = RED
                z = z.p.p
                continue
            elseif z == z.p.right         // case 2
                z = z.p
                LEFT-ROTATE(T,z)
            z.p.color = BLACK            // case 3
            z.p.p.color = RED            // case 3
            RGIHT-ROTATE(T, z.p.p)       // case 3
        else 
            (sanme as then clause with 'right' and 'left' exchanged)
    T.root.color = BLACK

在 z 插入时，上述5个性质可能会被破坏。因为新插入的红结点的两个子结点都是哨兵 T.nil，因此性质1、性质3和性质5继续成立。如果z是根结点，破坏了性质2；如果z的父结点是红结点，则破坏了性质4.

如果违反了性质2，那么红色根结点一定是新增结点 z，它是树中唯一的内部结点。因为 z 的父结点和两个子结点都是哨兵 T.nil,没有违反性质4. 如果违反了性质4，由于z的子结点是黑色哨兵，且该树在 z 插入之前没有违反任何性质，那么违反必然是因为 z 和 z.p 都是红色，且没有其他性质被违反。解决该问题，有以下三种情况：

  1. z 的叔结点 y 是红色 这种情况在 z.p 和 y 都是红色时发生，因为 z.p.p 是黑色的，所以将 z.p 和 y 都着为黑色，来解决 z 和 z.p 都是红色的问题。然后将z.p.p作为新结点 z 来重复 while 循环。

  2. z 的叔结点 y 是黑色且 z 是一个右孩子

  3. z 的叔结点 y 是黑色且 z 是一个左孩子 在情况2中，通过左旋可以将此情况转变为情况3，而旋转不会违反红黑树的性质。而情况3可以通过改变结点颜色，并做一次右旋，以保持性质5

删除

红黑树上一个删除一个结点要花费 $O(\lg n)$的时间。 从一棵红黑树中删除结点是基于 TREE-DELETE 过程的：

RB-TRANSPLANT(T, u, v)
   if u.p == T.nil
       T.root = v
   elseif u == u.p.left
       u.p.left = v
   else 
       u.p.right = v
   v.p = u.p

过程 RB-DELETE 与 TREE-DELETE类似。但是记录了结点 y 的踪迹，因为 y 可能导致红黑树的性质被破坏。当要删除结点 z ，且此时 z 的子结点少于2个时， z 从树中删除，并让 y 成为 z。当 z 有两个结点时，y应该是z的后继，并且将 y 移至树中 z 的位置。在结点被移除或者在树中移动之前，必须记住y的颜色，并且记录结点 x 的踪迹，将 x 移至树中 y 的位置，因为结点 x 也可能破坏红黑树的性质。删除结点 z 之后，RB-DELETE 调用一个辅助过程 RB-DELETE-FIXUP，该过程通过改变颜色和执行旋转来恢复红黑性质。

RB-DELETE(T, z)
    y = z
    y-original-color = y.color
    if z.left == T.nil
        x = z.right
        RB-TRANSPLANT(T, z, z.right)
    elseif z.right == T.nil
        x = z.left
        RB-TRANSPLANT(T, z, z.left)
    else 
        y = TREE-MINIMUM(z.right)
        y-original-color = y.color
        x = y.right
        if y.p == z
            x.p = y
        else 
            RB-TRANSPLANT(T, y, y.right)
            y.right = z.right
            y.right.p = y
        RB-TRANSPLANT(T, z, y)
        y.left = z.left
        y.left.p = y
        y.color = z.color
    if y-original-color == BLACK
        RB-DELETE-FIXUP(T, x)

RB-DELETE 同 TREE-DELETE相似，只是维持了从树中删除或者移至树内的结点y。如果最后 y 的颜色是黑色，那么就有可能破坏了红黑树的性质，所以需要恢复：

RB-DELETE-FIXUP(T, x)
    while x != T.root and x.color == BLACK
        if x == x.p.left
            w = x.p.right
            if w.color == RED
                w.color = BLACK
                x.p.color = RED
                LEFT-ROTATE(T, x.p)
                w = x.p.right
            if w.left.color =- BLACK and w.right.color == BLACK
                w.color = RED
                x = x.p
            else 
                if w.right.color == BLACK
                    w.left.color = BLACK
                    w.color = RED
                    RIGHT-ROTATE(T, w)
                    w = x.p.right
                w.color = x.p.color
                x.p.color = BLACK
                w.right.color = BLACK
                LEFT-ROTATE(T, x.p)
                x = T.root
        else 
            same as then clause with "right" and "left" exchanged

B-Tree

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

大多数系统中，B树算法的运行时间主要由它执行的磁盘读取和写入操作的次数决定，所以我们希望这些操作能够一次读或写尽可能多的信息。因此一个B树结点通常和一个完整磁盘页一样大，并且磁盘页的大小限制了一个B树结点可以含有孩子个数。

B树定义

一棵B树T是具有以下性质的有根数：

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

常见的B树变种B+树将所有的卫星数据都存储在叶结点中，内部结点只存放关键字和孩子指针，最大化了内部结点的分支因子。

B树上的基本操作

B树上操作有两个约定：

  • B树的根结点始终在主内存中，这样无需对根做 DISK-READ 操作；当根结点被需改后，需要对根结点做一次 DISK-WRITE 操作
  • 任何被当做参数的结点被传递之前，都需要做一次DISK-READ操作。

搜索B树

搜索B树同搜索二叉树相似，只是根据结点的孩子树做多路分支选择。

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

创建一棵空的 B树

构造一个B树，需要在 $O(1)$ 的时间为一个新结点分配一个磁盘页：

B-TREE-CREATE(T)
    x = ALLOCATE-NODE()
    x.leaf = TRUE
    x.n = 0
    DISK-WRITE(x)
    T.root = x

分裂结点

向B树中插入关键字不能直接创建新的叶结点，然后将其插入，因为这样得到的不是合法的B树。我们需要将新的关键字插入到一个已经存在的结点上，如果该结点是满的，那么需要按其中间关键字分裂成两个各含有 t-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+i
        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] = y.key[t]
    x.n = x.n + 1
    DISK-WRITE(y)
    DISK-WRITE(z)
    DISK-WRITE(x)

插入关键字

在一棵高度为 h 的B树中，以沿树单程下行方式插入一个关键字的操作需要 $O(h)$ 次磁盘存取。

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-SPILT-CHILD(s, 1)
        B-TREE-INSERT-NONFULL(s, k)
    else 
        B-TREE-INSERT-NONFULL(r, k)

过程 B-TREE-INSERT-NONFULL 完成将 k 插入非满的树中。

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
    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树种删除关键字

B树上的删除操作与插入操作类似，必须防止因删除操作而导致树的结构违反B树性质，保证一个结点不会因为删除一个关键字儿变得太小。当删除关键字的路径上结点（非根）有最少的关键字个数时，可能需要向上回溯。

在以 $x$ 为根的子树中删除关键字 $k$，过程中必须保证结点 $x$ 递归调用自身时，$x$ 中的关键字个数至少为最小度数 $t$（这样运行在一趟下降过程中，可以将一个关键字移到子节点中，无需回溯）。

删除情况如下：

  1. 如果关键字 $k$ 在结点 $x$ 中，并且 $x$ 是叶结点，则从$x$ 中删除$k$
  2. 如果关键字 $k$ 在结点 $x$ 中，并且$x$ 是内部结点，则做如下操作：
    1. 如果结点$x$ 中前于 $k$ 的子结点 $y$ 至少包含 $t$ 个关键字，则找出 $k$ 在以$y$ 为根的子树中的前驱 $k'$. 递归删除 $k'$，并在 $x$ 中用$k'$替代 $k$
local_offer #算法 
navigate_before navigate_next