红黑树的构建
let sentinel = {color: 'black', value: null}; let root = sentinel; function data(data) { return typeof data === 'object' && data !== null ? data.key : data; } function Node({value, left = sentinel, right = sentinel, parent = null, color}) { Object.assign(this, { left, right, parent, value, color, }); }; function black(node) { node.color = 'black'; } function red(node) { node.color = 'red'; } function isBlack(node) { return node.color === 'black'; } function isRed(node) { return node.color === 'red'; } function rbtree_insert(node) { // root为空说明当前插入第一个节点 if (root === sentinel) { root = node; return; } let current = root; // 先插入 while(current) { // 比当前节点大则往右走，如果到达最后一个右孩子，则设置当前节点为他的右孩子 if (data(node.value) > data(current.value)) { if (current.right === sentinel) { current.right = node; node.parent = current; break; } current = current.right; } else { // 同上 if (current.left === sentinel) { current.left = node; node.parent = current; break; } current = current.left; } } // 插入成功后，标记插入节点为红色，尽量满足各种约束 red(node); /* 父节点是红色的话，需要开始调整 node节点是根节点的孩子时，不进入while。 node不是根节点并且父节点是红色，说明父节点还有父节点， 即父节点不是根节点，因为根节点必须是黑色 */ while(node !== root && isRed(node.parent)) { // node的父节点是node父节点的父节点的左孩子 if (node.parent === node.parent.parent.left) { /* node的父节点是红色，说明祖父节点是黑色，node的叔叔节点是红色， 则只需要做下面一步调整，即node的父节点和叔叔好节点变红，祖父节点变红。 因为以祖父节点为根的这棵子树中，调整前，父节点和叔叔节点共享 祖父节点的黑色，调整后，祖父节点为红色，但是父节点和叔叔节点为黑色了， 不影响以祖父节点为根节点的子树的黑高度。因为祖父节点变红了，如果祖父节点的父节点 也是红色，则又回到了一开始的问题，即跳到while。 1 当node.parent.parent是根节点的时候，直接退出循环，但这是他是红色的，所以循环外需要 2 把他强制变黑。如果node.parent.parent是根节点的孩子，则isRed(node.parent)不会成立，也会退出循环。 */ if (isRed(node.parent.parent.right)) { black(node.parent); black(node.parent.parent.right); red(node.parent.parent); node = node.parent.parent; } else { /* 如果叔叔节点是黑色，这时候的结构是， 父节点是红色，祖父是黑色，叔叔是黑色。node是红色。 调整理论也是类似上面，即父节点变黑，祖父节点变红，叔叔变黑。 但是因为调整前，以祖父节点为根的子树中，父节点和叔叔共享祖父的一个黑节点， 现在祖父变红，父节点变黑，对祖父节点到父节点这条路径的黑高度没影响，但是对 祖父到叔叔这条路径有影响，少了一个黑高度。这时候就要右旋转（见下面右旋转函数的解释）。 右旋导致父节点上升，替换祖父节点的位置，祖父下降成为父节点的右孩子，从而导致父节点原来的 右孩子（如果有的话）没有地方挂载。所以右旋转前，要先把以父节点为根的子树，左旋转（见下面左旋函数的结束）一下。 因为父节点的右孩子比父节点大，所以右孩子会替换父节点成为该子树的新根节点。而父节点变成右孩子的左孩子。 这时候，因为右孩子上升为根节点，并且左孩子是原来的父节点。会导致右孩子原来的左孩子（有的话）没有地方挂载。 所以这个左孩子会成为父节点的右孩子。我们会发现，这样左旋或右旋，是不是破坏红黑数的规则的。 */ if (node === node.parent.right) { rbtreeLeftRotate(node.parent); } black(node.parent); black(node.parent.parent.right); red(node.parent.parent); rbtreeRightRotate(node.parent.parent); } } else { // 类似上面的解释 if (isRed(node.parent.parent.left)) { black(node.parent); black(node.parent.parent.left); red(node.parent.parent); node = node.parent.parent; } else { if (node === node.parent.left) { rbtreeRightRotate(node.parent); } black(node.parent); black(node.parent.parent.left); red(node.parent.parent); rbtreeLeftRotate(node.parent.parent); } } } // 根节点可能会被变红，这里强制变黑 black(root); } // 左旋转，node成为右节点的左孩子，node右孩子的左孩子成为node的右孩子 // function rbtreeLeftRotate(node) { // 保存右孩子的地址，因为node的右指针即将被修改 let right = node.right; // 第一步挂载右孩子的节点到父节点 // 右孩子的左孩子成为node的右孩子 node.right = right.left; // 可能没有左孩子，有的话他的父指针指向node if (node.right !== sentinel) { node.right.parent = node; } // 第二步，替换node成为子树根节点 // 到达根，则right变成新的根节点，否则修改node的父节点对应指针的指向，即替换node的位置， if (node === root) { root = right; } else if (node === node.parent.left){ node.parent.left = right; } else { node.parent.right = right; } // 更新右孩子的父节点，不再是node，而是他的父节点 right.parent = node.parent; // 第三步，建立右孩子和node的连接 right.left = node; node.parent = right; } // 右旋转，node成为左节点的右孩子，node左孩子的右孩子成为node的左孩子 function rbtreeRightRotate(node) { let left = node.left; node.left = left.right; if (node.left !== sentinel) { node.left.parent = node; } if (node === root) { root = left; } else if (node === node.parent.left) { node.parent.left = left; } else { node.parent.right = right; } left.parent = node.parent; left.right = node; node.parent = left; } (function test(){ const data = []; let i = 0; while(i < 5) { rbtree_insert(new Node({value: i++})); } console.log(root) }())
