第三部分 数据结构

​ 集合作为计算机科学的基础，就如同它们在数学中所起的作用。数学中的集合是不变的，而由算法操作的集合却在整个过程中能增大、缩小或发生其他变化。我们称这样的集合是动态的。

动态集合的元素

​ 在动态集合的典型实现中，每个元素都由一个对象来表示，如果有一个指向对象的指针，就能对其各个属性进行检查和操作。

​ 一些类型的动态集合假定对象中的一个属性为标识关键宇(key) 。对象可能包含卫星数据，它们与其他对象属性一起移动，除此之外，集合实现不使用它们。对象也可以有由集合操作使用的属性；这些属性可能包含有关集合中其他对象的数据或指针。

动态集合上的操作

​ 动态集合上的操作可以分为两类：简单返回有关集合信息的查询操作和改变集合的修改操作。

• SEARCH(S, k): 一个查询操作，给定一个集合S 和关键字k, 返回指向S 中某个元素的指针x, 使得 x.key=k ; 如果S 中没有这样的元素，则返回NIL 。
• INSERT(S, x): 一个修改操作，将由x 指向的元素加入到集合S 中。通常假定元素x 中集合S 所需要的每个属性都巳经被初始化好了。
• DELETE(S, x): 一个修改操作，给定指针x 指向集合S 中的一个元素，从S 中删除x 。（注意，这个操作取一个指向元素x 的指针作为输入，而不是一个关键字的值。）
• MINIMUM(S): 一个查询操作，在全序集S 上返回一个指向S 中具有最小关键字元素的指针。
• MAXIMUM(S) : 一个查询操作，在全序集S 上返回一个指向S 中具有最大关键字元素的指针。
• SUCCESSOR(S, x) : 一个查询操作，给定关键字属于全序集S 的一个元素x, 返回S 中比x 大的下一个元素的指针；如果x 为最大元素，则返回NIL 。
• PREDECESSOR(S, x): 一个查询操作，给定关键字属于全序集S 的一个元素x, 返回S 中比x 小的前一个元素的指针；如果x 为最小元素，则返回NIL 。

​ 在某些情况下，能够将SUCCESSOR 和PREDECESSOR 查询操作推广应用到一些具有相同关键字的集合上。对于一个有n 个关键字的集合，通常的假设是调用一次MAXIMUM 后再调用 n-1 次SUCCESSOR, 就可以按序枚举出该集合中的所有元素。

第十章 基本数据结构

10.1 栈和队列

​ 在栈(stack) 中，被删除的是最近插入的元素：栈实现的是一种后进先出（last-in, first-out, LIFO) 策略。

​ 在队列(queue) 中，被删去的总是在集合中存在时间最长的那个元素：队列实现的是一种先进先出(first-in, first-out, FIFO) 策略。

栈

​ 栈上的INSERT 操作称为压人(PUSH) ，而无元素参数的DELETE 操作称为弹出(POP) 。

用一个数组 $S[1.. n]$ 来实现一个最多可容纳n 个元素的栈。栈的几种操作只需分别用几行代码来实现：

STACK-EMTY(S)
  if S.tap == O
    return TRUE
  else
    return FALSE

PUSH(S, x)
  S.top = S.top + 1
  S[S.top] = x

POP(S)
  if STACK-EMPTY(S)
    error "underflow"
  else 
    S.top = S.top - 1
  return S[S.top + 1]

队列

​ 队列上的INSERT 操作称为入队(ENQUEUE), DELETE 操作称为出队(DEQUEUE)；队列有队头(head) 和队尾(tail), 当有一个元素入队时，它被放在队尾的位置，而出队的元素则总是在队头的那个。

​ 用数组 $Q[1.. n]$ 来实现一个最多容纳 n-1 个元素的队列，该队列有一个属性 Q.head 指向队头元素。而属性Q.tail 则指向下一个新元素将要插入的位置。队列中的元素存放在位置 Q.head , Q.head + 1, … , Q.tail - 1, 当 Q.head= Q.tail 时，队列为空,拖此时从空队列中删除一个元素，则队列发生下溢。当Q.head=Q. tail+l 时，队列是满的，此时若试图插入一个元素，则队列发生上溢。

ENQUEUE(Q, x)
  Q[Q.tail] = x
  if Q.tail == Q.length
    Q.tail = 1
  else
    Q.tail = Q.tail + 1

DEQUEUE(Q)
  x = Q[Q.head]
  if Q.head == Q.length
    Q.head = 1
  else 
    Q.head = Q.head + 1
  return x

10.2 链表

​ 链表Oinked list)中的各对象按线性顺序排列，链表的顺序是由各个对象里的指针决定的。

​ 双向链表(doubly linked list) L 的每个元素都是一个对象，每个对象有一个关键字key 和两个指针： next 和prev 。对象中还可以包含其他的辅助数据（或称卫星数据）。设x为链表的一个元素， x.next 指向它在链表中的后继元素， x.prev 则指向它的前驱元素。

​ 链表可以有多种形式。

• 若为单链接的(singly linked) , 则省略每个元素中的prev 指针。
• 若链表是已排序(sorted) 的，则链表的线性顺序与链表元素中关键字的线性顺序一致。
• 若链表是未排序(unsorted) 的，则各元素可以以任何顺序出现。
• 在循环链表(circular list) 中，表头元素的prev 指针指向表尾元素，而表尾元素的next 指针则指向表头元素。

假设所处理的链表都是未排序的且是双链接的。

链表的搜索

​ 过程LIST-SEARCH(L, k) 采用简单的线性搜索方法，，用于查找链表L 中第一个关键字为K的元素，并返回指向该元素的指针，在最坏情况下的运行时间为 O(n)。

LIST-SEARCH(L, k)
  x = L.head
  while x != NIL and x.key != k
    x = x.next
  return x

链表的插入

​ 给定一个已设置好关键字key 的元素x, 过程LIST-INSERT 将x"连接入”到链表的前端，运行时间是 O(1) 。

LIST-INSERT(L, x)
  x.next = L.head
  if L.head != NIL
    L.head.prev = x
  L.head = x
  x.prev = NIL

链表的删除

​ 过程LIST-DELETE 将一个元素x 从链表L 中移除。该过程要求给定一个指向x 的指针，然后通过修改一些指针，将x"删除出“该链表。如果要删除具有给定关键字值的元素，则必须先调用 LIST-SEARCH 找到该元素。

LIST-DELETE(L, x)
  if x.prev != NIL
    x.prev.next = x.next
  else 
    L.head = x.next
  if x.next != NIL
    x.next.prev = x.pre

哨兵

​ 哨兵(sentinel) 是一个哑对象，其作用是简化边界条件的处理。哨兵L.nil 位于表头和表尾之间。属性 L.nil.next 指向表头， L. nil.prev 指向表尾。

10.3 指针和对象的实现

​ 用数组实现指针的数据结构

10.4 有根树的表示

​ 二叉树 T 中属性p 、left 和right 分别存放指向父结点、左孩子和右孩子的指针。

