# 树

树是一种非线性表数据结构，包含一系列存在父子关系的节点。

除了顶部的第一个节点，每个节点都有一个父节点以及零个或多个子节点。

下面解释一些术语：

节点：树中的每个元素都叫作节点；
- 根节点：树顶部的节点叫作根节点，它没有父节点。
- 内部节点：至少有一个子节点的节点称为内部节点；
- 外部节点（叶节点）：没有子元素的节点称为外部节点或叶节点；
子树：子树由节点和它的后代构成。例如，节点 13、12 和 14 构成了上图中树的一棵子树；
深度：节点的深度取决于它的祖先节点的数量。例如，节点 8 有 3 个祖先节点（9、7 和 11），它的深度为 3；
高度：树的高度取决于所有节点深度的最大值；
层：根节点在第 0 层，它的子节点在第 1 层，以此类推。

# 二叉树

二叉树，每个节点最多有两个两个子节点，分别是左子节点和右子节点。

『 满二叉树 』叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点。如上图编号 2 所示。

『 完全二叉树 』叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大。如上图编号 3 所示。

# 储存二叉树

想要存储一棵二叉树，我们有两种方法：

一种是基于「指针」的二叉链式存储法。
一种是基于「数组」的顺序存储法。

# 二叉链式存储法

每个节点有三个属性，其中一个存储数据，另外两个是指向左右子节点的指针。我们只要拎住根节点，就可以通过左右子节点的指针，把整棵树都串起来。这种存储方式我们比较常用。

# 顺序存储法

在数组中，如果节点 $X$ 存储在数组中下标为 $i$ 的位置，下标为 $2 * i$ 的位置存储的就是左子节点，下标为 $2 * i + 1$ 的位置存储的就是右子节点。

反过来，下标为 $i/2$ 的位置存储就是它的父节点。

上面的例子是一棵「完全二叉树」，所以仅仅“浪费”了一个下标为 0 的存储位置。如果是「非完全二叉树」，其实会浪费比较多的数组存储空间。

所以，如果某棵二叉树是一棵完全二叉树，那用数组存储是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针。

同样，这也是为什么完全二叉树要求最后一层的子节点都靠左的原因。

# 二叉树的遍历

如何将所有节点都遍历打印出来呢？经典的方法有三种，前序遍历、中序遍历和后序遍历。其中，前、中、后序，表示的是节点与它的左右节点遍历打印的先后顺序：

前序遍历：对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树；
中序遍历：对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树；
后序遍历：对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身；

二叉树的前、中、后序遍历就是一个递归的过程。下面是它们各自的实现代码：


void preOrder(Node* root) {
  if (root == null) return;
  System.out.print(root->value);
  preOrder(root->left);
  preOrder(root->right);
}

void inOrder(Node* root) {
  if (root == null) return;
  inOrder(root->left);
  System.out.print(root->value);
  inOrder(root->right);
}

void postOrder(Node* root) {
  if (root == null) return;
  postOrder(root->left);
  postOrder(root->right);
  System.out.print(root->value);
}

从前、中、后序遍历的顺序图，可以看出来，每个节点最多会被访问两次，所以遍历操作的时间复杂度，跟节点的个数 n 成正比，也就是说二叉树遍历的时间复杂度是 $O(n)$ 。

# 二叉查找树

『 二叉查找树 Binary Search Tree 』最大的特点就是，支持动态数据集合的快速插入、删除、查找操作。

二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

可以发现，中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度是 $O(n)$ ，非常高效。因此，二叉查找树也叫作二叉排序树。

# 二叉查找树的查找操作

在二叉查找树中查找一个节点。我们先取根节点，如果它等于我们要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。

public class BinarySearchTree {
  private Node tree;

  public Node find(int data) {
    Node p = tree;
    while (p != null) {
      if (data < p.data) p = p.left;
      else if (data > p.data) p = p.right;
      else return p;
    }
    return null;
  }

  public static class Node {
    private int data;
    private Node left;
    private Node right;

    public Node(int data) {
      this.data = data;
    }
  }
}

# 二叉查找树的插入操作

新插入的数据一般都是在叶子节点上，所以我们只需要从根节点开始，依次比较要插入的数据和节点的大小关系。

