红黑树简介

纯爱战神弗耶戈

一、概念
红黑树是一种自平衡二叉查找树（二叉排序树）。与平衡二叉树（avl树）不同的是，红黑树是弱平衡二叉树，即它的左右子树高度差有可能大于1，但不超过一倍。

二、5大性质
每个节点要么是黑色, 要么是红色。
根节点是黑色。
每个叶节点(Nil，空值)都是黑色。
每个红色节点的两个子节点一定都是黑色。（但黑色节点的子节点可以也是黑色）
任意一个节点到每个叶子节点的路径都包含相同数量的黑节点。
总结：根黑叶黑，红不相邻，黑色平衡。

三、推论（或规律）
左子树和右子树的黑节点的层数是相等的。因此我们称红黑树的这种平衡为黑色完美平衡。（由性质5推出）
如果一个节点存在黑子节点，那么该节点肯定有两个子节点。（由性质5推出）
任意节点到每个叶子节点最长路径不会超过最短路径的2倍。（由性质4、5推出）
任意节点到每个叶子节点的路径都有相同的黑节点个数。
树的高度不超过2log(n+1)。
四、红黑树的操作及其时间复杂度
时间复杂度：查询、插入和删除均为O（logn）。

关于红黑树的操作大家可以自己去在线演示网站试试：
中文版：https://rbtree.phpisfuture.com/
英文版：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

PS：英文版网站还有各种数据结构的在线演示哦：
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

口诀：叔红要变色，叔黑要左右；右子要左旋，左旋自己来；左子要右旋，右旋父亲去。

1、查询操作
2、变色操作
也就是把节点涂成黑色或红色。

3、插入操作
插入的新节点一定是红色，也就是“红插”，后续将根据平衡性变色。

同时由于是红插，插入操作只会破坏第4个性质，也就是“红不相邻”的性质；调整时才会破坏第2或第5个性质。

若插入新节点后依然满足红黑树定义，则插入结束
若插入新节点后不满足红黑树定义（非根节点只需要看是不是红相邻了，如果是根节点，涂黑即可），需要调整，看叔叔节点：
叔叔节点是黑色
LL型：右单旋，父换爷+变色
RR型：左单旋，父换爷+变色
LR型：左右双旋，儿换爷+变色
RL型：右左双旋，儿换爷+变色
叔叔节点是红色
叔父爷全部变色，爷变新节点，再来一轮调整
4、删除操作
5、红黑树的建立
当插入节点的父亲节点为null，则将该节点颜色置为黑色。
当插入节点的父亲节点为黑色，不需要调整。
当插入节点的父亲节点为红色，其叔叔节点亦为红色，则将其父亲节点和叔叔节点置为黑色，同时将祖父节点置为红色，将祖父节点设置为当前新增节点，重新按照从规则1开始判断。
当插入节点的父亲节点为红色，其叔叔节点为黑色或null，则需要分多种情况考虑。
a. 新增节点为父亲节点右孩子，同时父亲节点是祖父节点的左孩子，则进行左旋，将父亲节点置为新节点，重新按照规则1进行判断；
b. 新增节点为父亲节点左孩子，同时父亲节点是祖父节点的右孩子，则进行右旋，将父亲节点置为新节点，重新按照规则1进行判断；
不满足上述所有条件，将父亲节点置为黑色，同时，将祖父节点置为红色，进行以下两种情况判断。
a. 新增节点为父亲节点左孩子，同时父亲节点是祖父孩子的左孩子，则对祖父节点进行右旋
b. 其他情况，对祖父节点左旋。
五、与平衡二叉树（avl树）的联系和差别
联系
都是自平衡二叉树
查找、插入和删除的平均时间复杂度相同（log ⁡ 2 n \log_2nlog 2n）
高度都趋近于log ⁡ 2 n \log_2nlog 2n

差别
平衡二叉树都可以经过变色操作成为红黑树，但红黑树不一定是平衡二叉树。
平衡二叉树是严格平衡二叉树，红黑树是弱平衡二叉树。
红黑树的自平衡操作一定会在3次旋转之内解决，而平衡二叉树往往要比红黑树多。
因为平衡二叉树更平衡，查找效率往往要高于红黑树；但插入和删除效率往往低于红黑树。
实际应用中，若搜索次数远远大于插入和删除次数，那么选择平衡二叉树；否则，选择红黑树。
平衡二叉树的插入/删除操作很容易破坏“平衡”特性，需要频繁调整；红黑树的插入/删除操作相对不容易破坏“平衡”特性，不需要频繁调整。
六、应用
广泛用于C++的STL中，map和set都是用红黑树实现的。
著名的linux进程调度Completely Fair Scheduler，用红黑树管理进程控制块，进程的虚拟内存区域都存储在一颗红黑树上，每个虚拟地址区域都对应红黑树的一个节点,左指针指向相邻的地址虚拟存储区域，右指针指向相邻的高地址虚拟地址空间。
IO多路复用epoll的实现采用红黑树组织管理sockfd，以支持快速的增删改查。
ngnix中，用红黑树管理timer，因为红黑树是有序的，可以很快的得到距离当前最小的定时器。
java中TreeMap的实现。