​ 二叉树的表示方法可以推广到每个结点的孩子数至多为常数K 的任意类型的树：只需要将left 和五ght 属性用$child_1 , child_2 , …， child_k$ 代替。

第十一章 散列表

11.1 直接寻址表

当关键字的全域 U 比较小时，直接寻址是一种简单而有效的技术，将数据放入其值对应的数组索引中，即具有关键字k 的元素被存放在槽k 中。

11.2 散列表

​ 在直接寻址方式下，具有关键字k 的元素被存放在槽k 中。在散列方式下，该元素存放在槽h(k) 中；即利用散列函数(hash function) h, 由关键字k 计算出槽的位置。这里，函数h 将关键字的全域U 映射到散列表(hash table) $T[0… m-1] $ 的槽位上，这里散列表的大小m 一般要比 |U| 小得多。

$$h:U \rightarrow \{0,1,...,m-1 \}$$

​ 两个关键字可能映射到同一个槽中。我们称这种情形为冲突(collision) 。

通过链接法解决冲突：在链接法中，把散列到同一槽中的所有元素都放在一个链表中。

11.3 散列函数

11. 3.1 除法散列法

​ 通过取k 除以m 的余数，将关键字k 映射到m 个槽中的某一个上，即散列函数为：$h(k)=k \: mod \: m$

​ 当应用除法散列法时，要避免选择m 的某些值。一个不太接近2 的整数幕的素数，常常是m 的一个较好的选择。

11. 3.2 乘法散列法

​ 构造散列函数的乘法散列法包含两个步骤。第一步，用关键字k 乘上常数A(0<A<1), 并提取 kA 的小数部分。第二步，用m 乘以这个值，再向下取整。总之，散列函数为：$h(k) = \lfloor m(kA \: mod \: 1) \rfloor$

​ 乘法散列法的一个优点是对m 的选择不是特别关键，一般选择它为2 的某个幕次，最佳的选择与待散列的数据的特征有关。

11. 3.3 全域散列法

​ 全域散列法在执行开始时，就从一组精心设计的函数中，随机地选择一个作为散列函数。随机化保证了没有哪一种输入会始终导致最坏情况性能，且因为随机地选择散列函数，算法在每一次执行时都会有所不同，这样就可以确保对于任何输入，算法都具有较好的平均情况性能。

11.4 开放寻址法

​ 在开放寻址法(open addressing) 中，所有的元素都存放在散列表里。也就是说，每个表项或包含动态集合的一个元素，或包含NIL。当查找某个元素时，要系统地检查所有的表项，直到找到所需的元素，或者最终查明该元素不在表中，装载因子a 绝对不会超过1 。

​ 不用存储指针而节省的空间，使得可以用同样的空间来提供更多的槽，潜在地减少了冲突，提高了检索速度。

​ 为了使用开放寻址法插入一个元素，需要连续地检查散列表，或称为探查(probe), 直到找到一个空槽来放置待插入的关键字为止。

​ 有三种技术常用来计算开放寻址法中的探查序列：线性探查、二次探查和双重探查。

线性探查

​ 给定一个普通的散列函数 $h':U \rightarrow \{0, 1 ,..., m-1\}$ , 称之为辅助散列函数(auxiliary hashfunction), 线性探查Clinear probing) 方法采用的散列函数为：$h(k,i) = (h'(k) +i)mod \:m, i = 0,1, …, m-1$

​ 线性探查方法比较容易实现，但它存在着一个问题，称为一次群集(primary clustering) 。随着连续被占用的槽不断增加，平均查找时间也随之不断增加。

二次探查

​ 二次探查(quadratic probing) 采用如下形式的散列函数：$h(k,i) = (h'(k) + c_1i + c_2i^2)mod \:m$

​ 如果两个关键字的初始探查位置相同，那么它们的探查序列也是相同的，这是因为h(k1, 0) =h(k2’0) 蕴涵着hCk1, i) =h(k2, i) 。这一性质可导致一种轻度的群集，称为二次群集(secondary clustering)

双重散列

​ 双重散列(double hashing) 是用于开放寻址法的最好方法之一，因为它所产生的排列具有随机选择排列的许多特性。双重散列采用如下形式的散列函数：$h(k,i) = (h_1(k) + ih_2(k))mod \:m$ ，其中h1 和比均为辅助散列函数。

为了能查找整个散列表，值 $h_2(k) $ 必须要与表的大小m 互素。有一种简便的方法确保这个条件成立，就是取m 为2 的幕，并设计一个总产生奇数的 h₂ 。另一种方法是取m为素数，并设计一个总是返回较m 小的正整数的函数h₂。

11.5 完全散列

​ 完全散列(perfecthashing), 用该方法进行查找时，能在最坏情况下用0(1) 次访存完成。

​ 采用两级的散列方法来设计完全散列方案，在每级上都使用全域散列。

• 第一级与带链接的散列表基本上是一样的：利用从某一全域散列函数簇中仔细选出的一个散列函数h, 将n 个关键字散列到m 个槽中。

• 第二级使用了一个较小的二次散列表(secondary hash table) S; 及相关的散列函数h_j, 而不是将散列到槽j 中的所有关键字建立一个链表。利用精心选择的散列函数h_j 可以确保在第二级上不出现冲突。

  为了确保在第二级上不出现冲突，需要让散列表S_j 的大小m_j 为散列到槽j 中的关键字数n_j 的平方。尽管m_j 对n_j 的这种二次依赖看上去可能使得总体存储需求很大，但我们会在后面说明，通过适当地选择第一级散列函数，可以将预期使用的总体存储空间限制为O(n) 。

第十二章 二叉搜索树

​ 可以将二叉树的节点设置为可以存储多个数据，比如用数量表示当前节点元素个数实现插入相同的元素，默认下述二叉搜索树元素均不可相等。

12.1 什么是二叉搜索树

​ 二叉搜索树中的关键字总是以满足二叉搜索树性质的方式来存储：设x 是二叉搜索树中的一个结点。如果y 是x 左子树中的一个结点，那么 $y.key \le x. key$。如果y 是x 右子树中的一个结点，那么 $y.key \le x.key$ 。

中序遍历

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

12.2 查询二叉搜索树

查找

​ 输入一个指向树根的指针和一个关键字k, 如果这个结点存在， TREE-SEARCH 返回一个指向关键字为K 的结点的指针；否则返回NIL 。

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

最大关键字元素和最小关键字元素

​ 通过从树根开始沿着left 孩子指针直到遇到一个NIL, 我们总能在一棵二叉搜索树中找到一个最小元素，同理通过从树根开始沿着 right 孩子指针直到遇到一个NIL, 我们总能在一棵二叉搜索树中找到一个最大元素。

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

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

后继和前驱

​ 给定一棵二叉搜索树中的一个结点，有时候需要按中序遍历的次序查找它的后继。如果所有的关键字互不相同，则一个结点x 的后继是大于 x.key 的最小关键字的结点。一棵二叉搜索树的结构允许我们通过没有任何关键字的比较来确定一个结点的后继。

寻找后继算法步骤：

