被问到了几次都直接说不了解 花点时间深入学习一手
红黑树的定义
- 节点是红色或黑色且是一个平衡二叉树
- 根节点是黑色，并定义null是黑色
- 如果一个节点是红色，那么他的两个子节点都是黑色且父节点也必定是黑色
- 对任一节点来说到叶子的所有路径都包含相同数目的黑色节点，称为黑高
任意一颗以黑色节点为根的子树也必定是一颗红黑树(递归定义)
左(右)子树的高度最多是(右)左子树的两倍,即:若H(left)>H(right),则H(left)<=2*H(right)+1
插入原则
不能插入黑色节点，只能插入红色节点然后再调整
将节点进行染色或者旋转时需要考虑定义的3和4
父节点:P,爷爷节点:G,叔节点:Y
无需调整的情况:
- X为根节点，将X由红色染成黑色,rootOver
- 父节点P为黑色，BlackParentOver ，bpOver
由于性质3爷爷节点必须为黑色节点，仅考虑父节点为红色的情况
- case1:Y为红色，X可左可右；P、Y染黑，G染红
- case2:Y为黑色，X为右孩子；左旋P，X指向P，转化为case3
-
case3:Y为黑色，X为左孩子；P染黑，G染红，右旋G
左旋：
image.png
右旋：
这里写图片描述
RBT的插入调整最多调整两次
case1：(叔、父皆红 叔父黑,祖父红)
条件:P为G的左孩子，Y为红色，X可左可右
处理方式:P、Y染黑，G染红，X回溯至爷节点(染红后引发新的case)
case1正确性证明：
- 此时X、P、Y、G的关系均满足性质3
- X的黑高并未改变，P、Y的黑高同时增加了1(染色)
- G的黑高并未改变(黑染红)
- G被染成红色，可能违反了性质2、性质3
由于此刻G是一个红色节点，故case1可以继续转化为case1、case2、case3。如果G是根节点此刻把根节点由红染黑，结束调整过程，此时红黑树的黑高增加1，这是唯一增加整个树黑高的情形(rootOver)
case2:(右孩子, 父红、叔黑 父右旋)
条件:P为G的左孩子，Y为黑色，X为右孩子
处理方式:左旋P，X指向P，转化为case3
case2正确性证明：
- P的左右子树的黑高并未改变(P满足性质4)
- X的左右子树黑高并未改变(X满足性质4)
- G的左右子树黑高并未改变
- P与X的关系违反性质3需要转化为case3
case3:(左孩子,父红、叔黑 父黑,祖父红,右旋祖父)
条件:P为G的左孩子，Y为黑色，X为P的左孩子
处理方式：P染黑，G染红，右旋G，结束
case3正确性证明：
- G的左右子树的黑高并未改变(G满足性质4)
- P的左右子树的黑高并未改变(P满足性质4)
- P的黑高并未改变(满足性质4)，P的颜色为黑色，必定满足性质2，性质3
对比AVL插入与RBT插入
插入元素都是二叉排序树插入，关键在于调整
旋转次数：AVL与RBT均是O(1)
指针回溯最好：AVL很早遇到单旋或者双旋的情况，为O(1)。RBT很早就遇到case2或者case3，为O(1)。
指针回溯最坏：AVL回溯至根节点才发现根节点不平衡，为logN。RBT不断执行case1，直到根节点，但每次向上回溯两层，为logN/2。
删除原则
删除红色节点，不会影响黑高，也不会违反性质3，无需调整
删除黑色节点，节点所在子树的黑高-1，需要调整
需要删除的节点X
