B tree)原理图文详解(2)

这个时候，你会发现对于节点64无论是红色节点还是黑色节点，都会违反规则5，路径中的黑色节点始终无法达成一致，这个时候仅通过【变色】已经无法达成目的。我们需要通过旋转操作，当然【旋转】操作一般还需要搭配【变色】操作。

旋转包括【左旋】和【右旋】，

左旋：

逆时针旋转两个节点，让一个节点被其右子节点取代，而该节点成为右子节点的左子节点

左旋操作步骤如下：

首先断开节点PL与右子节点G的关系，同时将其右子节点的引用指向节点C2；然后断开节点G与左子节点C2的关系，同时将G的左子节点的应用指向节点PL

右旋：

顺时针旋转两个节点，让一个节点被其左子节点取代，而该节点成为左子节点的右子节点

右旋操作步骤如下：

首先断开节点G与左子节点PL的关系，同时将其左子节点的引用指向节点C2；然后断开节点PL与右子节点C2的关系，同时将PL的右子节点的应用指向节点G

无法通过变色而进行旋转的场景分为以下四种：

3.2 左左节点旋转

这种情况下，父节点和插入的节点都是左节点，如下图(旋转原始图1)这种情况下，我们要插入节点65

规则如下：以祖父节点【右旋】，搭配【变色】

按照规则，步骤如下：

3.3 左右节点旋转

这种情况下，父节点是左节点，插入的节点是右节点，在旋转原始图1中，我们要插入节点67

规则如下：先父节点【左旋】，然后祖父节点【右旋】，搭配【变色】

按照规则，步骤如下：

3.4 右左节点旋转

这种情况下，父节点是右节点，插入的节点是左节点，如下图(旋转原始图2)这种情况，我们要插入节点68

规则如下：先父节点【右旋】，然后祖父节点【左旋】，搭配【变色】

按照规则，步骤如下：

3.5 右右节点旋转

这种情况下，父节点和插入的节点都是右节点，在旋转原始图2中，我们要插入节点70

规则如下：以祖父节点【左旋】，搭配【变色】

按照规则，步骤如下：