红黑树的本质依然是二叉搜索树认为不存在相同的节点。最近在学map、set二者的底层数据结构都是红黑树。所以复习一下红黑树。对于一颗红黑树插入节点的大致流程是插入新节点-判断当前状态是否失衡-失衡调节-插入完成。一颗红黑树需要满足以下基本条件只有红黑节点顾名思义根节点是黑节点黑同路树上每个节点到它的任意叶子节点黑色节点的数量相同红孤单红节点不允许连续路径长度从根节点到某个叶子节点的所有路径里不存在一条路径长度大于另一条路径的2倍关于黑同路其实就是在红黑树上任选2个点分别作为起点和终点那么两点之间的任何路径经过的黑色节点都是一样的。补充的黑色节点是可以连续的且一个节点的孩子可以一个是红、一个是黑。只是插入新节点之前还有两个问题需要澄清一下新节点插入到哪个地方插入的新节点选择什么颜色新节点插入在什么地方只要哪个节点的子节点没满那都可以插入。插入的新节点选什么颜色那就分类讨论一下插入的新节点是黑色根据红黑树的黑同路性质一颗正常、未失衡的红黑树必定满足黑同路也即——每个节点到任一叶子节点的路径黑节点相同。那么如果插入一个新的黑节点那必定会导致所有经过它的路径都多了1个黑节点破坏了性质就需要失衡调节。插入的新节点是红色如果新节点的父亲是黑色那么插入之后依然不会破坏红黑树的性质。总而言之一句话如果插入的是黑节点那么必定需要失衡调节如果插入的是红节点至少有时候可以不用调节。对于插入节点我们给与它相关的节点都取个名字方便后续表示。[这里要插一张图]curcurrent表示插入的新节点parparentcur节点的父节点uncunclecur节点的叔叔或者说是par节点的兄弟gragrandcur节点的爷爷也是par和unc的父节点根据插入节点的位置和颜色情况一共有3种分类方向每种分类有2个可能组合起来就是2×2×282 \times 2 \times 2 82×2×28种情况。3种分类方向是par节点在gra节点的左边还是右边左边是Lleft右边是Rrightcur节点在par节点的左边还是右边左边是L右边是Rcur节点的unc节点是红色还是黑色黑色是Bblack红色是RRed注空节点视作黑节点所以如果爷爷节点只有1个孩子那么cur节点的叔叔视作黑色接下来开始分类讨论如何失衡调节。大类1叔叔是红色XXR叔叔是红色那么一共就有如下情况LLR、LRR、RLR、RRRLLR来确认一下图中情况是否是LLRL父亲在爷爷的左边L自己在父亲的左边R叔叔的颜色是红色调节方式是父亲、叔叔染黑爷爷染红调节之后如图可判断是否满足红黑树的基本性质。看上去挺简单的那么把情况扩展成一般情况用相同方式调节之后可以发现爷爷gra和自己的父节点都是红色破坏了红黑树“红节点不能连续”的性质。对于这种情况就需要把爷爷视作cur相应的也就有了新的par、unc、gra。此时再次按照父亲、叔叔染黑爷爷染红的方式调节。如此不断往上调整。那什么时候调整结束呢当cur是根节点时红黑树平衡结束调整。或者当cur的父节点是黑色也结束调整。最后还得注意把根节点给涂黑。因为当cur是根节点的孙子时调节时会把爷爷gra给染红那不就是把根节点给染红了嘛。LRRL父亲在爷爷的左边R自己在父亲的右边R叔叔是红色调节父亲、叔叔染黑爷爷染红接着cur标签移到爷爷处以同样的方式进行失衡调节当cur的父亲是黑色或者自己本身是根节点时结束循环红黑树已平衡将根节点染黑RLRR父亲在爷爷的右边L自己在父亲的左边R叔叔是红色调节父亲、叔叔染黑爷爷染红cur移动到爷爷处继续失衡判断当cur父亲是黑色或者自己是根节点时结束循环将根节点染黑RRRR父亲在爷爷的右边R自己的爷爷的右边R叔叔是红色调节同上大类2叔叔是黑色XXB叔叔是黑色当我把四种情况都画出来后发现新插入节点的父亲是红色且没有兄弟空节点视为黑色。LLBL父亲在爷爷的左边L自己在父亲的左边B叔叔是黑色调节父黑爷红爷旋转父亲染黑爷爷染红爷爷右旋关于左右旋我的理解是类似以前的手机游戏《吃糖果》。节点右旋说明该节点位于其子节点右上角那么该节点就往右旋转”落下来“变成了自己子节点的右孩子。如果碰到了子节点的右孩子那就顶替它把那条连线撞上去。节点左旋该节点位于其子节点的左上角左旋就是它往左旋转”掉落“变成自己子节点的左孩子。碰到子节点原本的左孩子就顶替它。LRBRLBRRB