1. 当前节点的右子树不为空。则一直遍历右子树的左节点，直至为null。
2. 当前节点的右子树为空，则从父节点开始寻找后继节点：
   1. 如果当前节点为父节点的左子树，则后继节点即为父节点。例：9的后继节点为10。
   2. 如果当前节点为父节点的右子树，则依次遍历父节点，直至遍历节点的父节点为左子树为止，因为如果遍历的父节点一直为右节点，肯定是比该节点小的，只有找到节点的父节点为左子树时，找到节点的父节点才比它大，即为后继节点。
   3. 如果父节点为空，返回当前节点的父节点，即 == null。

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

TREE-PREDECESSOR(x)
  if x.left != NIL
    return TREE-MAXIMUM(x.left)
  y = x.p
  while y != NIL and x == y.left
    x = y
    y = y.p
  return y

12.3 插入和删除

​ 要将一个新值v 插入到一棵二叉搜索树T 中，需要调用过程TREE-INSERT。该过程以结点 z 作为输入，其中z.key=v, z.left=NIL, z.right=NIL。这个过程要修改T 和z 的某些属性，来把z 插入到树中的相应位置上。

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 // tree T was empty
  else if z.key < y.key
    y.left = z
  else 
    y.right = z

删除

从一棵二叉搜索树T 中删除一个结点z 的整个策略分为三种基本情况（如下所述）:

• 如果z 没有孩子结点，那么只是简单地将它删除，并修改它的父结点，用NIL 作为孩子来替换z 。
• 如果z 只有一个孩子，那么将这个孩子提升到树中z 的位置上，并修改z 的父结点，用z的孩子来替换z 。
• 如果z 有两个孩子，那么找z 的后继y(一定在z 的右子树中），并让y 占据树中z 的位置。z 的原来右子树部分C:\WorkPlace\VisualStudioCode\java\tree\BinarySearchTree.java成为y 的新的右子树，并且z 的左子树成为y 的新的左子树。这种情况稍显麻烦（如下所述），因为还与y 是否为z 的右孩子相关。

为了在二叉搜索树内移动子树，定义一个子过程TRANSPLANT, 它是用另一棵子树替换一棵子树并成为其双亲的孩子结点：

子树交换程序

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

从二叉搜索树T 中删除结点z 的删除过程：

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

java实现代码：

import java.util.LinkedList;
import java.util.Queue;

public class BinarySearchTreeParent {
    public static class TreeNode {
        public int val;
        public TreeNode parent;
        public TreeNode left;
        public TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    private TreeNode root;

    public BinarySearchTreeParent() {
        this.root = null;
    }

    public BinarySearchTreeParent(TreeNode root) {
        this.root = root;
    }

    public void insert(int val) {
        TreeNode node = new TreeNode(val);
        if (root == null) {
            this.root = node;
            return;
        }

        // 查询替换数据
        TreeNode pre = null, p = root;
        while (p != null) {
            pre = p;
            if (val < p.val) {
                p = p.left;
            } else {
                p = p.right;
            }
        }

        node.parent = pre;
        if (val < pre.val) {
            pre.left = node;
        } else {
            pre.right = node;
        }
    }
    
    private void transplant(TreeNode n1, TreeNode n2) {
        // 空判断
        if (n1.parent == null) {
            root = n2;
            return;
        }

        if (n1 == n1.parent.left) {
            // 是父亲的左孩子
            n1.parent.left = n2;
        } else {
            n1.parent.right = n2;
        }

        if (n2 != null) {
            n2.parent = n1.parent;
        }
        // 释放 n1
    }

    private void delete(TreeNode node) {
        if (node.left == null) {
            transplant(node, node.right);
        } else if (node.right == null) {
            transplant(node, node.left);
        } else {
            TreeNode next = successor(node);
            if (next.parent != node) {
                transplant(next, next.right);
                next.right = node.right;
                next.right.parent = next;
            }

            transplant(node, next);
            next.left = node.left;
            node.left.parent = next;
        }
    }

    public void delete(int val) {
        TreeNode node = search(this.root, val);
        delete(node);
    }

    public TreeNode search(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }

        if (val < root.val) {
            return search(root.left, val);
        } else {
            return search(root.right, val);
        }
    }

    private TreeNode minium(TreeNode node) {
        if (node == null) {
            return null;
        }
        TreeNode p = node;
        while (p.left != null) {
            p = p.left;
        }
        return p;
    }

    public TreeNode minium() {
        return minium(this.root);
    }

    private TreeNode maximum(TreeNode node) {
        if (node == null) {
            return null;
        }
        TreeNode p = node;
        while (p.right != null) {
            p = p.right;
        }
        return p;
    }

    public TreeNode maximum() {
        return maximum(this.root);
    }

    public TreeNode successor(TreeNode node) {
        if (node == null) {
            return null;
        }

        TreeNode p = node;
        if (p.right != null) {
            return minium(p.right);
        } else {
            TreeNode next = p.parent;
            while (next != null && next.right == p) {
                p = next;
                next = next.parent;
            }

            return next;
        }
    }

    public TreeNode predecessor(TreeNode node) {
        if (node == null) {
            return null;
        }

        TreeNode p = node;
        if (p.left != null) {
            return maximum(p.left);
        } else {
            TreeNode pre = p.parent;
            while (pre != null && pre.left == p) {
                p = pre;
                pre = pre.parent;
            }

            return pre;
        }
    }

    private void printOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        printOrder(root.left);
        System.out.print(root.val + ", ");
        printOrder(root.right);
    }
    
    public void printOrder() {
        printOrder(root);
        System.out.println();
    }

    public void printLayer() {
        Queue<TreeNode> 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++) {
                TreeNode node = queue.poll();
                if (node == null) {
                    System.out.print("null,");

                } else {
                    System.out.print(node.val + ",");
                    queue.offer(node.left);
                    queue.offer(node.right);
                    if(node.left != null || node.right != null){
                        isDo = true;
                    }
                }
            }
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        BinarySearchTreeParent tree = new BinarySearchTreeParent();
        tree.insert(8);
        tree.insert(4);
        tree.insert(13);
        tree.insert(2);
        tree.insert(6);
        tree.insert(10);
        tree.insert(1);
        tree.insert(3);
        tree.insert(5);
        tree.insert(7);
        tree.insert(9);
        tree.insert(12);
        tree.printLayer();
        tree.delete(6);
        tree.printLayer();
    }
}

import java.util.LinkedList;
import java.util.Queue;

public class BinarySearchTree {
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    private TreeNode root;

    public BinarySearchTree() {
        this.root = null;
    }

    public BinarySearchTree(TreeNode root) {
        this.root = root;
    }

    public void insert(int val) {
        TreeNode node = new TreeNode(val);
        if (root == null) {
            this.root = node;
            return;
        }

        // 查询替换数据
        TreeNode pre = null, p = root;
        while (p != null) {
            pre = p;
            if (val < p.val) {
                p = p.left;
            } else {
                p = p.right;
            }
        }

        if (val < pre.val) {
            pre.left = node;
        } else {
            pre.right = node;
        }
    }

