二叉树的时间复杂度在理想状况下是 O(logn) 但是在频繁的动态更新下可能就退化成 O(n) 或者接近 O(n) 了,这个问题不解决,二叉树的性能就太差了,由此便引出了平衡二叉树。

平衡二叉树的严格定义是二叉树中任意一个节点的左右子树的高度相差不能大于一。这里注意,这里说的定义是平衡二叉树而不是平衡二叉查找树。由这个定义来看,完全二叉树和满二叉树都是平衡二叉树。

平衡二叉查找树不仅要满足平衡二叉树的定义,还要满足二叉查找树的特点。但是工程上常用的像红黑树并不是严格满足左子树右子树高度相差一,因为只要左右子树高度相差的不多,就不会出现很严重的性能下降问题,同时如果硬要为了满足左右子树高度相差一,就要不断的做平衡,而平衡操作是非常的费时的,这反而可能造成性能下降。

由此引出了红黑树,红黑树便是在平衡操作和由树高相差过多引起性能下降做出权衡出现的平衡产物。

1 红黑树

红黑树中的节点,一类被标记为黑色,一类被标记为红色,除此以外,一棵红黑树还要满足如下几个要求:

  1. 根节点是黑色的
  2. 每个叶子结点都是黑色的空节点,也就是说,叶子结点不存储数据
  3. 任何相邻的节点都不能同时为红色,也就是说红色节点是被黑色节点隔开的
  4. 每个节点,从该节点到达其可达叶子结点的所有路径,都包含相数目的黑色节点

注:这里面的每个叶子节点都是黑色的空节点这个条件是为了简化代码实现设置的。

如下是一个红黑树的样例

红黑树样例

1.2 红黑树树高的分析

由于影响树的性能主要的原因在于树的高度,所以这里我们分析红黑树的高度。

对于一棵红黑树而言,我们去掉红黑树中的红色节点,那么子节点直接将祖父节点作为新的父节点,那么之前的二叉树就可能出现三叉树和四叉树。由于完全二叉树的树高为 \(log_{2}n\),所以这颗去掉红色节点的树节点少于 n,所以它的高度也小于 \(log_{2}n\),那么加上红色节点之后,它的高度可以估算为 \(2log_{2}n\),仅比高度平衡的树的时间复杂度多了一倍,性能下降并不严重,而且实际使用的效果比这个好。下图是去掉红色节点的树的演示图

去掉红色节点的红黑树

1.3 为什么要用红黑树

红黑树是一种平衡二叉查找树,它解决了普通二叉查找树在数据更新的过程中时间复杂度退化的问题,并且它的高度接近 O(logn),所以它的插入、删除、查找操作的时间复杂度都是 O(logn)。由于性能问题,所以工程中比较常用。