image
ZERO
持续更新 请关注：https://zorkelvll.cn/blogs/zorkelvll/articles/2019/01/17/1547726391242
一、背景
不管是在阅读jdk源码的过程中，还是数据结构的课程学习过程中，亦或是在程序员的面试过程中，红黑树问题都是十分常见的考察数据结构功底的一个典型问题，因此决定一探究竟！
二、二叉查找树BST
1、定义
- 左子树上所有结点的值均小于等于它的根结点的值
- 右子树上所有结点的值均大于等于它的根结点的值
- 左右子树也分别为二叉排序树
通俗地理解，所谓的二叉查找树，就是“左边小于等于根，右边大于等于根”这样一种树构造逻辑不断递归出来的一种树结构
imagepng
2、优势
- 在查找时，则刚好是一种对二分查找思想的应用；查找所需的最大次数等同于二叉查找树的高度
- 插入结点时，也是类似于查找时的二分查找思想，通过一层层比较大小，最终找到新节点适合插入的位置
3、劣势
但是，主要是在插入新节点的时候：假设是按照待插入的序列本身是有序的如“9，8，7，6，5”且根结点值为10,那么该二叉查找树就会变成左子树大幅不断延长，几乎就是变成了线性的了
即，二叉查找树，随着多次插入新节点而出现了不平衡
==>>重点来了，，，然后就是身为主角的“红黑树”上场了；理所当然，红黑树就是一种自平衡的二叉查找树
三、红黑树Red Black Tree
1、定义
- 首先红黑树是一个二叉查找树，也即满足二叉查找树的定义为前提条件，扩展的定义是为了保证其具有自平衡特性的
- 节点是红色或黑色
- 根节点是黑色
- 每个叶子节点都是黑色的空节点，即NIL节点
- 每个红色节点的两个子节点都是黑色（也即，从每个叶子到根的所有路径上不能有两个连续的红色节点，注意噢“没说黑色节点哈，因此可以出现两个连续的黑色节点”）
- 从任一节点到其每个叶子的所有路径均包含着相同数目的黑色节点
imagepng
=>也正是，上述的定义规则保证了红黑树可以具有自平衡的特性：在红黑树中，根结点到叶子结点的最大路径长度不会超过最短路径长度的2倍
2、调整
但是，在一般插入或删除节点的时候，红黑树可能会被打乱，导致其不符合其定义中的规则，因此需要做一些调整（变色和旋转【左旋转、右旋转】），以继续保证其仍然符合红黑树的定义规则
3、破坏
什么情况下会破坏红黑树的定义规则？什么情况下不会破坏红黑树的定义规则？
4、变色
也即，试图通过将红色节点变成黑色，或者将黑色节点变成红色，使得其重新满足红黑树的定义条件，这样的一种手段称之为变色
5、旋转
- 左旋转：逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子
- 右旋转：顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子
=>注意：红黑树的插入和删除，有很多种情况，每一种情况可能都会需要不同的处理方式(详细多种情形，可自行先维基百科中学习！后续再完善添加)
6、应用
- TreeMap
- TreeSet
- HashMap(JDK8)