如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。

public void insert(int data) {
  if (tree == null) {
    tree = new Node(data);
    return;
  }

  Node p = tree;
  while (p != null) {
    if (data > p.data) {
      if (p.right == null) {
        p.right = new Node(data);
        return;
      }
      p = p.right;
    } else { // data < p.data
      if (p.left == null) {
        p.left = new Node(data);
        return;
      }
      p = p.left;
    }
  }
}

# 二叉查找树的删除操作

针对要删除节点的子节点个数的不同，我们需要分三种情况来处理。

如果要删除的节点没有子节点，我们只需要直接将父节点中，指向要删除节点的指针置为 null；
如果要删除的节点只有一个子节点（只有左子节点或者右子节点），我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了；
如果要删除的节点有两个子节点。我们需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点；


public void delete(int data) {
  // p 指向要删除的节点，初始化指向根节点
  Node p = tree;
  // pp 记录的是 p 的父节点
  Node pp = null;
  while (p != null && p.data != data) {
    pp = p;
    if (data > p.data) p = p.right;
    else p = p.left;
  }
  // 没有找到
  if (p == null) return;

  // 要删除的节点有两个子节点
  if (p.left != null && p.right != null) { // 查找右子树中最小节点
    Node minP = p.right;
    // minPP表示minP的父节点
    Node minPP = p;
    while (minP.left != null) {
      minPP = minP;
      minP = minP.left;
    }
    // 将minP的数据替换到p中
    p.data = minP.data;
    // 下面就变成了删除minP了
    p = minP;
    pp = minPP;
  }

  // 删除节点是叶子节点或者仅有一个子节点
  Node child; // p的子节点
  if (p.left != null) child = p.left;
  else if (p.right != null) child = p.right;
  else child = null;

  // 删除的是根节点
  if (pp == null) tree = child;
  else if (pp.left == p) pp.left = child;
  else pp.right = child;
}

除此之外，关于二叉查找树的删除操作，还有个非常简单、取巧的方法，就是单纯将要删除的节点标记为“已删除”，但是并不真正从树中将这个节点去掉。这样原本删除的节点还需要存储在内存中，比较浪费内存空间，但是删除操作就变得简单了很多。

# 支持重复数据的二叉查找树

如果遇到了碰到一个节点的值，与要插入数据的值相同，我们就将这个要插入的数据放到这个节点的右子树，也就是说，把这个新插入的数据当作大于这个节点的值来处理。

当要查找数据的时候，遇到值相同的节点，我们并不停止查找操作，而是继续在右子树中查找，直到遇到叶子节点，才停止。这样就可以把键值等于要查找值的所有节点都找出来。

对于删除操作，我们也需要先查找到每个要删除的节点，然后再按前面讲的删除操作的方法，依次删除。

# 二叉查找树的时间复杂度分析

二叉查找树的形态各式各样。比如这个图中，对于同一组数据，我们构造了三种二叉查找树。它们的查找、插入、删除操作的执行效率都是不一样的。

图中第一种二叉查找树，根节点的左右子树极度不平衡，已经退化成了链表，所以查找的时间复杂度就变成了 $O(n)$ 。

最理想的情况下，二叉查找树是一棵完全二叉树（或满二叉树）。这个时候不管操作是插入、删除还是查找，时间复杂度其实都跟树的高度成正比，也就是 $O(height)$ 。

现在问题就变成了，如何求一棵包含 n 个节点的完全二叉树的高度？从树的图中可以看出，包含 n 个节点的满二叉树中，第一层包含 1 个节点，第二层包含 2 个节点，第三层包含 4 个节点，依次类推，下面一层节点个数是上一层的 2 倍，第 K 层包含的节点个数就是 $2^{(K-1)}$ 。

对于完全二叉树来说，最后一层的节点个数在 1 个到 $2^{(K-1)}$ 个之间（我们假设最大层数是 L）。如果我们把每一层的节点个数加起来就是总的节点个数 n。也就是说，如果节点的个数是 n，那么 n 满足这样一个关系：

$n >= 1+2+4+8+...+2^{(L-2)}+1$ $n <= 1+2+4+8+...+2^{(L-2)}+2^{(L-1)}$

