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 好一些。