红黑树的构建

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)
}())