借助等比数列的求和公式，我们可以计算出，L 的范围是 $[log_2(n+1), log_2n +1]$ 。完全二叉树的层数小于等于 $log_2n +1$ ，也就是说，完全二叉树的高度小于等于 $log_2n$ 。

# 二叉查找树 vs 散列表

二叉查找树最大的特点就是，支持动态数据集合的快速插入、删除、查找操作。之前说过，散列表也是支持这些操作的，并且散列表的这些操作比二叉查找树更高效，时间复杂度是 $O(1)$ 。既然有了这么高效的散列表，使用二叉树的地方是不是都可以替换成散列表呢？有没有哪些地方是散列表做不了，必须要用二叉树来做的呢？

散列表的插入、删除、查找操作的时间复杂度可以做到常量级的 $O(1)$ 。
二叉查找树在比较平衡的情况下，插入、删除、查找操作时间复杂度是 $O(logn)$

之所以有些地方不去用散列表，而是用二叉查找树，原因主要有如下几点：

散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在 $O(n)$ 的时间复杂度内，输出有序的数据序列；
散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 $O(logn)$ ；
尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比 $logn$ 小。所以实际的查找速度可能不一定比 $O(logn)$ 快；
散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定；

# 平衡查找树

『 平衡查找树 Balance Search Tree 』的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于 1。从这个定义来看，上一节我们讲的完全二叉树、满二叉树其实都是平衡二叉树，但是非完全二叉树也有可能是平衡二叉树。

前面说，二叉查找树在频繁的动态更新过程中，可能会出现树的高度远大于 $log_2n$ 的情况，从而导致各个操作的效率下降。极端情况下，二叉树会退化为链表，时间复杂度会退化到 $O(n)$ 。

发明平衡二叉查找树这类数据结构的初衷是，解决普通二叉查找树在频繁的插入、删除等动态更新的情况下，始终保持二叉树的平衡 ( 任意一个节点的左右子树的高度相差不能大于 1 ) ，防止时间复杂度退化。

# AVL 树

AVL 树是最早被发明的自平衡二叉查找树。名称来源于其发明者姓氏的缩写 ( Adelson-Velskii 和 Landis )。

在 AVL 树中，任一节点对应的两棵子树的最大高度差为 1
增加和删除元素时，通过四种旋转操作来实现树的重新平衡 ( 左旋，右旋，左右旋，右左旋 )

一个结点的『 平衡因子 Balance Factor 』是它的左子树的高度减去它的右子树的高度，可能的值为 0 1 或 -1

高度：节点的所有后代节点深度的最大值。
深度：节点的祖先节点的数量。

当有增加或删除元素操作时，AVL 树始终要保持每个结点的平衡因子绝对值，小于等于 1，大于等于 0。

2020-08-15-22-27-50

在开始讲之前，先定义一下 AVL 树中的结点 Node 类：

class Node
{
    int key, height;
    Node left, right;

    Node(int d)
    {
        key = d;
        height = 1;
    }
}

在定义一下，获得「平衡因子」的方法：

// Get Balance factor of node N
int getBalance(Node N)
{
    if (N == null)
        return 0;
    return height(N.left) - height(N.right);
}

# AVL 树的自平衡

根据「子树形态」的不同，选择不同的平衡操作：

# 右右子树 - 左旋

B 节点和 A 节点进行所谓 “父子交换”。如果 B 有左子树，则将其作为 A 的右子树。

2020-08-15-22-52-34 2020-08-15-22-49-02

// A utility function to left rotate subtree rooted with x
// See the diagram given above.
Node leftRotate(Node x)
{
    Node y = x.right;
    Node T2 = y.left;

    // Perform rotation
    y.left = x;
    x.right = T2;

    // Update heights
    x.height = max(height(x.left), height(x.right)) + 1;
    y.height = max(height(y.left), height(y.right)) + 1;

    // Return new root
    return y;
}

# 左左子树 - 右旋

B 节点和 C 节点进行所谓 “父子交换”。如果 B 有右子树，则将其作为 C 的左子树。

2020-08-15-22-52-55 2020-08-15-22-49-16

