存在问题：树可以认为是介于数组和链表二者之间的一种数据结构，拥有较快的查询速度同时拥有较快的插入和删除速度。但是在树出现极端或严重的不平衡情况下会导致效率低下

基于红黑树折中解决二叉树不平衡带来的效率低下问题

1.3.1 红黑树

• 红黑树，Red-Black Tree [RBT]是一个自平衡（不是绝对平衡）的二叉查找树（BST）,树上的每个节点需要遵循下面的规则

• 每个节点要么是黑色，要么是红色

• 根节点为黑色

• 每个叶子节点(NIL)是黑色

• 不能存在两个连续的红色节点（红色节点的两个子节点必须是黑色）

• 任一节点到叶子节点的路径包含相同数量的黑节点

红黑树通过什么自平衡

• 左旋：以某个节点作为支点（旋转节点），其右子节点变为旋转节点的父节点，右子节点的左节点变为旋转节点的右子节点，左子节点保持不变

• 
  
  

• 右旋：以某个节点作为支点（旋转节点），其左子节点变为旋转节点的父节点，左子节点的右子节点变为旋转节点的左子节点，右子节点保持不变

• 变色：节点的颜色由红色变为黑色或者黑色变为红色

红黑树插入场景

1、红黑树为空

? 1.1 插入节点作为根节点并把节点设置为黑色

2、插入节点的父节点为黑节点\

? 2.1 直接插入

3、插入节点的父节点为红节点

? 3.1 叔叔节点存在且为红节点

? 1、P 节点和 S 节点设置为黑色

? 2、PP 节点设置为红色

? 3、PP 设置为当前插入节点

? 4、再次重复上述步骤

? 3.2 叔叔节点不存在或者叔叔节点为黑色

? 3.2.1 P 节点是 PP 节点的左节点

? 3.2.1.1 插入节点是 P 节点的左节点

? 1、P 设置为黑色

? 2、PP 节点设置为红色

? 3、PP 节点右旋

? 3.2.1.2 插入节点是 P 节点的右节点

? 1、P 节点左旋

? 2、把 P 设置为插入节点（此时等于上面的场景）

? 3、PP 节点右旋

? 3.2.2 P 节点是 PP 节点的右节点

? 3.2.2.1 插入节点是 P 节点的右节点

? 1、P 节点设置为黑色

? 2、PP 节点设置为红色

? 3、PP 节点左旋

最后

按照上面的过程，4 个月的时间刚刚好。当然 Java 的体系是很庞大的，还有很多更高级的技能需要掌握，但不要着急，这些完全可以放到以后工作中边用别学。

学习编程就是一个由混沌到有序的过程，所以你在学习过程中，如果一时碰到理解不了的知识点，大可不必沮丧，更不要气馁，这都是正常的不能再正常的事情了，不过是“人同此心，心同此理”的暂时而已。

“道路是曲折的，前途是光明的！”

更多Java核心笔记、真实面经、学习笔记等知识干货可以点击这里免费领取