用Js实现红黑树-白红宇

学习红黑树，用js撸了一个

红黑树是一个效率很高且稳定的数据结构，插入和删除操作的时间复杂度都是logn。

红黑树的性质：

每一个节点或者着红色，或者着黑色

根是黑色

如果一个节点是红色的，那么它的子节点必须是黑色

从一个节点到一个Null节点（树叶）的每一条简单路径必须包含相同数目的黑色节点

插入操作以后再补~

删除操作（自顶向下的实现方式）

删除操作是红黑树最难的部分，通常有两种实现方式：自顶向下和自底向上。《算法导论》里使用的是自底向上的实现方式，对我而言相当晦涩，又看了几篇类似的实现方式，需要罗列出相当多的情形，实现不易。《数据结构与算法 -- C语言实现》里使用的是自顶向下的实现方式，但只讨论了大致逻辑，并未给出具体实现，最后在里找到了完整的实现。自顶向下的方式确实简单易懂，且非常巧妙，我也是用这种方式来实现红黑树的删除操作

在此之前，先复习一下前面列出的红黑树的性质。删除操作之所以复杂，是因为如果需要删除的节点是黑色的，那么直接删除它会破坏性质4。因此，我们需要保证删除该节点之后，能有一种方式修复删除后被破坏的部分。自底向上实现的思路是：先删除节点，然后通过旋转、变色等手段恢复破坏了红黑树性质的部分，而自顶向下实现的思路是：在查找需要删除的节点的路径上，保证每个节点都是红色的（如果不是就要通过变换让它变成红色，且不破坏树的性质），如果它是要删除的节点，就可以安心地删除它。就思路而言，显然自底向上的方式更易理解，好像也更容易实现，但当你去处理修复过程时会发现有相当多的情况需要考虑。而自顶向下的方式看似笨拙，却能够通过巧妙的变换简化变换的过程

总的来说，就是我们要让当前访问的节点X变红，然后再去考虑它是不是需要删除的节点

启动条件

删除是一个递归函数，在进入递归之前需要确保当前当前结构符合启动条件。这里的结构指以X为中心的部分树结构，可能包含P, S,GP, XL,XR,SL,SR。启动条件如下：

即：X和它的兄弟节点S为黑色，父亲节点P为红色。实现insert时我们做了一个特殊处理，构造了一个假的根节点，值为负无穷，颜色为黑色，因此所有的真实节点都在它的右子树上。它的左节点是一个null节点（黑色），右节点是真正的根节点（必然是黑色）。而自顶向下删除的第一步，就是把根节点涂成红色，这样就天然满足了启动条件

若X有两个黑色的节点。注意，当X为叶子节点时也适用，因为叶子节点的子节点为Null节点，是黑色

这时还需要考察S的子节点的情况才能决定如何变换，因此2还需要分几种子情形

2.1 符合2的条件，同时S也有两个黑色的子节点

这种情况是最简单的，让X变红只需要变换P，X，S的颜色即可。变换方法如下图

2.2 符合2的条件，且S有一个红色的左子节点，一个黑色的右子节点

这种情况下，X变红后，左边就少了一个黑色的节点，只能从P的右子树借一个过来。SL这个红色的节点可以利用起来，让它移到P现在的位置。显然这需要一个双旋转（SL位于整个旋转路径的内侧），变换如下：

2.3 符合2的条件，且S有一个黑色的左子节点，一个红色的右子节点

与2.2类似，我们要利用SR这个红色节点，因为SR在整个旋转路径的外侧，所以使用一个单旋转

在2的这三种情况完成变换之后，X已经是红色且保证了红黑树的性质，接下来就可以判断X是否为需要删除的节点了。这一步我们也标记一下，叫它D-1好了

D-1

如果X不是要删除的节点，那么下降一层，即让P = X, X = XL或者XR, S = X的另一个子节点，然后进入下一个删除循环（即1）。因为X是红色，它的子节点必然为黑色，所以符合启动条件

