两兄弟房子怎么分左右,两兄弟分房子有左右吗

上图包含了左旋和右旋的示意图，这里以右旋为例进行说明，右旋节点 M 的步骤如下：

0. 将节点 M 的左孩子引用指向节点 E 的右孩子
1. 将节点 E 的右孩子引用指向节点 M，完成旋转

旋转操作本身并不复杂，上面分析了右旋操作，左旋操作与此类似，只是右旋转的逆操作。

红黑树的插入过程和二叉查找树插入过程基本类似，不同的地方在于，红黑树插入新节点后，需要进行调整，以满足红黑树的性质。

性质1规定红黑树节点的颜色要么是红色要么是黑色，那么在插入新节点时，这个节点应该是红色还是黑色呢？答案是红色，原因也不难理解。如果插入的节点是黑色，那么这个节点所在路径比其他路径多出一个黑色节点，这个调整起来会比较麻烦（参考红黑树的删除操作，就知道为啥多一个或少一个黑色节点时，调整起来这么麻烦了）。如果插入的节点是红色，此时所有路径上的黑色节点数量不变，仅可能会出现两个连续的红色节点的情况。这种情况下，通过变色和旋转进行调整即可，比之前的简单多了。所以插入的时候将节点设置为红色，可以保证满足性质 1、2、3、5 ，只有性质4不一定满足，需要进行相关调整。如果是添加根节点，则将节点设定为黑色。

我们在分析红黑树各种插入情况的时候，将其等价转换为B树，这样我们能够更直观的进行分类，首先确定几条性质：

0. B树中，新元素必定是添加到叶子节点中（最底层的节点）
1. 4阶B树所有节点的元素个数 x 都符合 1 ≤ x ≤ 3

在上一章节红黑树的等价变换中，我们讲到了红黑树转换成B树总共有四种情况，也就是上图中叶子节点这四种情况，那么在我们进行插入操作的时候，会将节点插入到所有的叶子节点中，总共就会有12种情况，其中四种情况满足红黑树的性质，8种情况不满足红黑树性质。

有 4 种情况满足红黑树的性质 4 ：parent 为黑色节点。这四种情况不需要做任何额外的处理。

有 8 种情况不满足红黑树的性质 4 ：parent 为红色节点（ Double Red ），其中左面4种属于B树节点上溢的情况（一个4阶B树节点中最多存放三个数，这四种情况本来已经有3个了，又插入了1个，变成了4个，超出了4阶B树节点的容量范围，这种情况称为上溢）。这八种情况需要进行额外的处理。