// A utility function to right rotate subtree rooted with y
// See the diagram given above.
Node rightRotate(Node y)
{
    Node x = y.left;
    Node T2 = x.right;

    // Perform rotation
    x.right = y;
    y.left = T2;

    // Update heights
    y.height = max(height(y.left), height(y.right)) + 1;
    x.height = max(height(x.left), height(x.right)) + 1;

    // Return new root
    return x;
}

左右子树 - 左右旋：先进行左旋，然后进行右旋。

2020-08-15-22-50-40 2020-08-15-22-53-42

右左子树 - 右左旋：先进行右旋，然后进行左旋。

2020-08-15-22-55-23 2020-08-15-22-55-43

下图总体的展示了各种旋转操作的使用情况：

2020-08-15-23-02-52

# AVL 树插入

Node insert(Node node, int key)
{
    /* 1. Perform the normal BST rotation */
    if (node == null)
        return (new Node(key));

    if (key < node.key)
        node.left = insert(node.left, key);
    else if (key > node.key)
        node.right = insert(node.right, key);
    else // Equal keys not allowed
        return node;

    /* 2. Update height of this ancestor node */
    node.height = 1 + max(height(node.left),
                        height(node.right));

    /* 3. Get the balance factor of this ancestor
    node to check whether this node became
    Wunbalanced */
    int balance = getBalance(node);

    // If this node becomes unbalanced, then
    // there are 4 cases Left Left Case
    if (balance > 1 && key < node.left.key)
        return rightRotate(node);

    // Right Right Case
    if (balance < -1 && key > node.right.key)
        return leftRotate(node);

    // Left Right Case
    if (balance > 1 && key > node.left.key)
    {
        node.left = leftRotate(node.left);
        return rightRotate(node);
    }

    // Right Left Case
    if (balance < -1 && key < node.right.key)
    {
        node.right = rightRotate(node.right);
        return leftRotate(node);
    }

    /* return the (unchanged) node pointer */
    return node;
}

# AVL 树删除

Node deleteNode(Node root, int key)
{
    // STEP 1: PERFORM STANDARD BST DELETE
    if (root == null)
        return root;

    // If the key to be deleted is smaller than
    // the root's key, then it lies in left subtree
    if (key < root.key)
        root.left = deleteNode(root.left, key);

    // If the key to be deleted is greater than the
    // root's key, then it lies in right subtree
    else if (key > root.key)
        root.right = deleteNode(root.right, key);

    // if key is same as root's key, then this is the node
    // to be deleted
    else
    {
        // node with only one child or no child
        if ((root.left == null) || (root.right == null))
        {
            Node temp = null;
            if (temp == root.left)
                temp = root.right;
            else
                temp = root.left;

            // No child case
            if (temp == null)
            {
                temp = root;
                root = null;
            }
            else // One child case
                root = temp; // Copy the contents of
                            // the non-empty child
        }
        else
        {

            // node with two children: Get the inorder
            // successor (smallest in the right subtree)
            Node temp = minValueNode(root.right);

            // Copy the inorder successor's data to this node
            root.key = temp.key;

            // Delete the inorder successor
            root.right = deleteNode(root.right, temp.key);
        }
    }

    // If the tree had only one node then return
    if (root == null)
        return root;

    // STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
    root.height = max(height(root.left), height(root.right)) + 1;

    // STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to check whether
    // this node became unbalanced)
    int balance = getBalance(root);

    // If this node becomes unbalanced, then there are 4 cases
    // Left Left Case
    if (balance > 1 && getBalance(root.left) >= 0)
        return rightRotate(root);

    // Left Right Case
    if (balance > 1 && getBalance(root.left) < 0)
    {
        root.left = leftRotate(root.left);
        return rightRotate(root);
    }

    // Right Right Case
    if (balance < -1 && getBalance(root.right) <= 0)
        return leftRotate(root);

    // Right Left Case
    if (balance < -1 && getBalance(root.right) > 0)
    {
        root.right = rightRotate(root.right);
        return leftRotate(root);
    }

    return root;
}

# 红黑树

# 红黑树定义

『 红黑树 Red–black Tree 』是一种不严格的平衡二叉查找树。前面说 “平衡查找树” 中任意一个节点的左右子树的高度相差不能大于 1。我们可以不严格遵守这条规则。

