前言
首先我们需要二叉搜索树的主要优点：可以快速查找特定key值的节点，可以进快速进行删除和查找工作，
但同样二叉排序树也并非十全十美，比如连续插入一串有序的值的时候，如图：
如上图所示，我们得到的二叉树是十分不均匀的，一个好的二叉树必须满足均匀分布的特点，故此我们把这类树称为不平衡树，对于平衡树而言，插入/查找等操作时的效率围殴O(logN),但对于一个非平衡树而言，我们相当于重新编写了一个链表，效率就变为了O（N）
故此为了保证平衡树的实现，我们引入了AVL树和红黑树
红黑树
我常听过这样一句话“当面试官问你红黑树时，你基本已经挂了”，所以为了稍微稍微防止下这种情况，我们还是需要了解下红黑树的原理（代码就算了）
红黑树基本规则
- 节点是红色或黑色的
- 根节点是黑色
- 每个叶子结点都是黑色的空结点（NIL节点）
- 每个红色节点的两个儿子节点都是黑色节点（故此每个叶子到根的路径上不能有两个连续的红色节点）
- 从任意结点到每个叶子的所有路径都包含相同数目的黑色结点
这些规则的约束就可以构成红黑树的关键特性（相对平衡）
- 从根到叶子的最长可能路径，不会超过最短可能路径的两倍
- 这个树是一个平衡树，且高效
红黑树的变换
当我们插入一个新节点时，有可能不变的不再平衡，可以通过三种方式的转换将其变得平衡
- 变色
- 左旋转
-
变色
简单来说就是把红色变为黑色，把黑色变为红色（一头雾水）
首先我们需要知道，我们插入时往往插入的时红色节点，原因是： 插入一次红色结点大概率是不会违反红黑树规则的
- 插入黑色结点的话，就会导致多了黑色结点，很难调整
- 红色结点可能出现红红相连的情况，这种情况下需要变色和旋转
旋转
- 左旋转
逆转红黑树的两个结点，使得父节点被自己的右孩子代替，而自己变成了左孩子
- 右旋转
逆转红黑树的两个结点，使得父节点被自己的左孩子代替，而自己变成了右孩子
旋转后原分支的叶子结点大部分情况下都是通过平移解决，且旋转后原子树不会受到影响
红黑树的插入
接下来我们讨论红黑树的插入的情况，设要插入的结点为N，其父节点为P，其祖父结点为G，其父亲的兄弟结点为U
由上文可知，我们默认插入的结点为红色结点
情况一
新节点位于红黑树的根上，没有父节点，这样只需把N结点变为黑色即可（自黑）
情况二
新节点的父节点为黑色结点，尽管新节点有两个黑色的NIL结点，但其为红色结点，所以路径中黑色结点的个数依然相同，满足性质（父黑）
情况三
新节点为红色左子结点，其父节点也为红色结点，其叔叔结点也为红色结点，故此祖父结点肯定为黑色结点（父红叔红祖黑自为左孩）
解决：
我们要做的操作就是将P和U结点变为黑色结点，G结点变为红色结点，这样一来新节点N有一个黑色父亲结点P，所以每条路径上的黑色结点数目没有变，而从更高路径向下看，都会经过G点，故此路径上的黑色结点数目也满足性质（父黑叔黑祖变红）
问题：
如果G结点的父亲结点为红色的话，就不满足性质，此时可以通过递归来调整颜色，但是到了根节点，就得通过旋转来解决问题，这个之后再说
情况四
P结点为红色结点，U结点为黑色结点，G结点为黑色结点，N为左孩子（父红叔黑祖黑自为左孩）
解决：
G结点进行右旋转，旋转后以前的父节点P变成了以前祖父结点G的父结点，交换P结点和G结点的颜色，
B结点向右平移，变成G的左子结点（父黑组红右旋转），但是最好先变色后旋转
情况五
P为红色结点，U为黑色结点，G为黑色结点，N为右孩子（父红叔黑祖红自为右孩）
解决：
对P进行左旋转，形成情况四，再对G进行一次右旋转，再变色（父左组右再变色）
红黑树插入案例
案例：有1 2 3 4 5 6 7 8 9 10，依次插入10 9 8 7 6 5 4 3 2 1
插入结点10：
插入结点10，将10的颜色变为黑色
插入结点9：
符合情况二，不需要改变
插入结点8
满足情况四
插入结点7
满足情况三
父红叔黑组黑→父黑叔黑组红
但是会违背规则二
插入结点6
满足情况四
父变黑，祖变红，进行右旋转
插入结点5
满足情况三
6，8变为黑，7变为红
插入结点4
满足情况四
5变为黑，6变为红，再旋转
插入结点3
第一次变化：满足情况三，3，4，6变黑，5变红
第二次变化：满足情况四，7变黑，9变红，右旋转
插入结点2
满足情况四，3变黑，4变红，右旋转
插入结点1
第一次变化：2，4变黑，3变红
第二次变化：5，9变黑，7变红
就到这里吧
红黑树的删除更难，我就算了把。。。
若有收获，就点个赞吧
0 人点赞
