红黑树的插入

摘要：算法导论由于性质，红黑树中不会出现两个红色结点相邻的情形。红黑树的插入首先以二叉搜索树的方式插入结点，并将其着为红色。假设整棵二叉搜索树中，只有和因违背性质而无法成为正常的红黑树，此时将图调整成图，则可以恢复成正常的红黑树。

一棵满足以下性质的二叉搜索树是一棵红黑树

每个结点或是黑色或是红色。

根结点是黑色的。

每个叶结点(NIL)是黑色的。

如果一个结点是红色的，则它的两个子结点都是黑色的。

对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。

性质1和性质2，不用做过多解释。

性质3，每个叶结点(NIL)是黑色的。这里的叶结点并不是指上图中结点1,5,8,15，而是指下图中值为null的结点，它们的颜色为黑色，且是它们父结点的子结点。

性质4，如果一个结点是红色的(图中用白色代替红色)，则它的两个子结点都是黑色的，例如结点2,5,8,15。但是，如果某结点的两个子结点都是黑色的，该结点未必是红色的，例如结点1。

性质5，对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。例如，从结点2到其所有后代叶结点的简单路径上，黑色结点的数量都为2；从根结点11到其所有后代叶结点的简单路径上，黑色结点的数量都为3。

这样的一棵树有什么特点呢？

通过对任何一条从根到叶结点的简单路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍，因为是近似于平衡的。——《算法导论》

由于性质4，红黑树中不会出现两个红色结点相邻的情形。树中最短的可能出现的路径是都是黑色结点的路径，树中最长的可能出现的路径是红色结点和黑色结点交替的路径。再结合性质5，每条路径上均包含相同数目的黑色结点，所以红黑树确保没有一条路径会比其他路径长出2倍。

首先以二叉搜索树的方式插入结点，并将其着为红色。如果着为黑色，则会违背性质5，不便调整；如果着为红色，可能会违背性质2或性质4，可以通过相对简单的操作，使其恢复红黑树的性质。

一个结点以二叉搜索树的方式被插入后，可能出现以下几种情况：

插入结点后，无父结点，结点插入成为根结点，违背性质2，将结点调整为黑色，完成插入。

插入结点后，其父结点为黑色，没有违背任何性质，不用调整，完成插入。例如下图中插入结点13。

插入结点后，其父结点为红色，违背了性质4，需要采取一系列的调整。例如下图中插入结点4。

那么一系列的调整是什么呢？

如果插入结点node的父结点father为红色，则结点father必然存在黑色的父结点grandfather，因为如果结点father不存在父结点的话，就是根结点，而根结点是黑色的。那么结点grandfather的另一个子结点，我们可以称之为结点uncle，即结点father的兄弟结点。结点uncle可能为黑色，也可能为红色。

先从最简单的情形分析，因为复杂的情形可以转化为简单的情形，简单的情形就是结点uncle为黑色的情形。

如上图(a)中，情形是这样的，node 为红，father 为红，grandfather 和 uncle 为黑，α，β，θ，ω，η 都是结点对应的子树。假设整棵二叉搜索树中，只有node和father因违背性质4而无法成为正常的红黑树，此时将图(a)调整成图(b)，则可以恢复成正常的红黑树。整个调整过程中实际分为两步，旋转和变色。

什么是旋转？

如上图(c)是一棵二叉搜索树的一部分，其中 x, y 是结点，α，β，θ 是对应结点的子树。由图可知，α < x < β < y < θ ，即 α子树中的所有结点都小于x，结点 x都小于 β子树中的所有结点，β子树中的所有结点的值都小于结点 y 的值，结点 y 的值都小于 θ子树中的所有结点。在二叉搜索树中，如果结点y的值比结点x的值大，那么结点x在结点y的左子树中，如图(c)；或者结点y在结点x的右子树中，如图(d)。故 α < x < β < y < θ ，也可以用图(d)的结构来表现。这就是旋转，它不会破坏二叉搜索树的性质。

node 为红，father 为红，grandfather 和 uncle 为黑的具体情形一

图(a)中，node 为 father 的左子结点， father 为 grand 的左子结点，node < father < θ < grand < uncle。这种情形中 father < grand，即可以表现为 father 是 grand 的左子树，也可以表现为 grand 是 father 的右子树，故将图(a)中 father 和 grand 旋转，旋转虽然不会破坏二叉搜索树的性质，但是旋转之后，会破坏红黑树的性质，所以还需要调整结点的颜色。

变色

所以图(a)旋转过后，还要将 grand 变为红色，father 变为黑色，变成图(b)，完成插入。

