无法通过变色而进行旋转的场景分为以下四种:
左左节点旋转
这种情况下,父节点和插入的节点都是左节点,如下图(旋转原始图1)这种情况下,我们要插入节点 65。
规则如下:以祖父节点【右旋】,搭配【变色】。
按照规则,步骤如下:
左右节点旋转
这种情况下,父节点是左节点,插入的节点是右节点,在旋转原始图 1 中,我们要插入节点 67。
规则如下:先父节点【左旋】,然后祖父节点【右旋】,搭配【变色】。
按照规则,步骤如下:
右左节点旋转
这种情况下,父节点是右节点,插入的节点是左节点,如下图(旋转原始图 2)这种情况,我们要插入节点 68。
规则如下:先父节点【右旋】,然后祖父节点【左旋】,搭配【变色】。