图(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，就成为了具体情形二，再次旋转，变色后，完成插入。
情形3.2
node ，father 和 uncle 为红，grandfather 为黑。
如上图(k)，不旋转，而是将grand着红，father和uncle着黑，同时将grand作为新的node，进行情形的判断。如果grand作为新的node后，变成了情形2，则插入完成；如果变成了情形3.1，则调整后，插入完成；如果仍是情形3.2，则继续将grand，father和uncle变色，和node结点上移，如果新的node结点没有父节点了，则变成了情形1，将根结点着为黑色，那么插入完成。
综上
node的情形
操作
情形1
node为红,无father
将node重新着色
情形2
node为红,father为黑
情形3.1
node,father为红,grand,uncle为黑
旋转一次或两次,并重新着色
情形3.2
node,father,uncle为红,grand为黑
将father, uncle,grand重新着色, grand作为新的node
代码
// 结点 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
总结