红黑树的旋转

转换规则

• 红黑树默认插入的是红子树、也不允许有任何两个相连的节点都为红色。

• 1、颜色转换情况：
  如果当前节点的父节点是红色，且父节点的兄弟节点也是红色，那么需要进行颜色转变：

  • 父节点变为黑色、父节点的兄弟节点也变为黑色，然后父节点的父节点表位红色

• 2、左旋的情况：（自己当然是红色）
  如果父节点为红色，父节点的兄弟节点是黑色，且自己是父节点的 右子树 时需要进行左旋：

  • 以父节点作为旋转节点，将父节点转到自己的左子树下，自己就转到父节点位置。

• 3、右旋的情况：（稍微复杂一点）
  如果父节点为红色，父节点的兄弟节点是黑色，且自己是父节点的 左子树 时需要进行右旋：

  • 1、先要进行变色：父节点变为黑色、再把父节点的父节点变为红色
  • 2、以父节点的父节点作为旋转节点，将父节点的父节点变为父节点右子树，父节点代替父节点的父节点的位置。

就这样一直变颜色、旋转，直到该数符合红黑树即可，并不难。