    /**
     * 另一种删除元素的方式
     * @param root
     * @param key
     * @return
     */
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null)
            return null;
        if (root.val == key) {
            if (root.left == null) return root.right;
            if (root.right == null) return root.left;

            TreeNode next = successor(root);
            // 此处不能先对 next.left 赋值，因为 root.right 中还有 next这个元素
            // 赋值后会导致需要删除的 root.right 子树的节点增加
            next.right = deleteNode(root.right, next.val);
            next.left = root.left;
            return next;
        }

        if (root.val > key) {
            root.left = deleteNode(root.left, key);
        } else {
            root.right = deleteNode(root.right, key);
        }

        return root;
    }

    private void transplant(TreeNode n1, TreeNode n2) {
        TreeNode n1Parent = searchParent(n1);

        // 空判断
        if (n1Parent == null) {
            root = n2;
            return;
        }

        if (n1 == n1Parent.left) {
            // 是父亲的左孩子
            n1Parent.left = n2;
        } else {
            n1Parent.right = n2;
        }
    }

    private TreeNode searchParent(TreeNode node) {
        if(node == root) return null;
        TreeNode pre = null, p = root;
        while(p != null && p != node) {
            pre = p;
            if(node.val < p.val) {
                p = p.left;
            } else {
                p = p.right;
            }
        }
        return pre;
    }

    private void delete(TreeNode node) {
        if (node.left == null) {
            transplant(node, node.right);
        } else if (node.right == null) {
            transplant(node, node.left);
        } else {
            TreeNode next = successor(node);
            if (searchParent(next) != node) {
                transplant(next, next.right);
                next.right = node.right;
            }

            transplant(node, next);
            next.left = node.left;
        }
    }

    public void delete(int val) {
        TreeNode node = search(val);
        delete(node);
    }

    private TreeNode search(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }

        if (val < root.val) {
            return search(root.left, val);
        } else {
            return search(root.right, val);
        }
    }

    public TreeNode search(int val) {
        return search(this.root, val);
    }

    private TreeNode minium(TreeNode node) {
        if (node == null) {
            return null;
        }
        TreeNode p = node;
        while (p.left != null) {
            p = p.left;
        }
        return p;
    }
    
    public TreeNode minium() {
        return minium(this.root);
    }

    private TreeNode maximum(TreeNode node) {
        if (node == null) {
            return null;
        }
        TreeNode p = node;
        while (p.right != null) {
            p = p.right;
        }
        return p;
    }

    public TreeNode maximum() {
        return maximum(this.root);
    }

    public TreeNode successor(TreeNode node) {
        if (node == null) {
            return null;
        }

        TreeNode p = node;
        if (p.right != null) {
            return minium(p.right);
        } else {
            TreeNode next = null, q = root;
            while(q != null && q != p) {
                if(p.val < q.val) {
                    next = q;
                    q = q.left;
                } else {
                    q = q.right;
                }
            }

            return next;
        }
    }

    public TreeNode predecessor(TreeNode node) {
        if (node == null) {
            return null;
        }

        TreeNode p = node;
        if (p.left != null) {
            return maximum(p.left);
        } else {
            TreeNode pre = null, q = root;
            while (q != null && q != p) {
                if(p.val < q.val){
                    q = q.left;
                } else {
                    pre = q;
                    q = q.right;
                }
            }

            return pre;
        }
    }

    private void printOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        printOrder(root.left);
        System.out.print(root.val + ", ");
        printOrder(root.right);
    }
    
    public void printOrder() {
        printOrder(root);
        System.out.println();
    }

    public void printLayer() {
        Queue<TreeNode> 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++) {
                TreeNode node = queue.poll();
                if (node == null) {
                    System.out.print("null,");

                } else {
                    System.out.print(node.val + ",");
                    queue.offer(node.left);
                    queue.offer(node.right);
                    if(node.left != null || node.right != null){
                        isDo = true;
                    }
                }
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        tree.insert(8);
        tree.insert(4);
        tree.insert(13);
        tree.insert(2);
        tree.insert(6);
        tree.insert(10);
        tree.insert(1);
        tree.insert(3);
        tree.insert(5);
        tree.insert(7);
        tree.insert(9);
        tree.insert(12);
        tree.printLayer();
        tree.delete(6);
        tree.printLayer();
    }
}

12.4 随机构建二叉搜索树

​ 二叉搜索树上的每个基本操作都能在O(h) 时间内完成，其中h 为这棵树的高度，$h \ge \lfloor lgn \rfloor$, 。和快速排序一样其平均情形性能更接近千最好情形。

第十三章 红黑树

13.1 红黑树的性质

​ 红黑树是一棵二叉搜索树，它在每个结点上增加了一个存储位来表示结点的颜色，可以是RED 或BLACK。通过对任何一条从根到叶子的简单路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2 倍，因而是近似千平衡的。

​ 树中每个结点包含5 个属性： color 、key 、left 、right 和P 。如果一个结点没有子结点或父结点，则该结点相应指针属性的值为NIL。我们可以把这些NIL 视为指向二叉搜索树的叶结点（外部结点）的指针，而把带关键字的结点视为树的内部结点。

一棵红黑树是满足下面 红黑性质 的二叉搜索树：

• 每个结点或是红色的，或是黑色的。
• 根结点是黑色的。
• 每个叶结点(NIL) 是黑色的。
• 如果一个结点是红色的，则它的两个子结点都是黑色的。
• 对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。

​ 为了便于处理红黑树代码中的边界条件，使用一个哨兵来代表NIL。对于一棵红黑树T, 哨兵T.nil 是一个与树中普通结点有相同属性的对象。它的color 属性为BLACK, 而其他属性任意，所有指向NIL 的指针都用指向哨兵 T.nil 的指针替换。

​ 从某个结点x 出发（不含该结点）到达一个叶结点的任意一条简单路径上的黑色结点个数称为该结点的黑高(black-height) , 记为bh(x) 。从该结点出发的所有下降到其叶结点的简单路径的黑结点个数都相同。因此定义红黑树的黑高为其根结点的黑高。

13.2 旋转

​ 搜索树操作TREE-INSERT 和TREE-DELETE 在含n 个关键字的红黑树上，运行花费时间为 $O(lgn)$ 。指由于这两个操作对树做了修改，结果可能违反红黑性质，为了维护这些性质，必须要改变树中某些结点的颜色以及指针结构。

​ 针结构的修改是通过旋转(ratation) 来完成的，这是一种能保持二叉搜索树性质的搜索树局部操作。

​ 左旋和右旋：当在某个结点x 上做左旋时，假设它的右孩子为y 而不是T.nil; x 可以为其右孩子不是T. nil 结点的树内任意结点。左旋以x 到y 的链为＂支轴”进行。它使y 成为该子树新的根结点， x 成为y 的左孩子， y 的左孩子成为x 的右孩子。

假设 $x.right \: != T.nil$ 且根结点的父结点为 $T.nil$ ：

向左旋转：

LEIT-ROTATE(T, x)
  y = x.right			// set y
  x.right = y.left		// turn y's left subtree into x's right subtree
  if y.left != T.nil
    y.left.p = x
  y.p = x.p				// link x's parent toy
  if x.p == T.nil
    T.root = y
  else if x == x.p.left
    x.p.left = y
  else 
    x.p.right = y
  y.left = x			// put x on y's left
  x.p = y