如果X正式需要删除的节点，需要分两种情况
1. X恰好是叶子节点，这种情况直接删除X即可，不会对红黑树的性质有任何影响
2. X为非叶子节点，如果直接删除X，它的子节点应该如何与它的父节点对接是个很复杂的操作，所以我们采用二叉查找树的节点删除方法：找到该节点的后继或前驱（如果后继不存在，再使用它的前驱节点），用它的值代替X的值，然后再去删除它的后继或前驱，反复这个过程直到我们需要删除的节点是叶子节点
ok，2这类大的情况就处理好了，下面需要考虑X有至少一个红色节点的情况

X至少有一个红色节点。这种情况需要改变一下思路，因为X有至少一个红色节点，如果X不是要删除的节点，就没必要再把X变红了，如果直接下降一层，X有很大概率直接落到红色的节点上，这能节省很多时间

所以对于3这种情况，先判断X是否为要删除的节点，这就分成两种情况

3.1 X不是要删除的节点，那么下降一层。这时X可能落到红色节点上，也可能落到黑色节点上，两种情况都需要考虑

3.1.1 X是红色节点，那么X已经符合D-1的删除条件，可以直接进入D-1

3.1.2 X是黑色节点，这时需要作一次节点变换。为了更直观，这里分成两个步骤，第一步下降一层，并让X落到黑色节点上，第二步才是变换

此时X还是黑色，并不满足进入D-1的条件，但是仔细看X节点的上下结构，P、SR、X构成的子树正好满足1的启动条件。所以下一步是进入1的删除循环

自此，3.1的所有情况已经处理好了，下面我们来看X是需要删除的节点这种情况

3.2 X是需要删除的节点。因为X有红色的子节点，所以它不可能是叶子节点，也就是说即使把它变红也不能直接删除。在这种情况下，我们在D-1的基础上稍作修改：找到X的后继或前驱，用它的值代替X的值，之后下降一层，再一次进入到3的逻辑

这就是自顶向下删除需要考虑的所有情形了。我画了一个流程图，梳理了删除的逻辑

按照这个流程图来写代码，会非常清晰~

源码

