这里再来复习一下二叉树的概念：
1. 每个节点下子元素不可超过两个，必须是0个或者一个或则两个
2. 二叉树是一种有序树。
理解了这些，我们这节要学习的内容就是有关于二叉查找树以及有关红黑树。
## 二叉查找树
从这个名字，可以简单理解一下，他是为了解决什么被发明出来的。当然是查找了。因为名字自带查找。哈哈 开个玩笑。其实就是为了方便查找
*特征：**左边**子元素的值一定 <= 根节点*
*特征：**右边**子元素的值一定 >= 根节点*
这就是一个典型的二叉查找树，比如我们查找一个`2`的元素位置
- 从根节点出发。5比2大，向着左节点4
- 4比2大，向着左节点
- 到达2的位置。
二叉查找树使用二分法的思想，将元素的位置唯一指定出来。查找最大次数=二叉树高度。
### 二叉查找树缺陷
这么nice的二分法查找树，也不是没有缺陷的，世界上没有任何一个完美的东西。
所以，它的缺陷就是：如果我们的元素全部都是小于根节点的，那就变成这样的一个东西了。
这样，若是查找一个关于`7` 的元素，那么直接乱套了。直接和线性的数组就没有区别了。还是需要一个个遍历。
为了解决这种缺陷，下面这个东西出现了！
## 红黑树
红黑树，是一种自我平衡的二叉查找树，说白了就是比二叉查找树更加Plus
HashMap 再JDK 8当中。若链表长度超过8，则转换为红黑树。这也是一种特别好用的数据结构。所以说。`很重要`
### 特点
1. 节点要么是红色/黑色（名字中自带的属性）
2. 根节点是黑色的。
3. 叶子节点是`黑色的空节点`
4. 每个红色节点下面都有两个黑色节点
5. 从任意节点到每个叶子节点路径都都包含相同数目的黑色节点
### 插入一个新值
在插入一个新值的时候，可能会使红黑树违反上面的5条规则，这个时候需要进行变色和旋转，我们逐一来讲解。
假设向当前红黑树插入一个 `21` 节点。
21比22小，所以只能放到22左边的位置。这里问题也就来了：
- 为啥这个节点必须是`红色`的 而不能是黑色？
> 叶子节点必须是黑色空节点，所以，红色节点下必须有两个黑色节点，所以该节点必须是红色。
当然，又往上面看的话，你就会发现：22 是红色节点，红色节点必须包含两个黑色节点？ 这又冲突了。怎么办？
## 节点的变色
这里尝试将22 节点变为黑色。这样的话，下面的规则满足了。但是从17号元素出发。到叶子节点。左边的线路有三个黑色节点，左边只有两个。
> 从任意节点到每个叶子节点路径都都包含相同数目的黑色节点
为了规则的完整性，继续变色。将25号元素变成红色
这时候还没有结束，因为
> 每个红色节点下面都有两个黑色节点
这样才算完全符合规则规范。
## 节点的旋转方法
### 左旋转
这里理解起来会很吃力。我先画个图。来理解这里面涉及到的内容。
1. 父节点被自己的右边孩子取代。
2. 而原来的父节点则需要成为被取代位置的左节点。
**最简单的方式是将子节点的左节点断开，挂到父节点上，翻转一下位置即可。**
1. 断开子节点的左边节点。
2. 将断开的这个节点挂到父节点上。
3. 旋转位置
很好理解吧！
### 右旋转 顺时针旋转
1. 断开子节点的右孩子。
2. 挂到父节点上
3. 旋转位置。
**往那边旋转，就断开自己的那边的孩子，然后挂到父级，将节点变换一下位置即可。**
## 小结
其实红黑树的内容了解这么多就可以了。也没必要必须钻牛角尖。只需要懂得红黑树这种自平衡的主体思想即可。
## 参考
https://mp.weixin.qq.com/s/jz1ajDUygZ7sXLQFHyfjWA