node 为红，father 为红，grandfather 和 uncle 为黑的具体情形二

node 为 father 的右子结点， father 为 grand 的右子结点，如下图(e)，就是具体情形一的翻转。

即，uncle < grand < θ < father < node ，将图(e)中 father 和 grand 旋转，变色后，变成图(f)，完成插入。

node 为红，father 为红，grandfather 和 uncle 为黑的具体情形三

node 为 father 的右子结点， father 为 grand 的左子结点，如下图(m)。

将图(m)中 node 和 father 旋转后，变成图(n)，将father看作新的node，就成为了具体情形一，再次旋转，变色后，完成插入。

node 为红，father 为红，grandfather 和 uncle 为黑的具体情形四

node 为 father 的右子结点， father 为 grand 的左子结点，如下图(i)，就是具体情形三的翻转。

将图(i)中 node 和 father 旋转后，变成图(j)，将father看作新的node，就成为了具体情形二，再次旋转，变色后，完成插入。

node ，father 和 uncle 为红，grandfather 为黑。

如上图(k)，不旋转，而是将grand着红，father和uncle着黑，同时将grand作为新的node，进行情形的判断。如果grand作为新的node后，变成了情形2，则插入完成；如果变成了情形3.1，则调整后，插入完成；如果仍是情形3.2，则继续将grand，father和uncle变色，和node结点上移，如果新的node结点没有父节点了，则变成了情形1，将根结点着为黑色，那么插入完成。

// 结点
function Node(value) {
  this.value = value
  this.color = "red" // 结点的颜色默认为红色
  this.parent = null
  this.left = null
  this.right = null
}

function RedBlackTree() {
  this.root = null
}

RedBlackTree.prototype.insert = function (node) {
  // 以二叉搜索树的方式插入结点
  // 如果根结点不存在，则结点作为根结点
  // 如果结点的值小于node，且结点的右子结点不存在，跳出循环
  // 如果结点的值大于等于node，且结点的左子结点不存在，跳出循环
  if (!this.root) {
    this.root = node
  } else {
    let current = this.root
    while (current[node.value <= current.value ? "left" : "right"]) {
      current = current[node.value <= current.value ? "left" : "right"]
    }
    current[node.value <= current.value ? "left" : "right"] = node
    node.parent = current
  }
  // 判断情形
  this._fixTree(node)
  return this
}

RedBlackTree.prototype._fixTree = function (node) {
  // 当node.parent不存在时，即为情形1，跳出循环
  // 当node.parent.color === "black"时，即为情形2，跳出循环
  while (node.parent && node.parent.color !== "black") {
    // 情形3
    let father = node.parent
    let grand = father.parent
    let uncle = grand[grand.left === father ? "right" : "left"]
    if (!uncle || uncle.color === "black") {
      // 叶结点也是黑色的
      // 情形3.1
      let directionFromFatherToNode = father.left === node ? "left" : "right"
      let directionFromGrandToFather = grand.left === father ? "left" : "right"
      if (directionFromFatherToNode === directionFromGrandToFather) {
        // 具体情形一或二
        // 旋转
        this._rotate(father)
        // 变色
        father.color = "black"
        grand.color = "red"
      } else {
        // 具体情形三或四
        // 旋转
        this._rotate(node)
        this._rotate(node)
        // 变色
        node.color = "black"
        grand.color = "red"
      }
      break // 完成插入，跳出循环
    } else {
      // 情形3.2
      // 变色
      grand.color = "red"
      father.color = "black"
      uncle.color = "black"
      // 将grand设为新的node
      node = grand
    }
  }

  if (!node.parent) {
    // 如果是情形1
    node.color = "black"
    this.root = node
  }
}

RedBlackTree.prototype._rotate = function (node) {
  // 旋转 node 和 node.parent
  let y = node.parent
  if (y.right === node) {
    if (y.parent) {
      y.parent[y.parent.left === y ? "left" : "right"] = node
    }
    node.parent = y.parent
    if (node.left) {
      node.left.parent = y
    }
    y.right = node.left
    node.left = y
    y.parent = node
  } else {
    if (y.parent) {
      y.parent[y.parent.left === y ? "left" : "right"] = node
    }
    node.parent = y.parent
    if (node.right) {
      node.right.parent = y
    }
    y.left = node.right
    node.right = y
    y.parent = node
  }
}

let arr = [11, 2, 14, 1, 7, 15, 5, 8, 4, 16]
let tree = new RedBlackTree()
arr.forEach(i => tree.insert(new Node(i)))
debugger