/** *  RedBlackTreeNode.js *  红黑树的节点实现，比普通的二叉树节点多了color属性 */class RedBlackTreeNode {    constructor(data, color, lchild, rchild) {        // validate color        if (!Color[color]) {            throw new Error(`color can only be RED or BLACK`);        }         this.color = color;        this.data = data;        this.lchild = lchild;        this.rchild = rchild;     } }const Color = {    "RED": "RED",    "BLACK": "BLACK"};module.exports = {    RedBlackTreeNode,    Color,};复制代码

/** * @file 红黑树实现 * @author YDSS * * Created on Sun May 27 2018 */const { RedBlackTreeNode, Color } = require("./RedBlackTreeNode");class RedBlackTree {    constructor(arr) {        this._initialize();        this.create(arr);    }    _initialize() {        // init NullNode        this.NullNode = new RedBlackTreeNode(            Number.NEGATIVE_INFINITY,            Color.BLACK,            null,            null        );        this.NullNode.lchild = this.NullNode;        this.NullNode.rchild = this.NullNode;        // extra attr for recognizing the NullNode        this.NullNode.type = "null";        // init header        this.header = new RedBlackTreeNode(            Number.NEGATIVE_INFINITY,            Color.BLACK,            this.NullNode,            this.NullNode        );        // init nodes to store parent, grandparent and grandgrandparent        this.X = null;        this.P = null;        this.GP = null;        this.GGP = null;        // X's sister        this.S = null;    }    create(arr) {        arr.forEach(item => {            this.header = this.insert(item);        });    }    find(val) {        return this._find(val, this.header);    }    _find(val, T) {        if (!T) {            return null;        }        if (val === T.data) {            return T;        }        if (val > T.data) {            return this._find(val, T.rchild);        }        if (val < T.data) {            return this._find(val, T.lchild);        }    }    insert(data) {        this.X = this.P = this.GP = this.GGP = this.header;        this.NullNode.data = data;        while (data !== this.X.data) {            this.GGP = this.GP;            this.GP = this.P;            this.P = this.X;            if (data < this.X.data) {                this.X = this.X.lchild;            } else {                this.X = this.X.rchild;            }            if (                this.X.lchild.color === Color.RED &&                this.X.rchild.color === Color.RED            )                this._handleReorient(data);        }        // duplicate        if (this.X !== this.NullNode) {            return this.NullNode;        }        this.X = new RedBlackTreeNode(            data,            Color.RED,            this.NullNode,            this.NullNode        );        if (data < this.P.data) {            this.P.lchild = this.X;        } else {            this.P.rchild = this.X;        }        this._handleReorient(data);        return this.header;    }    _handleReorient(data) {        this.X.color = Color.RED;        this.X.lchild.color = Color.BLACK;        this.X.rchild.color = Color.BLACK;        if (this.P.color === Color.RED) {            this.GP.color = Color.RED;            if (data < this.GP.data !== data < this.P.data)                this.P = this._rotate(data, this.GP);            this.X = this._rotate(data, this.GGP);            this.X.color = Color.BLACK;        }        this.header.rchild.color = Color.BLACK;    }    /**     * single rotate     *     * @param {*} data     * @param {RedBlackTreeNode} Parent Parent Node of the subtree will rotate     */    _rotate(data, Parent) {        if (data < Parent.data) {            return (Parent.lchild =                data < Parent.lchild.data                    ? this._singleRotateWithLeft(Parent.lchild)                    : this._singleRotateWithRight(Parent.lchild));        } else {            return (Parent.rchild =                data > Parent.rchild.data                    ? this._singleRotateWithRight(Parent.rchild)                    : this._singleRotateWithLeft(Parent.rchild));        }    }    _singleRotateWithLeft(T) {        let root = T.lchild;        T.lchild = root.rchild;        root.rchild = T;        return root;    }    _singleRotateWithRight(T) {        let root = T.rchild;        T.rchild = root.lchild;        root.lchild = T;        return root;    }    /**     * find precursor node of this node     *  if this node doesn't have the left subtree, return null     *     * @param {*} data data of current node     * @return {BinaryTreeNode|Null}     */    findPrecursor(node) {        // let node = this.find(data);        // if (!node) {
            //     throw new Error(`node with data(${data}) is not in the tree`);        // }        if (!node.lchild) {            return null;        }        let pre = node.lchild;        let tmp;        while (!this._isNilNode(tmp = pre.lchild)) {            pre = tmp;        }        return pre;    }    /**     * find successor node of this node     *  if this node doesn't have the right subtree, return null     *     * @param {BinaryTreeNode} current node     * @return {BinaryTreeNode|Null}     */    findSuccessor(node) {        // let node = this.find(data);        // if (!node) {
            //     throw new Error(`node with data(${data}) is not in the tree`);        // }        if (!node.rchild) {            return null;        }        let suc = node.rchild;        let tmp;        while (!this._isNilNode(tmp = suc.lchild)) {            suc = tmp;        }        return suc;    }    /**     * delete node by means of top to down     *      * @param {*} val      */    delete(val) {        // prepare for deleting        this.header.color = Color.RED;        this.GP = null;        this.P = this.header;        this.X = this.header.rchild;        this.S = this.header.lchild;        this._delete(val);    }    _delete(val) {        if (            this.X.lchild.color === Color.BLACK &&            this.X.rchild.color === Color.BLACK        ) {            // S has two black children            if (                this.S.lchild.color === Color.BLACK &&                this.S.rchild.color === Color.BLACK            ) {                this._handleRotateSisterWithTwoBlackChildren();                // judge if X.data is what we are looking for                this._handleDeleteXWhenXhasTwoBlackChildren(val);            }            // S has at last one red children            else {                // single rotate when S with it's red child in a line,                // reference to avl rotate                // 2.3                if (                    this.S.data > this.P.data ===                    (this.S.rchild.color === Color.RED)                ) {                    this._rotate(this.S.data, this.GP);                    // change color                    this.P.color = Color.BLACK;                    this.X.color = Color.RED;                    this.S.color = Color.RED;                    this.S.lchild.color = Color.BLACK;                    this.S.rchild.color = Color.BLACK;                    // judge if X.data is what we are looking for                    this._handleDeleteXWhenXhasTwoBlackChildren(val);                    // double rotate when S with it's red child in a z-shape line                    // 2.2                } else {                    let firstData =                        this.S.data < this.P.data                            ? this.S.rchild.data                            : this.S.lchild.data;                    this._rotate(firstData, this.P);                    this._rotate(this.S.data, this.GP);                    // change color                    this.P.color = Color.BLACK;                    this.X.color = Color.RED;                    // judge if X.data is what we are looking for                    this._handleDeleteXWhenXhasTwoBlackChildren(val);                }            }        } else {            this._handleDeleteXWhenXhasAtLastOneRedChild(val);        }    }    // 2.1    _handleRotateSisterWithTwoBlackChildren() {        this.P.color = Color.BLACK;        this.X.color = Color.RED;        this.S.color = Color.RED;    }    _handleDeleteXWhenXhasTwoBlackChildren(val) {        if (this.X.data === val) {            if (this._hasChild(this.X)) {                val = this._replaceWithSuccessorOrPrecursor(val);                this._descend(val);                this._delete(val);            } else {                // delete X when it's a leaf                this._deleteLeafNode(val, this.P);            }        } else {            this._descend(val);            this._delete(val);        }    }    _handleDeleteXWhenXhasAtLastOneRedChild(val) {        if (this.X.data === val) {            val = this._replaceWithSuccessorOrPrecursor(val);            this._descend(val);        } else {            this._descend(val);        }        // X is red, enter the phase of judging X's data        if (this.X.color === Color.RED) {            this._handleDeleteXWhenXhasTwoBlackChildren(val);        } else {            this._handleRotateWhenXIsBlackAndSisterIsRed();            this._delete(val);        }    }    // 3.1.2    _handleRotateWhenXIsBlackAndSisterIsRed() {        let curGP = this._rotate(this.S.data, this.GP);        // change color        this.S.color = Color.BLACK;        this.P.color = Color.RED;        // fix pointer of S and GP        this.S = this.X.data > this.P.data ? this.P.lchild : this.P.rchild;        this.GP = curGP;    }    _deleteLeafNode(val, parent) {        if (parent.rchild.data === val) {            parent.rchild = this.NullNode;        } else {            parent.lchild = this.NullNode;        }    }    _hasChild(node) {        return !this._isNilNode(node.lchild) || !this._isNilNode(node.rchild);    }    _isNilNode(node) {        return node === this.NullNode;    }    /**     * replace X with it's successor,     *  if it has no successor, instead of it's precursor     * @param {*} val the delete data     *     * @return {*} updated delete data     */    _replaceWithSuccessorOrPrecursor(val) {        let child = this.findSuccessor(this.X);        if (!child) {            child = this.findPrecursor(this.X);        }        this.X.data = child.data;        return child.data;    }    /**     * descend one floor     *     * @param {*} val the val of node will be deleted     */    _descend(val) {        this.GP = this.P;        this.P = this.X;        if (val < this.X.data) {            this.S = this.X.rchild;            this.X = this.X.lchild;        } else if (val > this.X.data) {            this.S = this.X.lchild;            this.X = this.X.rchild;        }        // val === this.X.data when X's successor or precursor        //  is it's child, in this situation it's wrong to choise        //  where X to go down by comparing val, cause X.data is equal        //  with new delete value        else {            if (val === this.X.lchild) {                this.S = this.X.rchild;                this.X = this.X.lchild;            }            else {                this.S = this.X.lchild;                this.X = this.X.rchild;            }        }    }}module.exports = RedBlackTree;复制代码