红黑树（Red-Black Tree，RBT）_红黑树的结论

作者：Monodyee | 2024-06-06 19:56:48

踩

红黑树的结论

1.红黑树

强烈推荐！！算法交互式网站： Red/Black Tree
在insert左侧框输入要插入的数字，然后点击insert就会按红黑树规则进行插入

1.1 什么是红黑树？

红黑树是一种平衡二叉查找树的变体，它的左右子树高差有可能大于 1，所以红黑树不是严格意义上的平衡二叉树（AVL），但对之进行平衡的代价较低，其平均统计性能要强于 AVL 【引用自红黑树】

笔记来源于：什么是红黑树，据说红黑树很难理解，看动画5分钟就弄明白原理

1.2 为什么要引入红黑树？

二叉排序树（BST）、平衡二叉树（AVL）、红黑树（RBT）均用于查找数据元素

平衡二叉树（AVL）为严格平衡的（左子树高度 - 右子树高度 $\leq$ 1）
红黑树（RBT）为非严格平衡（红黑树中从根到叶结点的最长路径 $\leq$ 最短路径的2倍，即左右子树高度最多差2倍）

BST $\rightarrow$ AVL $\rightarrow$ RBT
从 BST 到 AVL 引入平衡，将二叉排序树的树高缩小，提高了查找效率
从 AVL 到 RBT 引入颜色，解决插入/删除频繁调整AVL的问题

这三个树对应三个操作的时间复杂度如下表【此表引自王道考研计算机数据结构全程班】

由上表看出平衡二叉树和红黑树的三个操作时间复杂度完全一样，但我们为什么要引入红黑树？
原因在于：平衡二叉树中当插入/删除一个元素时，我们要判断是否在插入/删除元素后，平衡二叉树不再平衡，即平衡因子不满足要求（左子树高度 $-$ 右子树高度 $= - 1 / 1 / 0$ ），如果不满足平衡要求，我们需要对不平衡的二叉树进行调整，这个调整的过程时间开销很大。尤其在插入多个元素时，要频繁的调整树的状态。由此引出红黑树，红黑树在插入/删除后，不会破坏“红黑”特性，无需频繁调整树的状态。即便需要调整，其时间消耗也在常数级别

平衡二叉树的适用情况：以查为主，很少进行插入或删除
红黑树的适用情况：频繁进行插入或删除

1.3 红黑树的性质

笔记来源于：什么是红黑树，据说红黑树很难理解，看动画5分钟就弄明白原理

红黑树（RBT）首先是一颗二叉排序树（BST），即满足左子树结点值 $\lt$ 根结点的值 $\lt$ 右子树结点值

性质一：根结点是黑色的、叶结点是不存储数据的黑色空结点
注意：这里的叶结点是方形（查找失败的结点），注意与其他树的叶结点进行区别！！

性质二：任何相邻的两个结点不能同时为红色
即红结点的父结点和孩子结点均为黑色
注意：这种相邻是路径上的相邻，兄弟不属于相邻！！

性质三：任意结点到其可到达的叶结点各条路径上经过相同数量的黑色结点
例如：下图结点a到左子树叶结点之间包含2个黑色结点，结点a到右子树叶结点之间也包含2个黑色结点

当从根到任一叶结点的简单路径最短时，这条路径必然全由黑结点构成

黑高：从某结点出发（不含该结点）到达叶结点的任一简单路径上黑结点总数称为该结点的黑高（记为bh）

1.4 红黑树的结论

结论1：红黑树中从根到叶结点的最长路径 $\leq$ 最短路径的2倍
例如：下图一条路径长度为3，另一条路径长度为2， $\lt 2×2=4$

结论2：有n个内部结点（圆结点）的红黑树的高度 $\leq 2\log_2(n+1)$

结论2证明：从根结点到叶结点（不含叶结点）的任何一条简单路径上都至少有一半是黑结点，所以根的黑高至少为 $h / 2$ ，于是有 $\geq 2^{h/2}-1$ （树的结点总个数）
$\geq 2^{h/2}-1\\ ~\\ n+1 \geq 2^{h/2}\\ ~\\ \log_2(n+1) \geq \frac{h}{2}\\ ~\\ h \leq 2\log_2(n+1)$