红黑树的引入

一、有了二叉树，为什么还需要平衡二叉树？

1. 二叉树容易退化成一条链，也就是出现左斜树、右斜树的情况；

2. 当出现斜树的时候，查询时间复杂度由O(log2N)增长至O(N)；

3. 引入左右子树高度差绝对值不能大于1的平衡二叉树，可以保证在最坏的情况下，查询时间复杂度为O(log2N)；

4. 平衡的定义，是说从空链接到根节点的距离相等，也就是说非叶子节点是不会出现空链接的；

二、有了平衡二叉树，为什么还需要红黑树？

1. 平衡二叉树左右子树的高度差绝对值不能大于1，每次进行插入删除操作时，几乎都需要通过旋转来保持平衡；

2. 频繁地插入删除操作，频繁地旋转，平衡二叉树的性能大打折扣；

3. 红黑树通过牺牲严格的平衡，换取插入、删除时的旋转操作，整体性能优于平衡二叉树；

   3.1 红黑树插入时的不平衡，通过不超过2次旋转就能解决；

   3.2 红黑树删除时的不平衡，通过不超过3次旋转就能解决；

4. 红黑树的红黑规则，保证在最坏的情况下，也能在O(log2N)时间内完成查找工作；

红黑树是什么？有哪些特点和应用？

一、红黑树是一种自平衡的二叉查找树。

红黑树

二、红黑规则是什么呢？

1. 根节点是黑色；

2. 节点不是黑色就是红色；

3. 叶子节点为黑色，末梢的空节点nill，也就是null;

4. 一个节点为红色，必须有两个子节点为黑色；

5. 每个节点到叶子节点的所有路径，都含有相同数量的黑色节点，也就是说有相同的黑色高度；

三、红黑的优点有哪些？

1. 红黑规则4、5保证了红黑树的大致平衡；从根到叶子的所有路径中，最长路径不会超过最短路径的2倍；

2. 红黑树在最坏的情况下，依旧能满足在O(log2N)时间内完成查找工作；

   例：当黑色高度为3时，最长路径为4：黑色-》红色-》黑色-》红色-》黑色；最短路径为2：黑色-》黑色-》黑色，不算叶子节点nil；

3. 在Java实现中，NULL代表空节点；

4. 新插入的节点为红色，因为父节点为黑色的概率最大；

四、红黑树的应用有哪些？

1. 在java中，TreeMap、TreeSet都是用红黑树作为底层数据结构；

2. JDK1.8以及后面的版本，HashMap也使用红黑树作为底层数据结构；

3. 多路复用技术的Epoll，其核心结构是红黑树 + 双向链表；

4. Linux底层的CFS进程调度算法中，vruntime使用红黑树进行存储。

参考文档：

https://blog.csdn.net/u014454538/article/details/120120216

https://www.zhihu.com/question/312327402

https://blog.csdn.net/cy973071263/article/details/122543826