也就是让整棵树左右看起来 “比较平衡”，不要出现左子树很高、右子树很矮的情况。只要树的高度不比 $log_2n$ 大很多（比如树的高度仍然是对数量级的），那么性能就依旧还不错。

红黑树中的节点，一类被标记为黑色，一类被标记为红色。一棵红黑树需要满足这样几个要求：

根节点是黑色的；
每个叶子节点都是黑色的空节点（NIL）。也就是说，叶子节点不存储数据；
任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
从任一节点到达其叶子节点的所有路径，都包含相同数目的黑色节点；

# 红黑树自平衡

前面定义中说：

任何相邻的节点都不能同时为红色；
从任一节点到达其叶子节点的所有路径，都包含相同数目的黑色节点；

在红黑树插入，删除节点的过程中，这两条可能会被破坏。这被称为，破坏红黑树的平衡。

红黑树的自平衡，就是为了把红黑树的平衡调整过来。

自平衡有三种操作：

左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点。右子结点的左子结点变为旋转结点的右子结点。旋转结点左子结点保持不变；
右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点。左子结点的右子结点变为旋转结点的左子结点。旋转结点右子结点保持不变；
变色：结点的颜色由红变黑或由黑变红；

# 红黑树查找

因为红黑树是一颗二叉平衡树，并且查找不会破坏树的平衡，所以查找跟二叉平衡树的查找无异。

步骤：

从根结点开始查找，把根结点设置为当前结点；
若当前结点为空，返回 null；
若当前结点不为空，用当前结点的 key 跟查找 key 作比较；
若当前结点 key 等于查找 key，那么该 key 就是查找目标，返回当前结点；
若当前结点 key 大于查找 key，把当前结点的左子结点设置为当前结点，重复步骤 2；
若当前结点 key 小于查找 key，把当前结点的右子结点设置为当前结点，重复步骤 2；

# 红黑树插入

红黑树规定，插入的节点必须是红色的。而且，二叉查找树中新插入的节点都是放在叶子节点上。

在讲插入之前，为了简化描述，我们先定义几个名字：

我们把正在处理的节点叫作关注节点。关注节点会随着不停地迭代处理，而不断发生变化。最开始的关注节点就是新插入的节点；
把父节点的兄弟节点叫作叔叔节点，父节点的父节点叫作祖父节点；

插入操作包括两部分：

查找插入的位置；
插入节点后如不满足红黑树性质还需要进行自平衡；

具体可以分为如下几种情况：

# 场景 1：红黑树为空树

直接把插入节点作为根节点，并把节点设置为黑色；

# 场景 2：插入节点的 key 已存在

如果插入结点的 key 在树中已存在，既然红黑树总保持平衡，在插入前红黑树已经是平衡的，那么把插入结点设置为将要替代结点的颜色，再把结点的值更新就完成插入。

# 场景 3：插入节点的父节点为黑节点

如果插入节点的父节点是黑色的，那我们什么都不用做，它仍然满足红黑树的定义。

# 场景 4：插入节点的父节点为红节点

如果插入的父结点为红结点，那么该父结点不可能为根结点，所以插入结点总是存在祖父结点。这点很重要，因为后续的旋转操作肯定需要祖父结点的参与。

这种情景下，还会分为如下几种情况：

情况 1：叔叔结点存在并且为红结点

将关注节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑色；
将关注节点 a 的祖父节点 c 的颜色设置成红色；
如果祖父节点 c 的父节点黑色，那么无需再做任何处理；
如果祖父节点 c 的父结点是红色，此时红黑树已不平衡了，所以还需要让把 c 当作新的插入结点，关注节点变成 c，继续做插入操作自平衡处理，直到平衡为止；

情况 2：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的左子结点

如果叔叔结点为黑结点，而父结点为红结点，那么叔叔结点所在的子树的黑色结点就比父结点所在子树的多了。

只要一边子树的结点多了或少了，我们就需要进行旋转，来把节点借给另一边。

这种情况下还可以分为两种情况：

1. 插入结点是其父结点的左子结点

围绕关注节点 a 的祖父节点 c 右旋；
将关注节点 a 的父节点 b、兄弟节点 c 的颜色互换。

