数据结构与算法-基础(2)

12、数据结构与算法 - 基础：红黑树（1）概述

摘要

红黑树是数据结构中重要的一种结构，其本质是通过定义一些性质，让二叉树分布结构变的相对合理，并在动态添加或者删除的过程中去修复结构。红黑树在搜索、添加、删除这 3 种操作的效率相对比较均衡，所以有很多实际的应用场景。

红黑树是一种自平衡的二叉搜索树，是一种重要的数据结构，后面的集合、映射等数据结构，都可以从这基础上去搭建。同时也是内容和逻辑比较多的数据结构，需要多花费一些精力去学习它。

红黑树有 5 条性质，凡是满足这 5 条，才能称为红黑树，这 5 条性质有：

1、节点必须是RED或者BLACK，也可以理解为存在一个Boolean的标志，不是false就是ture；
2、根节点是BLACK；
3、叶子节点都是BLACK，这里要特别留意，叶子节点存在两个空节点，只有一个子树的节点，另外一个不存在的子树也是一个空节点；
4、 RED节点的子节点都是BLACK，RED节点的父节点也都是BLACK保证**从根节点到叶子节点的所有路径上，不会出现2个连续的RED节点；
5、从任意一个节点到叶子节点的所有路径上包含的BLACK节点数量相同；

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eLaOobUI-1640349225584)(https://cdn.jsdelivr.net/gh/shPisces/writing_pic/img/RBT-image1.png)]

注意：如上图的红黑树，必须是要有 null（空节点）节点。后面的示例图中省略，节省作图时间，但一定要有。

为什么满足这 5 条性质，就能保证平衡呢？

先来温习一个平衡的标准，参照 AVL 树中的定义，节点的左右子树的高度差要不大于 1，即是平衡的。

红黑树在满足上面的 5 条性质之后，第 5 条性质中说明 BLACK 节点数量相关也就可以推断出节点的左右子树高度差是不大于 1 的（考虑到空节点，所以有可能是 1）。

红黑树与 4 阶 B 树

看红黑树中，黑色节点和它的左右子节点合并就变成 4 阶 B 树。红黑树的黑色节点和 4 阶 B 树的节点数量也是一样多的。一般情况都是这样，还有其他的特殊情况。如下图：

辅助准备

在开始红黑树之前，先定义一些属性和函数，帮助实现红黑树的代码。

先要给节点（下面统称 node）添加一些判断与其他 node 的关系函数。

parent：父节点，在 node 的结构中已经定义父节点的属性
sibling：兄弟节点，若 node 是 parent 的 left，兄弟节点就是 parent 的 right

public Node<E> sibling() {
     
       
  if (isLeftChild()) {
     
       
    return parent.right;
  }
  if (isRightChild()) {
     
       
    return parent.left;
  }
  return null;
}

uncle：叔父节点，就是 parent 的兄弟节点。
grand：祖父节点，就是 parent 的父节点

写下来，先实现一些处理红黑树节点的函数（比如看节点的颜色等）。在这之前，需要提前全局定义两个值，用 Boolean 值来定义RED 和 BLACK。

private static final boolean RED = false;
private static final boolean BLACK = true;

染色，把 node 上色：

private Node<E> color(Node<E> node, boolean color) {
     
       
  if (node == null) return node;
  ((RBNode<E>)node).color = color;
  return node;
}

染成红色：

private Node<E> red(Node<E> node) {
     
       
  return color(node, RED);
}

染成黑色：

private Node<E> black(Node<E> node) {
     
       
  return color(node, BLACK);
}

获取 node 的颜色：

private boolean colorOf(Node<E> node) {
     
       
  return node == null ? BLACK : ((RBNode<E>)node).color;
}

是否是红色：

private boolean isRed(Node<E> node) {
     
       
  return colorOf(node) == RED;
}

是否是黑色：

private boolean isBlack(Node<E> node) {
     
       
  return colorOf(node) == BLACK;
}

添加和删除

红黑树的添加和删除和 AVL 树的添加和删除的原则大致一样，即添加元素都是添加称为叶子节点，删除元素的时候就要区分删除的是叶子节点还是非叶子节点。

在添加或者删除元素之后，要判断当前树是否依然符合红黑树的 5 条性质，若不符合就要做恢复为红黑树的操作。这就是红黑树的重点，内容很多，后面文章专门分析添加和删除处理。

AVL 树和红黑树

AVL 树的平衡标准比较严格，即一个节点的左右子树的高度差不能超过 1，搜索、添加和删除操作都是 O(logn)，添加元素只需要 O(1) 次旋转，删除元素最多需要 O(logn) 次旋转。

红黑树是比较宽松的，没有一条路径的节点数量会大于其他路径节点数量的 2 倍。搜索、添加和删除操作都是 O(logn)，添加或者删除元素都只需要 O(1) 次的旋转。

因为AVL 树的平衡标准比红黑树要高，所以在搜索方面，AVL 树的效率也是比红黑树大。但是在添加或者删除后需要旋转的次数比红黑树要多。这就可以总结出搜索次数远远大于插入和删除时，选择 AVL 树；搜索、插入、删除的次数都差不多，可以选择红黑树。

在实际应用中，选择更多的是红黑树，因为应用红黑树统计的平均性能要比 AVL 好一些。