摘要：紅黑樹(shù)的刪除可能出現(xiàn)的情形討論刪除紅黑樹(shù)中一個(gè)結(jié)點(diǎn)，刪除的結(jié)點(diǎn)是其子結(jié)點(diǎn)狀態(tài)和顏色的組合。組合被刪結(jié)點(diǎn)無(wú)子結(jié)點(diǎn)，且被刪結(jié)點(diǎn)為紅色此時(shí)直接將結(jié)點(diǎn)刪除即可，不破壞任何紅黑樹(shù)的性質(zhì)。

刪除紅黑樹(shù)中一個(gè)結(jié)點(diǎn)，刪除的結(jié)點(diǎn)是其子結(jié)點(diǎn)狀態(tài)和顏色的組合。子結(jié)點(diǎn)的狀態(tài)有三種：無(wú)子結(jié)點(diǎn)、只有一個(gè)子結(jié)點(diǎn)、有兩個(gè)子結(jié)點(diǎn)。顏色有紅色和黑色兩種。所以共會(huì)有6種組合。

此時(shí)直接將結(jié)點(diǎn)刪除即可，不破壞任何紅黑樹(shù)的性質(zhì)。

處理方法略微復(fù)雜，稍后再議。

這種組合是不存在的，如圖假如被刪結(jié)點(diǎn)node只有一個(gè)有值的子結(jié)點(diǎn)value，而以value為根結(jié)點(diǎn)的子樹(shù)中，必然還存在null結(jié)點(diǎn)，如此不符合紅黑樹(shù)的性質(zhì)5，對(duì)每個(gè)結(jié)點(diǎn)，從該結(jié)點(diǎn)到其所有后代葉結(jié)點(diǎn)的簡(jiǎn)單路徑上，均包含相同數(shù)目的黑色結(jié)點(diǎn)。

這種組合下，被刪結(jié)點(diǎn)node的另一個(gè)子結(jié)點(diǎn)value必然為紅色，此時(shí)直接將node刪掉，用value代替node的位置，并將value著黑即可。

當(dāng)被刪結(jié)點(diǎn)node有兩個(gè)子結(jié)點(diǎn)時(shí)，先要找到這個(gè)被刪結(jié)點(diǎn)的后繼結(jié)點(diǎn)successor，然后用successor代替node的位置，同時(shí)著成node的顏色，此時(shí)相當(dāng)于successor被刪。

因?yàn)閚ode有兩個(gè)子結(jié)點(diǎn)，所以successor必然在node的右子樹(shù)中，必然是下圖兩種形態(tài)中的一種。

若是(a)的情形，用successor代替node后，相當(dāng)于successor被刪，若successor為紅色，則變成了組合1；若successor為黑色，則變成了組合2。

若是(b)的情形，用successor代替node后，相當(dāng)于successor被刪，若successor為紅色，則變成了組合1；若successor為黑色，則變成了組合2或4。

若被刪結(jié)點(diǎn)是組合1或組合4的狀態(tài)，很容易處理；被刪結(jié)點(diǎn)不可能是組合3的狀態(tài)；被刪結(jié)點(diǎn)是組合5&6的狀態(tài)，將變成組合1或組合2或組合4。

因?yàn)閯h除黑色結(jié)點(diǎn)會(huì)破壞紅黑樹(shù)的性質(zhì)5，所以為了不破壞性質(zhì)5，在替代結(jié)點(diǎn)上額外增加一個(gè)黑色，這樣不違背性質(zhì)5而只違背性質(zhì)1，每個(gè)結(jié)點(diǎn)或是黑色或是紅色。此時(shí)將額外的黑色移除，則完成刪除操作。

然后再結(jié)合node原來(lái)的父結(jié)點(diǎn)father和其兄弟結(jié)點(diǎn)brother來(lái)分析。

brother為黑色，且brother有一個(gè)與其方向一致的紅色子結(jié)點(diǎn)son，所謂方向一致，是指brother為father的左子結(jié)點(diǎn)，son也為brother的左子結(jié)點(diǎn)；或者brother為father的右子結(jié)點(diǎn)，son也為brother的右子結(jié)點(diǎn)。