向右旋转：

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

{collapse}
{collapse-item label=“旋转节点示例” }

13.3 插入

​ 在 $O(lgn)$ 时间内完成向一棵含n 个结点的红黑树中插入一个新结点。利用 TREE-INSERT 过程的一个略作修改的版本来将结点z 插入树T 内，就好像T 是一棵普通的二叉搜索树一样，然后将z 着为红色。调用一个辅助程序RB-INSERT-FIXUP 来对结点重新着色并旋转。调用 RB-INSERT(T, z) 在红黑树T 内插入结点之，假设z 的key 属性已被事先赋值。

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
  else if z.key < y.key
    y.left = z
  else
    y.rght = z
  z.left = T.nil
  z.right = T.nil
  z.color = RED
  RB-INSERT-FIXUP(T, z)

插入修复程序：

RB-INSERT-FIXUP(T, z)
  while z.p.color == RED
    if z.p == z.p.p.left
      y = z.p.p.right
      if y.color == RED        // 条件：叔叔是红色
        z.p.color = BLACK      // Case 1 (01) 将“父节点”设为黑色。
        y.color = BLACK        // Case 1 (02) 将“叔叔节点”设为黑色。
        z.p.p.color = RED      // Case 1 (03) 将“祖父节点”设为“红色”。
        z = z.p.p              // Case 1 (04) 将“祖父节点”设为“当前节点”(红色节点)
      else if z == z.p.right   // 条件：叔叔是黑色，且当前节点是右孩子
        z = z.p                // Case 2 (01) 将“父节点”作为“新的当前节点”。
        LEFT-ROTATE(T, z)      // Case 2 (02) 以“新的当前节点”为支点进行左旋。
      else                     // 条件：叔叔是黑色，且当前节点是左孩子。
        z.p.color = BLACK      // Case 3 (01) 将“父节点”设为“黑色”。
        z.p.p.color = RED      // Case 3 (02) 将“祖父节点”设为“红色”。
        RIGHT-ROTATE(T, z.p.p) // Case 3 (03) 以“祖父节点”为支点进行右旋。
    else  // same as then clause with "right" and "left" exchanged
    ...
  T.root.color= BLACK

​ 在插入给定的数据后，只有性质2 和性质4可能被破坏，即根结点需要为黑色以及一个红结点不能有红孩子。这两个性质可能被破坏是因为z 被着为红色。如果z 是根结点，则破坏了性质2; 如果z 的父结点是红结点，则破坏了性质4 。

while 循环在每次迭代的开头保待下列3 个部分的不变式：

​ a. 结点z 是红结点。
​ b. 如果z.p 是根结点，则z.p 是黑结点。
​ c. 如果有任何红黑性质被破坏，则至多只有一条被破坏，或是性质2, 或是性质4 。如果性质2 被破坏，其原因为z 是根结点且是红结点。如果性质4 被破坏，其原因为z 和 z.p 都是红结点。

算法分析

​ 由于一棵有n 个结点的红黑树的高度为OClgn), 因此RBINSERT的第1~16 行要花费$O(lgn)$ 时间。在RB-INSERT-FIXUP 中，仅当情况1 发生，然后指针z 沿着树上升2 层， while 循环才会重复执行。所以while 循环可能被执行的总次数为$O(lgn)$。因此， RB-INSERT 总共花费$O(lgn)$ 时间。此外，该程序所做的旋转从不超过2 次，因为只要执行了情况2 或情况3, while 循环就结束了。

{collapse}
{collapse-item label=“插入结点z后性质被破坏的情况” }

当前节点为x，且父节点是祖父节点的左孩子

case 1：父亲是红色的，叔叔也是红色的

处理方法：

1. 将“父节点”设为黑色
2. 将“叔叔节点”设为黑色
3. 将“祖父节点”设为红色
4. 将“祖父节点”设为当前节点

case 2：父亲是红色的，叔叔是黑色的，当前节点是右孩子

处理方法：

1. 将“父节点”作为“当前节点”
2. 以“当前节点”为支点进行左旋

case 3：父亲是红色的，叔叔是黑色的，当前节点是左孩

处理方法：

1. 将“父节点”设为黑色。
2. 将“祖父节点”设为红色。
3. 以“祖父节点”为支点进行右旋。

13.4 删除

​ 与n 个结点的红黑树上的其他基本操作一样，删除一个结点要花费 $O(lgn)$ 时间。从一棵红黑树中删除结点的过程是基于TREE-DELETE 过程，首先设计一个供TREE-DELETE 调用的子过程TRANSPLANT。

​ 程RB-DELETE 与TREE-DELETE 类似，只是多了几行伪代码。多出的几行代码记录结点y 的踪迹， y 有可能导致红黑性质的破坏。

• 当想要删除结点z, 且此时z 的子结点少于 2 个时，z 从树中删除，并让 y 成为之。
• 当z有两个子结点时， y应该是z的后继，并且y将移至树中的z位置。在结点被移除或者在树中移动之前，必须记住y的颜色，并且记录结点x 的踪迹，将x移至树中y 的原来位置，因为结点x 也可能引起红黑性质的破坏。

​ 删除结点z 之后， RB-DELETE 调用一个辅助过程 RB-DELETE-FIXUP, 该过程通过改变颜色和执行旋转来恢复红黑性质。

子树删除交换程序

RB-TRANSPLANT(T, u, v)
 // u 为ROOT节点
 if u.p == T.nil
   T.root = v
 else if u == u.p.left
   u.p.left = v
 else 
   u.p.right = v
 v.p = u.p

删除修复程序：

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                // 条件1：x的兄弟节点是红色。(此时x的父节点和x的兄弟节点的子节点都是黑节点)。                           
        w.color = BLACK                // case 1 (01) 将x的兄弟节点设为“黑色”。
        x.p.color = RED                // case 1 (02) 将x的父节点设为“红色”。
        LEFT-ROTATE(T, x.p)            // case 1 (03) 对x的父节点进行左旋。
        w = x.p.right                  // case 1 (04) 左旋后，重新设置x的兄弟节点。
       // 上面执行后：x的兄弟节点是黑色。
       if w.left.color == BLACK 
           and w.right.color == BLACK // 条件2：x的兄弟节点的两个孩子都是黑色。
         w.color = RED                // case 2 (01) 将x的兄弟节点设为“红色”。
         X = x.p                      // case 2 (02) 设置“x的父节点”为“新的x节点”。
       else if w.right.color == BLACK    // 条件3：x的兄弟节点的左孩子是红色，右孩子是黑色的。
           w.left.color = BLACK       // case 3 (01) 将x兄弟节点的左孩子设为“黑色”。
           w.color = RED              // case 3 (02) 将x兄弟节点设为“红色”。
           RIGHT-ROTATE(T,w)          // case 3 (03) 对x的兄弟节点进行右旋。
           w = x.p.right              // case 3 (04) 右旋后，重新设置x的兄弟节点。
           // 上面执行后刚好符合条件4：x的兄弟节点的右孩子是红色的。
           w.color = x.p.color        // case 4 (01) 将x父节点颜色 赋值给 x的兄弟节点。
           x.p.color = BLACK          // case 4 (02) 将x父节点设为“黑色”。
           w.right.color = BLACK      // case 4 (03) 将x兄弟节点的右子节设为“黑色”。
           LEFT-ROTATE(T, x.p)        // case 4 (04) 对x的父节点进行左旋。
           x = T.root                 // case 4 (05) 设置“x”为“根节点”。
    els // same as then clause with "right" and "left" exchanged    
    ...
