前言
二叉查找树是最常用的一种二叉树，它支持快速查找、插入、删除操作。性能与树的高度成正比，理想情况下，时间复杂为是O(logn)。
不过频繁的更新，二叉树的高度会远大于log2n，极端情况会退化成链表，时间复杂度变为O(n)。
因此需要设计一种平衡二叉查找树的结构，今天讲的红黑树就是平衡二叉查找树的其中一种。
什么是平衡二叉查找树
平衡二叉树，严格定义，二叉树中任意一个节点的左右子树的高度相差不能大于1。 而平衡二叉查找树，除了有平衡二叉树的特点，还要满足二叉查找树的特点。
平衡二叉查找树 vs 非平衡二叉查找树
常见的平衡二叉查找树有AVL树、Splay Tree（伸展树）、Treap（树堆）、红黑树等。
其实上很多平衡二叉查找树都没有严格按照上面的定义。我们在学习的时候也不用死抠定义，要学会从这个数据结构的由来去理解“平衡”。发明平衡二叉查找树的目的是为了解决二叉查找树因为动态更新引起的时间复杂度退化的问题。
平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。
什么是红黑树
红黑树的英文是“Red-Black Tree”，简称R-B Tree。红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑 树还需要满足这样几个要求：
- 根节点是黑色的；
- 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
- 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
- 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；
为了更好理解红黑树的定义，看看下面的例子：
红黑树
为什么说红黑树“近似平衡”
“平衡”的意思可以等价为性能不退化。“近似平衡”就等价为性能不会退化的太严重。
二叉查找树很多操作的性能与树的高度成正比，一颗极其平衡的二叉树的高度是log2n。
因此要证明红黑树“近似平衡”，只要推导红黑树的高度近似log2n即可。
分两种情况推导：
去掉红色节点
image
根据定义中的一条：从任意节点到可达的叶子节点的每个路径包含相同数目的黑色节点。仅包含黑色节点的四叉树的高度，比包含相同节点个数的完全二叉树的高度还要小。所以去掉红色节点的“黑树”的高度也不会超过log2n。
加入红色节点
根据定义中的一条：在红黑树中，红色节点不能相邻，也就是说，有一个红色节点就要至少有一个黑色节点，将它跟其他红色节点隔开。因此加入红色节点之后，最长路径不会超过2log2n，也就是说，红黑 树的高度近似2log2n。
所以，红黑树的高度只比高度平衡的AVL树的高度（log2n）仅仅大了一倍，在性能上，下降得并不多。
为什么在工程中喜欢用红黑树，而非其他平衡二叉查找树
因为红黑树是一种性能非常稳定的二叉查找树，所以，在工程中，但凡是用到动态插入、删 除、查找数据的场景，都可以用到它。不过，它实现起来比较复杂，如果自己写代码实现， 难度会有些高，这个时候，我们其实更倾向用跳表来替代它。
网友评论