JAVA面试八股文——红黑树

红黑树规则：
1、节点不是黑色，就是红色（非黑即红）
2、根节点为黑色
3、叶节点为黑色（叶节点是指末梢的空节点 Nil或Null）
4、一个节点为红色，则其两个子节点必须是黑色的（根到叶子的所有路径，不可能存在两个连续的红色节点）
5、每个节点到叶子节点的所有路径，都包含相同数目的黑色节点（相同的黑色高度）
规则说明：
1、约束4和5，保证了红黑树的大致平衡：根到叶子的所有路径中，最长路径不会超过最短路径的2倍。
2、使得红黑树在最坏的情况下，也能有 O ( l o g 2 N ) O(log_2N) O(log2N)的查找效率
3、关于叶子节点：Java实现中，null代表空节点，无法看到黑色的空节点，反而能看到传统的红色叶子节点
4、默认新插入的节点为红色：因为父节点为黑色的概率较大，插入新节点为红色，可以避免颜色冲突
红黑树的应用：
1、Java中，TreeMap、TreeSet都使用红黑树作为底层数据结构
2、JDK 1.8开始，HashMap也引入了红黑树：当冲突的链表长度超过8时，自动转为红黑树
3、Linux底层的CFS进程调度算法中，vruntime使用红黑树进行存储。
4、多路复用技术的Epoll，其核心结构是红黑树 + 双向链表。
更多技术分享，请持续关注云和数据！