x.color = BLACK

删除程序：

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)
  else if 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
      // 将y交换交换到 z.right
      RB-TRANSPLANT(T, y, y.right)
      y.right = z.right
      y.right.p = y
    // 删除 z
    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)

​ 如果结点y 是黑色的，则会产生三个问题，可以通过调用RB-DELETE-FIXUP 进行补救。

1. 如果y 是原来的根结点，而y 的一个红色的孩子成为新的根结点，这就违反了性质2 。
2. 如果x 和x.p 是红色的，则违反了性质4。
3. 在树中移动y 将导致先前包含y 的任何简单路径上黑结点个数少1 。因此，y 的任何祖先都不满足性质5。

算法分析

​ 因为含n 个结点的红黑树的高度为$O(lgn)$, 不调用RB-DELETE-FIXUP 时该过程的总时间代价为$O(lgn)$ 。在RB-DELETE-FIXUP 中，情况1 、3 和4在各执行常数次数的颜色改变和至多3 次旋转后便终止。情况2 是while 循环可以重复执行的唯一情况，然后指针x 沿树上升至多O(lgn) 次，且不执行任何旋转。所以，过程RB-DELETEFIXUP 要花费$O(lgn)$时间，做至多3 次旋转，因此RB-DELETE 运行的总时间为$O(lgn)$。

{collapse}
{collapse-item label=“删除结点z后性质被破坏的情况” }

当前节点为x，且当前点是父节点的左孩子

case 1：x的兄弟结点w 是红色的(此时x的父节点和x的兄弟节点的子节点都是黑节点)。

处理方法：

1. 将x的兄弟节点设为“黑色”。
2. 将x的父节点设为“红色”。
3. 对x的父节点进行左旋。
4. 左旋后，重新设置x的兄弟节点。

case 2：x的兄弟节点是黑色，x的兄弟节点的两个孩子都是黑色。

处理方法：

1. 将x的兄弟节点设为“红色”。
2. 设置“x的父节点”为“新的x节点”。

case 3：x的兄弟节点是黑色，x的兄弟节点的左孩子是红色，右孩子是黑色的。

处理方法：

1. 将x兄弟节点的左孩子设为“黑色”。
2. 将x兄弟节点设为“红色”。
3. 对x的兄弟节点进行右旋。
4. 右旋后，重新设置x的兄弟节点。

case 4：x的兄弟节点是黑色，x的兄弟节点的右孩子是红色的。

处理方法：

1. 将x父节点颜色 赋值给 x的兄弟节点。
2. 将x父节点设为“黑色”。
3. 将x兄弟节点的右子节设为“黑色”。
4. 对x的父节点进行左旋。
5. 设置“x”为“根节点”。

import java.util.LinkedList;
import java.util.Queue;

public class RedBlackTreeParent {

    public static enum Color {
        RED,
        BLACK;

        public boolean isRed() {
            return this.equals(RED);
        }

        public boolean isBlack() {
            return this.equals(BLACK);
        }
    }

    public static class TreeNode {
        public int val;
        public Color color;
        public TreeNode parent;
        public TreeNode left;
        public TreeNode right;

        TreeNode(int x) {
            val = x;
        }

        TreeNode(int val, Color color, TreeNode nil) {
            this.val = val;
            this.color = color;
            this.parent = nil;
            this.left = nil;
            this.right = nil;
        }
    }

    private TreeNode root;
    private TreeNode nil;

    public RedBlackTreeParent() {
        nil = new TreeNode(0, Color.BLACK, null);
        root = nil;
    }

    private void leftRotate(TreeNode x) {
        TreeNode y = x.right;
        x.right = y.left;
        if (y.left != nil) {
            y.left.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == nil) {
            root = y;
        } else if (x.parent.left == x) {
            x.parent.left = y;
        } else {
            x.parent.right = y;
        }

        y.left = x;
        x.parent = y;
    }

    private void rightRotate(TreeNode y) {
        TreeNode x = y.left;
        y.left = x.right;
        if (x.right != nil) {
            x.right.parent = y;
        }
        x.parent = y.parent;
        if (y.parent == nil) {
            root = x;
        } else if (y.parent.left == y) {
            y.parent.left = x;
        } else {
            y.parent.right = x;
        }

        x.right = y;
        y.parent = x;
    }

    private void insertFixup(TreeNode node) {
        while (node.parent.color.isRed()) {
            if (node.parent.parent.left == node.parent) {
                TreeNode uncle = node.parent.parent.right;
                if (uncle.color.isRed()) {
                    uncle.color = Color.BLACK;
                    node.parent.color = Color.BLACK;
                    node.parent.parent.color = Color.RED;
                    node = node.parent.parent;
                } else if (node == node.parent.left) {
                    node.parent.color = Color.BLACK;
                    node.parent.parent.color = Color.RED;
                    rightRotate(node.parent.parent);
                } else {
                    node = node.parent;
                    leftRotate(node);
                }
            } else {
                TreeNode uncle = node.parent.parent.left;
                if (uncle.color.isRed()) {
                    uncle.color = Color.BLACK;
                    node.parent.color = Color.BLACK;
                    node.parent.parent.color = Color.RED;
                    node = node.parent.parent;
                } else if (node == node.parent.left) {
                    node.parent.color = Color.BLACK;
                    node.parent.parent.color = Color.RED;
                    rightRotate(node.parent.parent);
                } else {
                    node = node.parent;
                    leftRotate(node);
                }
            }
        }
        this.root.color = Color.BLACK;
    }

    public void insert(int val) {
        TreeNode node = new TreeNode(val, Color.RED, nil);

        // 查询替换数据
        TreeNode pre = nil, p = root;
        while (p != nil) {
            pre = p;
            if (val < p.val) {
                p = p.left;
            } else {
                p = p.right;
            }
        }

        node.parent = pre;
        if (pre == nil) {
            this.root = node;
        } else if (val < pre.val) {
            pre.left = node;
        } else {
            pre.right = node;
        }
        // 修复红黑树
        insertFixup(node);
    }

    private void transplant(TreeNode n1, TreeNode n2) {
        if(n1.parent == nil){
            this.root = n2;
        }else if(n1 == n1.parent.left){
            n1.parent.left = n2;
        }else{
            n1.parent.right = n2;
        }
        n2.parent = n1.parent;
    }

    private TreeNode search(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }

