stay hungry stay foolish

JS数据结构-红黑树

红黑是一棵特殊的平衡二叉树,其没有AVL树那么严格,其查找时间复杂的为2log2N,在实际开发中更加常用。

红黑树的特性

  • 根节点为黑色;
  • 不存在两个连续的红色节点;
  • 叶子节点为NULL的黑色节点;
  • 根节点到每个叶子节点所经过的黑色节点个数一致;

红黑树的插入

当插入的节点为根节点时,直接将根节点颜色置为黑色。

为了减少调整的次数,插入的子节点默认置为红色,当插入的节点的父节点为黑色时候,此时没有破坏红黑树的特征,不需要调整树。

当插入的节点的父节点为红色时,此时需要对树进行调整,主要有以下两种大的情况:叔叔节点为红色,叔叔节点为黑色。

叔叔节点为红色

叔叔节点为黑色

插入对应的代码:

//插入后检查并调整树
_proto._insertBalance = function(node) {
    if (node.rChild && node.rChild.color == 1 && (node.rChild.lChild && node.rChild.lChild.color == 1 || node.rChild.rChild && node.rChild.rChild.color == 1)) { //右子树不平衡,需要调整
        if (node.lChild && node.lChild.color == 1) { //如果左节点为红节点,不需要旋转,只需要改变颜色
            node.lChild.color = 0;
            node.rChild.color = 0;
            if (node != this.root) { //如果是根节点,不需要变色
                node.color = 1;
            }
        } else {
            if (node.rChild.rChild && node.rChild.rChild.color == 1) { //左旋转
                this._lRotate(node, true);
            } else { //先右旋转,再左旋转
                this._rlRotate(node);
            }
        }
    } else if (node.lChild && node.lChild.color == 1 && (node.lChild.lChild && node.lChild.lChild.color == 1 || node.lChild.rChild && node.lChild.rChild.color == 1)) { //左子树不平衡,需要调整
        if (node.rChild && node.rChild.color == 1) { //如果右节点为红节点,不需要旋转,只需要改变颜色
            node.lChild.color = 0;
            node.rChild.color = 0;
            if (node != this.root) { //如果是根节点,不需要变色
                node.color = 1;
            }
        } else {
            if (node.lChild.lChild && node.lChild.lChild.color == 1) { //左旋转
                this._rRotate(node, true);
            } else { //先左旋转,再右旋转
                this._lrRotate(node);
            }
        }
    } else {
        this._setHeight(node);
    }
};

红黑树的删除

平衡二叉树的删除和二叉排序树的删除原则一样,如果待删除的既有左子树又有右子树,则将其与对应的叶子节点(没有左子树或者没有右子树)替换位置,再删除该叶子节点。

如果删除的节点为红色,不用调整树,直接删除即可。如果删除的节点为黑色(根据红黑树性质,其必然没有左右子树),则需要重新调整树。下面主要讨论删除黑色子节点的情况。

左子树缺少一个黑色节点

调整左子树对应的代码:

if (pNode.rChild && pNode.rChild.color == 1) { //兄弟节点为红色
    pNode.color = 1;
    pNode.rChild.color = 0;
    this._lRotate(pNode);
    //将兄弟节点变成黑色节点后,再平衡
    this._deleteBalance(pNode, true);
} else if (pNode.rChild && (pNode.rChild.lChild && pNode.rChild.lChild.color == 1 ||
        pNode.rChild.rChild && pNode.rChild.rChild.color == 1)) { //兄弟节点的子节点为红色

    if (!pNode.rChild.rChild || pNode.rChild.rChild.color != 1) { //兄弟节点的右子节点不为红色
        pNode.rChild.lChild.color = 0;
        pNode.rChild.color = 1;
        //先右旋转
        this._rRotate(pNode.rChild);
    }
    var tmp = pNode.color;
    pNode.color = pNode.rChild.color;
    pNode.rChild.color = tmp;
    pNode.rChild.rChild.color = 0;
    this._lRotate(pNode);
} else if (pNode.color == 1) { //父节点为红色
    pNode.color = 0;
    pNode.rChild.color = 1;
} else {
    pNode.rChild && (pNode.rChild.color = 1);
    if (pNode != this.root) {
        if (pNode.pNode.lChild == pNode) {
            this._deleteBalance(pNode.pNode, true);
        } else {
            this._deleteBalance(pNode.pNode, false);
        }
    }
}

右子树缺少一个黑色节点

调整过程和(左子树缺少一个黑色节点)类似。

调整右子树对应的代码:

if (pNode.lChild && pNode.lChild.color == 1) { //兄弟节点为红色
    pNode.color = 1;
    pNode.lChild.color = 0;
    this._rRotate(pNode);
    //将兄弟节点变成黑色节点后,再平衡
    this._deleteBalance(pNode, false);
} else if (pNode.lChild && (pNode.lChild.lChild && pNode.lChild.lChild.color == 1 ||
        pNode.lChild.rChild && pNode.lChild.rChild.color == 1)) { //兄弟节点的子节点为红色

    if (!pNode.lChild.lChild || pNode.lChild.lChild.color != 1) { //兄弟节点左子节点不为红色
        pNode.lChild.rChild.color = 0;
        pNode.lChild.color = 1;
        //先左旋转
        this._lRotate(pNode.lChild);
    }
    var tmp = pNode.color;
    pNode.color = pNode.lChild.color;
    pNode.lChild.color = tmp;
    pNode.lChild.lChild.color = 0;
    this._rRotate(pNode);
} else if (pNode.color == 1) { //父节点为红色
    pNode.color = 0;
    pNode.lChild.color = 1;
} else {
    pNode.lChild && (pNode.lChild.color = 1);
    if (pNode != this.root) {
        if (pNode.pNode.lChild == pNode) {
            this._deleteBalance(pNode.pNode, true);
        } else {
            this._deleteBalance(pNode.pNode, false);
        }
    }
}

完整代码