15 红黑树的插入变色旋转

情况三： 父红叔黑祖黑 插入后变成： 父黑叔黑祖红，并往上递归

情况四： （建议先变色再旋转）

情况五：

1. 对x左旋意味着“ 将x变成一个左节点 ，将“x的右孩子”设为“x的父亲节点” ”

2. 区分左旋右旋

左旋与右旋是对称的，无论是左旋还是右旋，被旋转的树，在旋转前是二叉查找树，并且旋转之后仍然是一颗二叉查找树。

3.  将插入的节点着色为红色，不会违背"特性(5)"！少违背一条特性，就意味着我们需要处理的情况越少。

但可能会违背性质四

红黑树的特性：

(1) 每个节点或者是黑色，或者是红色。

(2) 根节点是黑色。

(3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]

(4) 如果一个节点是红色的，则它的子节点必须是黑色的。

(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

4. 旋转的目的是让树保持红黑树的特性

5. 红黑树插入操作的核心思路都是：将红色的节点移到根节点；然后，将根节点设为黑色

补充

补充：左旋 / 右旋 是维持 BST 性质不变的前提下调整树形结构的两种基本操作：

  • 左旋 以某节点 x 为支点，x 的右孩子 y 上升为新的父节点，x 变为 y 的左孩子，y 原来的左孩子变为 x 的右孩子。
  • 右旋 与之对称。
// 以 y 为轴对 x 做左旋
function leftRotate(tree, x) {
  const y = x.right;
  x.right = y.left;
  if (y.left) y.left.parent = x;
  y.parent = x.parent;
  if (!x.parent) tree.root = y;
  else if (x === x.parent.left) x.parent.left = y;
  else x.parent.right = y;
  y.left = x;
  x.parent = y;
}

旋转后 BST 的中序遍历序列不变，仅改变节点的高度与父子关系，从而为后续的"重新着色 + 旋转"修复红黑树性质腾挪空间。

来源整理自：我的有道云笔记