圖(c)中，白色代表隨便是黑或是紅，方形結(jié)點(diǎn)除了存儲(chǔ)自身黑色外，還額外存儲(chǔ)一個(gè)黑色。將brother和father旋轉(zhuǎn)，并重新上色后，變成了圖(d)，方形結(jié)點(diǎn)額外存儲(chǔ)的黑色轉(zhuǎn)移到了father，且不違背任何紅黑樹(shù)的性質(zhì)，刪除操作完成。

圖(c)中的情形顛倒過(guò)來(lái)，也是一樣的操作。

brother為黑色，且brother有一個(gè)與其方向不一致的紅色子結(jié)點(diǎn)son

圖(e)中，將son和brother旋轉(zhuǎn)，重新上色后，變成了圖(f)，情形一。

圖(e)中的情形顛倒過(guò)來(lái)，也是一樣的操作。

brother為黑色，且brother無(wú)紅色子結(jié)點(diǎn)

此時(shí)若father為紅，則重新著色即可，刪除操作完成。如圖下圖(g)和(h)。

此時(shí)若father為黑，則重新著色，將額外的黑色存到father，將father作為新的結(jié)點(diǎn)進(jìn)行情形判斷，遇到情形一、情形二，則進(jìn)行相應(yīng)的調(diào)整，完成刪除操作；如果沒(méi)有，則結(jié)點(diǎn)一直上移，直到根結(jié)點(diǎn)存儲(chǔ)額外的黑色，此時(shí)將該額外的黑色移除，即完成了刪除操作。

brother為紅色，則father必為黑色。

圖(i)中，將brother和father旋轉(zhuǎn)，重新上色后，變成了圖(j)，新的brother變成了黑色，這樣就成了情形一、二、三中的一種。如果將son和brother旋轉(zhuǎn)，無(wú)論怎么重新上色，都會(huì)破壞紅黑樹(shù)的性質(zhì)4或5，例如圖(k)。
圖(i)中的情形顛倒過(guò)來(lái)，也是一樣的操作。

// 結(jié)點(diǎn)
function Node(value) {
  this.value = value
  this.color = "red" // 結(jié)點(diǎn)的顏色默認(rèn)為紅色
  this.parent = null
  this.left = null
  this.right = null
}

function RedBlackTree() {
  this.root = null
}

RedBlackTree.prototype.insert = function (node) {
  // 以二叉搜索樹(shù)的方式插入結(jié)點(diǎn)
  // 如果根結(jié)點(diǎn)不存在，則結(jié)點(diǎn)作為根結(jié)點(diǎn)
  // 如果結(jié)點(diǎn)的值小于node，且結(jié)點(diǎn)的右子結(jié)點(diǎn)不存在，跳出循環(huán)
  // 如果結(jié)點(diǎn)的值大于等于node，且結(jié)點(diǎn)的左子結(jié)點(diǎn)不存在，跳出循環(huán)
  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) {
  // 當(dāng)node.parent不存在時(shí)，即為情形1，跳出循環(huán)
  // 當(dāng)node.parent.color === "black"時(shí)，即為情形2，跳出循環(huán)
  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") {
      // 葉結(jié)點(diǎn)也是黑色的
      // 情形3.1
      let directionFromFatherToNode = father.left === node ? "left" : "right"
      let directionFromGrandToFather = grand.left === father ? "left" : "right"
      if (directionFromFatherToNode === directionFromGrandToFather) {
        // 具體情形一或二
        // 旋轉(zhuǎn)
        this._rotate(father)
        // 變色
        father.color = "black"
        grand.color = "red"
      } else {
        // 具體情形三或四
        // 旋轉(zhuǎn)
        this._rotate(node)
        this._rotate(node)
        // 變色
        node.color = "black"
        grand.color = "red"
      }
      break // 完成插入，跳出循環(huán)
    } else {
      // 情形3.2
      // 變色
      grand.color = "red"
      father.color = "black"
      uncle.color = "black"
      // 將grand設(shè)為新的node
      node = grand
    }
  }

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

RedBlackTree.prototype._rotate = function (node) {
  // 旋轉(zhuǎn) 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
  }
}