2. 插入结点是其父结点的右子结点

关注节点变成节点 a 的父节点 b；
围绕新的关注节点 b 左旋；
旋转完就变成完毕后，就变成 “插入结点是其父结点的左子结点”；
然后依照上一个情形的步骤，去做自平衡；

情况 3：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的右子结点

这种情况下还可以分为两种情况：

1. 插入结点是其父结点的右子结点

对 PP 进行左旋；
将 P 设为黑色；
将 PP 设为红色；

2. 插入结点是其父结点的右子结点

对 P 进行右旋；
把 P 设置为插入结点，得到上一个情形 “插入结点是其父结点的右子结点”；
然后依照上一个情形的步骤，去做自平衡；

# 红黑树删除

删除操作的平衡调整分为两步：

针对删除节点初步调整。让树满足定义，每个节点从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；
针对关注节点进行二次调整。让树满足定义，不存在相邻的两个红色节点；

# 针对删除节点初步调整

注意：

经过初步调整之后，为了保证满足红黑树定义 “只包含红色节点和黑色节点”。有些节点会被标记成两种颜色，“红 - 黑” 或者 “黑 - 黑”。如果一个节点被标记为了 “黑 - 黑”，那在计算黑色节点个数的时候，要算成两个黑色节点。

在下面的图中，如果一个节点既可以是红色，也可以是黑色，就会用一半红色一半黑色来表示。如果一个节点是 “红 - 黑” 或者 “黑 - 黑”，就在左上角用一个小黑点来表示额外的黑色。

情况 1：如果要删除的节点是 a，它只有一个子节点 b

删除节点 a，并且把节点 b 替换到节点 a 的位置，这一部分操作跟普通的二叉查找树的删除操作一样；
节点 a 只能是黑色，节点 b 也只能是红色，其他情况均不符合红黑树的定义；这种情况下，我们把节点 b 改为黑色；
调整结束，不需要进行二次调整；

情况 2：如果要删除的节点 a 有两个非空子节点，并且节点 a 的后继节点是 a 的右子节点 c

后继节点

大于删除结点的最小结点

如果节点 a 的后继节点就是右子节点 c，那右子节点 c 肯定没有左子树。我们把节点 a 删除，并且将节点 c 替换到节点 a 的位置。这一部分操作跟普通的二叉查找树的删除操作无异；
然后把节点 c 的颜色设置为跟节点 a 相同的颜色；
如果节点 c 是黑色，为了不违反红黑树的最后一条定义，我们给节点 c 的右子节点 d 多加一个黑色，这个时候节点 d 就成了 “红 - 黑” 或者 “黑 - 黑”；
这个时候，关注节点变成了节点 d。第二步的调整操作就会针对关注节点来做；

情况 3：如果要删除的是节点 a，它有两个非空子节点，并且节点 a 的后继节点不是 a 的右子节点

找到后继节点 d，并将它删除，删除后继节点 d 的过程参照 “情况 1”；
将节点 a 替换成后继节点 d；
把节点 d 的颜色设置为跟节点 a 相同的颜色；
如果节点 d 是黑色，为了不违反红黑树的最后一条定义，我们给节点 d 的右子节点 c 多加一个黑色，这个时候节点 c 就成了 “红 - 黑” 或者 “黑 - 黑”；
这个时候，关注节点变了节点 c，第二步的调整操作就会针对关注节点来做；

# 针对关注节点进行二次调整

二次调整是为了让红黑树中不存在相邻的红色节点。

经过初步调整之后，关注节点变成了 “红 - 黑” 或者 “黑 - 黑” 节点。针对这个关注节点，可以分四种情况来进行二次调整：

情况 1：如果关注节点是 a，它的兄弟节点 c 是红色的

情况 2：如果关注节点是 a，它的兄弟节点 c 是黑色的，并且节点 c 的左右子节点 d、e 都是黑色的情况 3：如果关注节点是 a，它的兄弟节点 c 是黑色，c 的左子节点 d 是红色，c 的右子节点 e 是黑色情况 4：如果关注节点 a 的兄弟节点 c 是黑色的，并且 c 的右子节点是红色的

# 树