        if (val < root.val) {
            return search(root.left, val);
        } else {
            return search(root.right, val);
        }
    }

    public TreeNode search(int val) {
        return search(this.root, val);
    }

    private void deleteFilup(TreeNode node) {
        while(node != root && node.color.isBlack()){
            if(node.parent.left == node){
                TreeNode brother = node.parent.right;
                if(brother.color.isRed()){
                    brother.color = Color.BLACK;
                    node.parent.color = Color.RED;
                    leftRotate(node.parent);
                    brother = node.parent.right;
                }

                if (brother.left.color.isBlack() && brother.right.color.isBlack()){
                    brother.color = Color.RED;
                    node = node.parent;
                }else if(brother.right.color.isBlack()){
                    brother.left.color = Color.BLACK;
                    brother.color = Color.RED;
                    rightRotate(brother);
                    brother = node.parent.right;

                    // 继续执行 情况四
                    brother.color = node.parent.color;
                    node.parent.color = Color.BLACK;
                    brother.right.color = Color.BLACK;
                    leftRotate(node.parent);
                    node = this.root;
                }
            }else{
                TreeNode brother = node.parent.left;
                if(brother.color.isRed()){
                    brother.color = Color.BLACK;
                    node.parent.color = Color.RED;
                    leftRotate(node.parent);
                    brother = node.parent.left;
                }

                if (brother.left.color.isBlack() && brother.right.color.isBlack()){
                    brother.color = Color.RED;
                    node = node.parent;
                }else if(brother.right.color.isBlack()){
                    brother.left.color = Color.BLACK;
                    brother.color = Color.RED;
                    rightRotate(brother);
                    brother = node.parent.left;

                    // 继续执行 情况四
                    brother.color = node.parent.color;
                    node.parent.color = Color.BLACK;
                    brother.right.color = Color.BLACK;
                    leftRotate(node.parent);
                    node = this.root;
                }
            }
        }

        node.color = Color.BLACK;
    }

    private void delete(TreeNode node){
        if(node == null) return;
        TreeNode saveNode = node, fixNode;
        Color saveColor = saveNode.color;
        if(node.left == nil){
            fixNode = node.right;
            transplant(node, node.right);
        }else if(node.right == nil){
            fixNode = node.left;
            transplant(node, node.left);
        }else{
            saveNode = node.right;
            while(saveNode.left != nil){
                saveNode = saveNode.left;
            }
            saveColor = saveNode.color;
            fixNode = saveNode.right;
            if (saveNode.parent == node){
                fixNode.parent = saveNode;
            }else{
                transplant(saveNode, saveNode.right);
                saveNode.right = node.right;
                saveNode.right.parent = saveNode;
            }
            // 删除 node
            transplant(node, saveNode);
            saveNode.left = node.left;
            saveNode.left.parent = saveNode;
            saveNode.left.color = node.color;
        }

        if (saveColor.isBlack()){
            deleteFilup(fixNode);
        }
    }

    public void delete(int val){
        TreeNode node = search(this.root, val);
        delete(node);
    }


    private void printOrder(TreeNode root) {
        if (root == nil) {
            return;
        }
        printOrder(root.left);
        System.out.print(root.val + ":" + root.color.name() + ", ");
        printOrder(root.right);
    }

    
    public void printOrder() {
        printOrder(root);
        System.out.println();
    }

    public void printLayer() {
        Queue<TreeNode> 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++) {
                TreeNode node = queue.poll();
                if (node == nil) {
                    System.out.print("null:BLACK, ");
                } else {
                    System.out.print(node.val + ":" + node.color.name() + ", ");
                    queue.offer(node.left);
                    queue.offer(node.right);
                    if (node.left != nil || node.right != nil) {
                        isDo = true;
                    }
                }
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        RedBlackTreeParent tree = new RedBlackTreeParent();
        tree.insert(10);
        tree.insert(8);
        tree.insert(4);
        tree.insert(13);
        tree.insert(2);
        tree.insert(6);
        tree.insert(1);
        tree.insert(3);
        tree.insert(5);
        tree.insert(7);
        tree.insert(9);
        tree.insert(12);
        tree.printOrder();
        tree.delete(7);
        tree.printLayer();
    }
}

第十四章 数据结构的扩张

​ 通过扩张红黑树构造出的两种数据结构。

14.1 动态顺序统计

​ 顺序统计树(order-statistic tree) T 只是简单地在每个结点上存储附加信息的一棵红黑树。在红黑树的结点x 中，除了通常属性x.key 、x.color 、x.p 、x.left 和x.right 之外，还包括另一个属性 x.size。这个属性包含了以x为根的子树（包括x 本身）的（内）结点数，即这棵子树的大小。如果定义哨兵的大小为 0, 也就是设置 T.nil.size 为o, 则有等式：$x.size = x.left.size + x.right.size + 1$

​ 通过定义一个元素的秩为在中序遍历树时输出的位置，来消除原顺序统计树定义的不确定性。

查找具有给定秩的元素

​ 对具有给定秩的元素的检索。过程 OS-SELECT(x, i) 返回一个指针，其指向以x 为根的子树中包含第i 小关键字的结点。为找出顺序统计树T 中的第 i 小关键字，我们调用过程 OS-SELECT(T.root, i)。

​ 因为每次递归调用都在顺序统计树中下降一层， OS-SELECT 的总时间最差与树的高度成正比。又因为该树是一棵红黑树，其高度为$O(lgn) $, 其中n 为数的结点数。所以，对千n 个元素的动态集合， OS-SELECT 的运行时间为$O(lgn) $。

OS-SELECT(x, i)
  r = x.left.size + 1
  if i == r
    return x
  else if i < r
    return OS-SELECT(x.left, i)
  else
    return OS-SELECT(x.right, i - r)

确定一个元素的秩

​ 给定指向顺序统计树T 中结点x 的指针，过程 OS-RANK 返回对T 中序遍历对应的线性序中x 的位置。

​ 因为while 循环的每次迭代耗费0(1) 时间，且y 在每次迭代中沿树上升一层，所以最坏情况下OS-RANK 的运行时间与树的高度成正比：在n 个结点的顺序统计树上为 $O(lgn) $ 。

OS-RANK(T,x)
 r = x.left.size + 1
 y = X
 while y != T.root
   if y == y.p.right
     r = r + y.p.left.size + 1
   y = y.p
 return r

对子树规模的维护

红黑树上的插入操作包括两个阶段。

• 第一阶段从根开始沿树下降，将新结点插入作为某个已有结点的孩子。在这阶段中为了维护子树的规模，对由根至叶子的路径上遍历的每一个结点x, 都增加x.size 属性。新增加结点的size 为1 。由于一条遍历的路径上共有 $O(lgn)$ 个结点，故维护size 属性的额外代价为 $O(lgn)$ 。
• 第二阶段沿树上升，做一些变色和旋转操作来保持红黑树性质。在这阶段，对红黑树结构上的改变仅仅是由旋转所致，旋转次数至多为2 。此外，旋转是一种局部操作：它仅会使两个结点的size 属性失效，而围绕旋转操作的链就是与这两个结点关联。因为在红黑树的插入过程中至多进行两次旋转，所以在第二阶段更新size 属性只需要O(1)的额外时间。\

​ 对一棵有n 个结点的顺序统计树插入元素所需要的总时间为 $O(lgn)$ , 从渐近意义上看，这与一般的红黑树是一样的。