RedBlackTree.prototype.remove = function (node) {
  while (true) {
    let {
      left,
      right,
      parent,
      color
    } = node
    // 組合1
    if (!left && !right && color === "red") {
      parent[parent.left === node ? "left" : "right"] = null
      return this
    }
    // 組合2
    if (!left && !right && color === "black") {
      if (parent) {
        let nullNode = new Node(null)
        nullNode.parent = parent
        nullNode.color = ["black", "black"]
        parent[parent.left === node ? "left" : "right"] = nullNode
        this._repairTree(nullNode)
      } else {
        this.root = null
      }
      return this
    }
    // 組合4
    if ((!left && right && color === "black") || (left && !right && color === "black")) {
      if (parent) {
        parent[parent.left === node ? "left" : "right"] = node.left || node.right
      } else {
        this.root = node.left || node.right
      }
      node[node.left ? "left" : "right"].color = "black"
      return this
    }
    // 組合5&6
    if (left && right) {
      // 尋找后繼結(jié)點(diǎn)
      let successor = right
      while (successor.left) {
        successor = successor.left
      }
      // 用后繼結(jié)點(diǎn)代替node
      node.value = successor.value
      // 刪除后街結(jié)點(diǎn)
      node = successor
      /* let successorColor = successor.color
      let successorLeft = successor.left
      let successorRight = successor.right
      let successorParent = successor.parent
      // 用后繼節(jié)點(diǎn)代替node
      if (parent) {
        parent[parent.left === node ? "left" : "right"] = successor
      } else {
        this.root = successor
      }
      successor.parent = parent
      successor.left = left
      successor.right = right
      left.parent = successor
      right.parent = successor
      successor.color = color
      // 刪除successor
      node.left = successorLeft
      node.right = successorRight
      node.parent = successorParent
      node.color = successorColor */
    }
  }
}

RedBlackTree.prototype._repairTree = function (node) {
  while (node.parent) {
    let father = node.parent
    let brother = father[father.left === node ? "right" : "left"]
    let son = brother[father.left === node ? "right" : "left"]
    let daugh = brother[father.left === node ? "left" : "right"]
    if (brother.color === "black") {
      if (son && son.color === "red") {
        // 情形一
        // 旋轉(zhuǎn)brother和father
        this._rotate(brother)
        // 變色
        brother.color = father.color
        father.color = "black"
        son.color = "black"
        // 移除black
        if (!node.value) {
          // nullNode
          father[father.left === node ? "left" : "right"] = null
        } else {
          node.color = "black"
        }
        // 刪除操作完成
        return
      } else if (daugh && daugh.color === "red") {
        // 情形二
        // 旋轉(zhuǎn)son和brother
        this._rotate(son)
        // 變色
        son.color = "black"
        brother.color = "red"
        // 變成情形一，繼續(xù)循環(huán)
      } else {
        // 情形三
        // brother無(wú)紅子結(jié)點(diǎn)
        if (father.color === "red") {
          // father為紅色
          father.color = "black"
          brother.color = "red"
          // 移除black
          if (!node.value) {
            // nullNode
            father[father.left === node ? "left" : "right"] = null
          } else {
            node.color = "black"
          }
          // 刪除操作完成
          return
        } else {
          // father為黑色
          father.color = ["black", "black"]
          brother.color = "red"
          // 移除black
          if (!node.value) {
            // nullNode
            father[father.left === node ? "left" : "right"] = null
          } else {
            node.color = "black"
          }
          node = father
          // 結(jié)點(diǎn)上移，繼續(xù)循環(huán)
        }
      }
    } else {
      // 情形四
      this._rotate(brother)
      brother.color = "black"
      father.color = "red"
      // 繼續(xù)循環(huán)
    }
  }
  this.root = node
  node.color = "black"
}

RedBlackTree.prototype.find = function (value) {
  let current = this.root
  while (current.value !== value) {
    current = current[value >= current.value ? "right" : "left"]
  }
  return current
}

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

紅黑樹(shù)的插入

紅黑樹(shù)的插入和刪除都是通過(guò)分類討論來(lái)解決的，耐心的分析即可。
為數(shù)不多使用技巧的地方，是為了維持紅黑樹(shù)的性質(zhì)，在結(jié)點(diǎn)上存兩個(gè)黑色，當(dāng)然這是算法導(dǎo)論告訴我的。