向左旋转：

LEIT-ROTATE(T, x)
  y = x.right			// set y
  x.right = y.left		// turn y's left subtree into x's right subtree
  if y.left != T.nil
    y.left.p = x
  y.p = x.p				// link x's parent toy
  if x.p == T.nil
    T.root = y
  else if x == x.p.left
    x.p.left = y
  else 
    x.p.right = y
  y.left = x			// put x on y's left
  x.p = y
  // 维护新属性
  y.size = x.size
  x.size = x.left.size + x.right.size + 1

向右旋转：

RIGHT-ROTATE(T, y)
  x = y.left
  y.left = x.right
  if x.right != T.nil
    x.right.p = y
  x.p = y.p
  if y.p == T.nil
    T.root = x
  else if y == y.p.left
    y.p.left = x
  else 
    y.p.right = x
  x.right = y
  y.p = x
  // 维护新属性
  x.size = y.size
  y.size = y.left.size + y.right.size + 1

红黑树上的删除操作也包括两个阶段：

• 第一阶段对搜索树进行操作。在这阶段中，要么将结点y 从树中删除，要么将它在树中上移。为了更新子树的规模，我们只需要遍历一条由结点y( 从它在树中的原始位置开始）至根的简单路径，并减少路径上每个结点的size 属性的值。因为在n 个结点的红黑树中，这样一条路径的长度为 $O(lgn)$, 所以第一阶段维护size 属性所耗费的额外时间为 $O(lgn)$。
• 第二阶段做至多三次旋转，其他对结构没有任何影响。在这阶段中，采用与插入相同的方式来处理删除操作中的 $O(1) $ 次旋转。所以对有n 个结点的顺序统计树进行插入与删除操作，包括维护size 属性，都只需要 $O(lgn)$ 的时间。

​ 对有n 个结点的顺序统计树进行插入与删除操作，包括维护size 属性，都只需要 $O(lgn)$ 的时间。

RB-DELETE(T, z)
  y = z
  y-original-color = y.color
  
  if z.left == T.nil or z.right == T.nil
    t = y  // 维护新属性
    while t != T.nil
      t.size = t.size - 1
      t = t.p
  
  if z.left == T.nil
    x = z.right
    RB-TRANSPLANT(T, z, z.right)
  else if z.right == T.nil
    x = z.left
    RB-TRANSPLANT(T, z, z.left)
  else 
    y = TREE-MINIMUM(z.right)  //右子树最小值
    
    t = y  // 维护新属性
    while t != T.nil
      t.size = t.size - 1
      t = t.p
    
    y-original-color = y.color
    x = y.right
    if y.p == z // ？
      x.p = y
    else
      // 将y交换交换到 z.right
      RB-TRANSPLANT(T, y, y.right)
      y.right = z.right
      y.right.p = y
    // 删除 z
    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)

14.2 如何扩张数据结构

扩张一种数据结构可以分为4 个步骤：

1. 选择一种基础数据结构。
2. 确定基础数据结构中要维护的附加信息。
3. 检验基础数据结构上的基本修改操作能否维护附加信息。
4. 设计一些新操作。

​ 对于步骤1，选择红黑树作为基础数据结构。红黑树是一种合适的选择，这源千它能有效地支持一些基千全序的动态集合操作，如MINIMUM 、MAXIMUM 、SUCCESSOR 和PREDECESSOR。

​ 对于步骤2，添加了size 属性，在每个结点x 中的size 属性存储了以x 为根的子树的大小。一般地，附加信息可使得各种操作更加有效。例如，我们本可以仅用树中存储的关键字来实现 OS-SELECT 和 OS-RANK, 但它们却不能在$O(lgn)$ 运行时间内完成。有时候，附加信息是指针类信息，而不是具体的数据。

​ 对于步骤3，我们保证了插入和删除操作仍能在 $O(lgn)$ 时间内维护size 属性。比较理想的是，只需要更新该数据结构中的几个元素就可以维护附加信息。例如，如果把每个结点的秩存储在树中，那么 OS-SELECT 和 OS-RANK 能够较快运行，但是当插入一个新的最小元素时，会导致树中每个结点的秩发生变化。如果我们存储的是子树的大小，则插入一个新的元素时仅会使 $O(lgn)$ 个结点的信息发生改变。

​ 对于步骤4，我们设计了新操作 OS-SELECT 和 OS-RANK。归根结底，一开始考虑去扩张一个数据结构的原因就是为了满足新操作的需要。然而有时并不是为了设计一些新操作，而是利用附加信息来加速已有的操作。

14.3 区间树

​ 区间树(interval tree) 是一种对动态集合进行维护的红黑树，其中每个元素x 都包含一个区间 x.int 。区间树支持下列操作：

​ INTERVAL-INSERT(T, x): 将包含区间属性$int$的元素x 插入到区间树T中。
​ INTERVAL-DELETE(T, x): 从区间树T中删除元素x 。
​ INTERVAL-SEARCH(T, i): 返回一个指向区间树T中元素x的指针，使$x.int$与i 重叠；若此元素不存在，则返回$T.nil$ 。

分析区间树以及区间树上各种操作的设计

步骤1: 基础数据结构

​ 我们选择这样一棵红黑树，其每个结点x 包含一个区间属性 $x.int$, 且x 的关键字为区间的低端点 $x.int.low$。因此，该数据结构按中序遍历列出的就是按低端点的次序排列的各区间。

步骤2: 附加信息

​ 每个结点x 中除了自身区间信息之外，还包含一个值 $x.max$, 它是以x 为根的子树中所有区间的端点的最大值。

步骤3: 对信息的维护

​ 我们必须验证n 个结点的区间树上的插入和删除操作能否在 $O(lgn)$ 时间内完成。通过给定区间 $x.int$ 和结点x 的子结点的max 值，可以确定 $x.max$ 值：$x.max = max(x.int.high, x.left.max, x.right.max)$ ，插人和删除操作的运行时间为 $O(lgn)$ 。事实上，在一次旋转后，更新max 属性只需 $O(1)$ 的时间。

步骤4: 设计新的操作

​ 这里我们仅需要唯一的一个新操作 INTERVAL-SEARCH(T, i), 它是用来找出树T 中与区间t 重叠的那个结点。若树中与 $i$ 重叠的结点不存在，则下面过程返回指向哨兵 $T.nil$ 的指针。

INTERVAL-SEARCH(T, i)
  x = T.root
  while x != T.nil and i does not overlap x.int 
//while x != T.nil and (x.high < i.low or i.high < x.low)
    if x.left != T.nil and x.left.max >= i.low
      x = x.left
    else 
      x = x.right
  return x

​ 查找与 t 重叠的区间x 的过程从以 x 为根的树根开始，逐步向下搜索。当找到一个重叠区间或者x 指向T. nil 时过程结束。由于基本循环的每次迭代耗费 $O(1)$ 的时间，又因为n 个结点的红黑树的高度为 $O(lgn)$ , 所以INTERVAL-SEARCH 过程耗费 $O(lgn)$ 的时间。