数据结构之红黑树

xiaoxiao2023-12-01 156
2-3树和红黑树相关学习：
  
 红黑树和2-3树本身是等价的,在学习红黑树之前我们不妨去了解一下2-3树的特性。当我们理解了2-3树之后，对于红黑树和通常用于磁盘存储，文件系统，数据库相应的B类树也是有帮助的。
2-3树2-3树是最简单的B-树（或-树）结构，其每个非叶节点都有两个或三个子女，而且所有叶都在统一层上。2-3树不是二叉树(满足二分搜索树的基本性质)，其节点可拥有3个孩子。不过，2-3树与满二叉树相似。高为h的2-3树包含的节点数大于等于高度为h的满二叉树的节点数，即至少有2^h-1个节点。
b的左孩子点小于b的值，bc中间的值再bc之间，c的右孩子的值大于c。
2-3树是一颗绝对平衡的树：从根节点到任意一个节点所经过的节点数量一定是相同的
插入如果插入2-节点那么
如果插入3-节点
如果插入3-节点，父亲节点为2-节点的话
如果插入3-节点，父亲节点也为3-节点
红黑树红黑树（英语：Red–black tree）是一种自平衡二叉查找树，计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它在1972年由鲁道夫·贝尔发明，被称为对称二叉B树，它现代的名字源于LeoJ. Guibas和Robert Sedgewick于1978年写的一篇论文。红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间，并且在实践中高效：它可以在 $\mathrm{O}(\log n)$时间内完成查找，插入和删除，这里的$n$是树中元素的数目。
性质
 节点是红色或黑色。根是黑色。所有叶子都是黑色（叶子是NIL节点）。每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
 
Java实现红黑树的基本操作是添加、删除和旋转。在对红黑树进行添加或删除后，会用到旋转方法。添加或删除红黑树中的节点之后，红黑树就发生了变化，可能不满足红黑树的5条性质，也就不再是一颗红黑树了，而是一颗普通的树。而通过旋转，可以使这颗树重新成为红黑树，旋转的目的是让树保持红黑树的特性。旋转包括两种：左旋 和 右旋。
基本定义12345678910111213141516171819202122232425public class RBTree<T extends Comparable<T>> {    private RBTNode<T> mRoot;    // 根结点    private static final boolean RED   = false;    private static final boolean BLACK = true;    public class RBTNode<T extends Comparable<T>> {        boolean color;        // 颜色        T key;                // 关键字(键值)        RBTNode<T> left;    // 左孩子        RBTNode<T> right;    // 右孩子        RBTNode<T> parent;    // 父结点        public RBTNode(T key, boolean color, RBTNode<T> parent, RBTNode<T> left, RBTNode<T> right) {            this.key = key;            this.color = color;            this.parent = parent;            this.left = left;            this.right = right;        }    }    ...}左旋
对x进行左旋，意味着”将x变成一个左节点”。
1234567891011121314151617181920212223242526272829303132333435363738394041/*  * 对红黑树的节点(x)进行左旋转 * * 左旋示意图(对节点x进行左旋)： *      px                              px *     /                               / *    x                               y                 *   /  \      --(左旋)-.           / \                # *  lx   y                          x  ry      *     /   \                       /  \ *    ly   ry                     lx  ly   * * */private void leftRotate(RBTNode<T> x) {    // 设置x的右孩子为y    RBTNode<T> y = x.right;    // 将 “y的左孩子” 设为 “x的右孩子”；    // 如果y的左孩子非空，将 “x” 设为 “y的左孩子的父亲”    x.right = y.left;    if (y.left != null)        y.left.parent = x;    // 将 “x的父亲” 设为 “y的父亲”    y.parent = x.parent;    if (x.parent == null) {        this.mRoot = y;            // 如果 “x的父亲” 是空节点，则将y设为根节点    } else {        if (x.parent.left == x)            x.parent.left = y;    // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”        else            x.parent.right = y;    // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”    }        // 将 “x” 设为 “y的左孩子”    y.left = x;    // 将 “x的父节点” 设为 “y”    x.parent = y;}右旋
对y进行左旋，意味着”将y变成一个右节点”。
1234567891011121314151617181920212223242526272829303132333435363738394041/*  * 对红黑树的节点(y)进行右旋转 * * 右旋示意图(对节点y进行左旋)： *            py                               py *           /                                / *          y                                x                   *         /  \      --(右旋)-.            /  \                     # *        x   ry                           lx   y   *       / \                                   / \                   # *      lx  rx                                rx  ry *  */private void rightRotate(RBTNode<T> y) {    // 设置x是当前节点的左孩子。    RBTNode<T> x = y.left;    // 将 “x的右孩子” 设为 “y的左孩子”；    // 如果"x的右孩子"不为空的话，将 “y” 设为 “x的右孩子的父亲”    y.left = x.right;    if (x.right != null)        x.right.parent = y;    // 将 “y的父亲” 设为 “x的父亲”    x.parent = y.parent;    if (y.parent == null) {        this.mRoot = x;            // 如果 “y的父亲” 是空节点，则将x设为根节点    } else {        if (y == y.parent.right)            y.parent.right = x;    // 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子”        else            y.parent.left = x;    // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”    }    // 将 “y” 设为 “x的右孩子”    x.right = y;    // 将 “y的父节点” 设为 “x”    y.parent = x;}添加将一个节点插入到红黑树中，需要执行哪些步骤呢？首先，将红黑树当作一颗二叉查找树，将节点插入；然后，将节点着色为红色；最后，通过”旋转和重新着色”等一系列操作来修正该树，使之重新成为一颗红黑树。详细描述如下：第一步: 将红黑树当作一颗二叉查找树，将节点插入。 红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。也就意味着，树的键值仍然是有序的。此外，无论是左旋还是右旋，若旋转之前这棵树是二叉查找树，旋转之后它一定还是二叉查找树。这也就意味着，任何的旋转和重新着色操作，都不会改变它仍然是一颗二叉查找树的事实。好吧？那接下来，我们就来想方设法的旋转以及重新着色，使这颗树重新成为红黑树！
第二步：将插入的节点着色为”红色”。 为什么着色成红色，而不是黑色呢？为什么呢？在回答之前，我们需要重新温习一下红黑树的特性：(1) 每个节点或者是黑色，或者是红色。(2) 根节点是黑色。(3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！](4) 如果一个节点是红色的，则它的子节点必须是黑色的。(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。 将插入的节点着色为红色，不会违背”特性(5)”！少违背一条特性，就意味着我们需要处理的情况越少。接下来，就要努力的让这棵树满足其它性质即可；满足了的话，它就又是一颗红黑树了。o(∩∩)o…哈哈
第三步: 通过一系列的旋转或着色等操作，使之重新成为一颗红黑树。 第二步中，将插入节点着色为”红色”之后，不会违背”特性(5)”。那它到底会违背哪些特性呢？ 对于”特性(1)”，显然不会违背了。因为我们已经将它涂成红色了。 对于”特性(2)”，显然也不会违背。在第一步中，我们是将红黑树当作二叉查找树，然后执行的插入操作。而根据二叉查找数的特点，插入操作不会改变根节点。所以，根节点仍然是黑色。 对于”特性(3)”，显然不会违背了。这里的叶子节点是指的空叶子节点，插入非空节点并不会对它们造成影响。 对于”特性(4)”，是有可能违背的！ 那接下来，想办法使之”满足特性(4)”，就可以将树重新构造成红黑树了。
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152/*  * 将结点插入到红黑树中 * * 参数说明： *     node 插入的结点        // 对应《算法导论》中的node */private void insert(RBTNode<T> node) {    int cmp;    RBTNode<T> y = null;    RBTNode<T> x = this.mRoot;    // 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。    while (x != null) {        y = x;        cmp = node.key.compareTo(x.key);        if (cmp < 0)            x = x.left;        else            x = x.right;    }    node.parent = y;    if (y!=null) {        cmp = node.key.compareTo(y.key);        if (cmp < 0)            y.left = node;        else            y.right = node;    } else {        this.mRoot = node;    }    // 2. 设置节点的颜色为红色    node.color = RED;    // 3. 将它重新修正为一颗二叉查找树    insertFixUp(node);}/*  * 新建结点(key)，并将其插入到红黑树中 * * 参数说明： *     key 插入结点的键值 */public void insert(T key) {    RBTNode<T> node=new RBTNode<T>(key,BLACK,null,null,null);    // 如果新建结点失败，则返回。    if (node != null)        insert(node);}内部接口 — insert(node)的作用是将”node”节点插入到红黑树中。外部接口 — insert(key)的作用是将”key”添加到红黑树中。
平衡1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071/* * 红黑树插入修正函数 * * 在向红黑树中插入节点之后(失去平衡)，再调用该函数； * 目的是将它重新塑造成一颗红黑树。 * * 参数说明： *     node 插入的结点        // 对应《算法导论》中的z */private void insertFixUp(RBTNode<T> node) {    RBTNode<T> parent, gparent;    // 若“父节点存在，并且父节点的颜色是红色”    while (((parent = parentOf(node))!=null) && isRed(parent)) {        gparent = parentOf(parent);        //若“父节点”是“祖父节点的左孩子”        if (parent == gparent.left) {            // Case 1条件：叔叔节点是红色            RBTNode<T> uncle = gparent.right;            if ((uncle!=null) && isRed(uncle)) {                setBlack(uncle);                setBlack(parent);                setRed(gparent);                node = gparent;                continue;            }            // Case 2条件：叔叔是黑色，且当前节点是右孩子            if (parent.right == node) {                RBTNode<T> tmp;                leftRotate(parent);                tmp = parent;                parent = node;                node = tmp;            }            // Case 3条件：叔叔是黑色，且当前节点是左孩子。            setBlack(parent);            setRed(gparent);            rightRotate(gparent);        } else {    //若“z的父节点”是“z的祖父节点的右孩子”            // Case 1条件：叔叔节点是红色            RBTNode<T> uncle = gparent.left;            if ((uncle!=null) && isRed(uncle)) {                setBlack(uncle);                setBlack(parent);                setRed(gparent);                node = gparent;                continue;            }            // Case 2条件：叔叔是黑色，且当前节点是左孩子            if (parent.left == node) {                RBTNode<T> tmp;                rightRotate(parent);                tmp = parent;                parent = node;                node = tmp;            }            // Case 3条件：叔叔是黑色，且当前节点是右孩子。            setBlack(parent);            setRed(gparent);            leftRotate(gparent);        }    }    // 将根节点设为黑色    setBlack(this.mRoot);}删除将红黑树内的某一个节点删除。需要执行的操作依次是：首先，将红黑树当作一颗二叉查找树，将该节点从二叉查找树中删除；然后，通过”旋转和重新着色”等一系列来修正该树，使之重新成为一棵红黑树。详细描述如下：第一步：将红黑树当作一颗二叉查找树，将节点删除。 这和”删除常规二叉查找树中删除节点的方法是一样的”。分3种情况：① 被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就OK了。② 被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。③ 被删除节点有两个儿子。那么，先找出它的后继节点；然后把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。在这里，后继节点相当于替身，在将后继节点的内容复制给”被删除节点”之后，再将后继节点删除。这样就巧妙的将问题转换为”删除后继节点”的情况了，下面就考虑后继节点。 在”被删除节点”有两个非空子节点的情况下，它的后继节点不可能是双子非空。既然”的后继节点”不可能双子都非空，就意味着”该节点的后继节点”要么没有儿子，要么只有一个儿子。若没有儿子，则按”情况① “进行处理；若只有一个儿子，则按”情况② “进行处理。
第二步：通过”旋转和重新着色”等一系列来修正该树，使之重新成为一棵红黑树。 因为”第一步”中删除节点之后，可能会违背红黑树的特性。所以需要通过”旋转和重新着色”来修正该树，使之重新成为一棵红黑树
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105/*  * 删除结点(node)，并返回被删除的结点 * * 参数说明： *     node 删除的结点 */private void remove(RBTNode<T> node) {    RBTNode<T> child, parent;    boolean color;    // 被删除节点的"左右孩子都不为空"的情况。    if ( (node.left!=null) && (node.right!=null) ) {        // 被删节点的后继节点。(称为"取代节点")        // 用它来取代"被删节点"的位置，然后再将"被删节点"去掉。        RBTNode<T> replace = node;        // 获取后继节点        replace = replace.right;        while (replace.left != null)            replace = replace.left;        // "node节点"不是根节点(只有根节点不存在父节点)        if (parentOf(node)!=null) {            if (parentOf(node).left == node)                parentOf(node).left = replace;            else                parentOf(node).right = replace;        } else {            // "node节点"是根节点，更新根节点。            this.mRoot = replace;        }        // child是"取代节点"的右孩子，也是需要"调整的节点"。        // "取代节点"肯定不存在左孩子！因为它是一个后继节点。        child = replace.right;        parent = parentOf(replace);        // 保存"取代节点"的颜色        color = colorOf(replace);        // "被删除节点"是"它的后继节点的父节点"        if (parent == node) {            parent = replace;        } else {            // child不为空            if (child!=null)                setParent(child, parent);            parent.left = child;            replace.right = node.right;            setParent(node.right, replace);        }        replace.parent = node.parent;        replace.color = node.color;        replace.left = node.left;        node.left.parent = replace;        if (color == BLACK)            removeFixUp(child, parent);        node = null;        return ;    }    if (node.left !=null) {        child = node.left;    } else {        child = node.right;    }    parent = node.parent;    // 保存"取代节点"的颜色    color = node.color;    if (child!=null)        child.parent = parent;    // "node节点"不是根节点    if (parent!=null) {        if (parent.left == node)            parent.left = child;        else            parent.right = child;    } else {        this.mRoot = child;    }    if (color == BLACK)        removeFixUp(child, parent);    node = null;}/*  * 删除结点(z)，并返回被删除的结点 * * 参数说明： *     tree 红黑树的根结点 *     z 删除的结点 */public void remove(T key) {    RBTNode<T> node;     if ((node = search(mRoot, key)) != null)        remove(node);}内部接口 — remove(node)的作用是将”node”节点插入到红黑树中。外部接口 — remove(key)删除红黑树中键值为key的节点。
平衡123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687/* * 红黑树删除修正函数 * * 在从红黑树中删除插入节点之后(红黑树失去平衡)，再调用该函数； * 目的是将它重新塑造成一颗红黑树。 * * 参数说明： *     node 待修正的节点 */private void removeFixUp(RBTNode<T> node, RBTNode<T> parent) {    RBTNode<T> other;    while ((node==null || isBlack(node)) && (node != this.mRoot)) {        if (parent.left == node) {            other = parent.right;            if (isRed(other)) {                // Case 1: x的兄弟w是红色的                  setBlack(other);                setRed(parent);                leftRotate(parent);                other = parent.right;            }            if ((other.left==null || isBlack(other.left)) &&                (other.right==null || isBlack(other.right))) {                // Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的                  setRed(other);                node = parent;                parent = parentOf(node);            } else {                if (other.right==null || isBlack(other.right)) {                    // Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。                      setBlack(other.left);                    setRed(other);                    rightRotate(other);                    other = parent.right;                }                // Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。                setColor(other, colorOf(parent));                setBlack(parent);                setBlack(other.right);                leftRotate(parent);                node = this.mRoot;                break;            }        } else {            other = parent.left;            if (isRed(other)) {                // Case 1: x的兄弟w是红色的                  setBlack(other);                setRed(parent);                rightRotate(parent);                other = parent.left;            }            if ((other.left==null || isBlack(other.left)) &&                (other.right==null || isBlack(other.right))) {                // Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的                  setRed(other);                node = parent;                parent = parentOf(node);            } else {                if (other.left==null || isBlack(other.left)) {                    // Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。                      setBlack(other.right);                    setRed(other);                    leftRotate(other);                    other = parent.left;                }                // Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。                setColor(other, colorOf(parent));                setBlack(parent);                setBlack(other.left);                rightRotate(parent);                node = this.mRoot;                break;            }        }    }    if (node!=null)        setBlack(node);}removeFixup(node, parent)是对应”上面所讲的第三步”。它是一个内部接口。
完整代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692/** * Java 语言: 红黑树 * * @author skywang * @date 2013/11/07 */public class RBTree<T extends Comparable<T>> {    private RBTNode<T> mRoot;    // 根结点    private static final boolean RED   = false;    private static final boolean BLACK = true;    public class RBTNode<T extends Comparable<T>> {        boolean color;        // 颜色        T key;                // 关键字(键值)        RBTNode<T> left;    // 左孩子        RBTNode<T> right;    // 右孩子        RBTNode<T> parent;    // 父结点        public RBTNode(T key, boolean color, RBTNode<T> parent, RBTNode<T> left, RBTNode<T> right) {            this.key = key;            this.color = color;            this.parent = parent;            this.left = left;            this.right = right;        }        public T getKey() {            return key;        }        public String toString() {            return ""+key+(this.color==RED?"(R)":"B");        }    }    public RBTree() {        mRoot=null;    }    private RBTNode<T> parentOf(RBTNode<T> node) {        return node!=null ? node.parent : null;    }    private boolean colorOf(RBTNode<T> node) {        return node!=null ? node.color : BLACK;    }    private boolean isRed(RBTNode<T> node) {        return ((node!=null)&&(node.color==RED)) ? true : false;    }    private boolean isBlack(RBTNode<T> node) {        return !isRed(node);    }    private void setBlack(RBTNode<T> node) {        if (node!=null)            node.color = BLACK;    }    private void setRed(RBTNode<T> node) {        if (node!=null)            node.color = RED;    }    private void setParent(RBTNode<T> node, RBTNode<T> parent) {        if (node!=null)            node.parent = parent;    }    private void setColor(RBTNode<T> node, boolean color) {        if (node!=null)            node.color = color;    }    /*     * 前序遍历"红黑树"     */    private void preOrder(RBTNode<T> tree) {        if(tree != null) {            System.out.print(tree.key+" ");            preOrder(tree.left);            preOrder(tree.right);        }    }    public void preOrder() {        preOrder(mRoot);    }    /*     * 中序遍历"红黑树"     */    private void inOrder(RBTNode<T> tree) {        if(tree != null) {            inOrder(tree.left);            System.out.print(tree.key+" ");            inOrder(tree.right);        }    }    public void inOrder() {        inOrder(mRoot);    }    /*     * 后序遍历"红黑树"     */    private void postOrder(RBTNode<T> tree) {        if(tree != null)        {            postOrder(tree.left);            postOrder(tree.right);            System.out.print(tree.key+" ");        }    }    public void postOrder() {        postOrder(mRoot);    }    /*     * (递归实现)查找"红黑树x"中键值为key的节点     */    private RBTNode<T> search(RBTNode<T> x, T key) {        if (x==null)            return x;        int cmp = key.compareTo(x.key);        if (cmp < 0)            return search(x.left, key);        else if (cmp > 0)            return search(x.right, key);        else            return x;    }    public RBTNode<T> search(T key) {        return search(mRoot, key);    }    /*     * (非递归实现)查找"红黑树x"中键值为key的节点     */    private RBTNode<T> iterativeSearch(RBTNode<T> x, T key) {        while (x!=null) {            int cmp = key.compareTo(x.key);            if (cmp < 0)                 x = x.left;            else if (cmp > 0)                 x = x.right;            else                return x;        }        return x;    }    public RBTNode<T> iterativeSearch(T key) {        return iterativeSearch(mRoot, key);    }    /*      * 查找最小结点：返回tree为根结点的红黑树的最小结点。     */    private RBTNode<T> minimum(RBTNode<T> tree) {        if (tree == null)            return null;        while(tree.left != null)            tree = tree.left;        return tree;    }    public T minimum() {        RBTNode<T> p = minimum(mRoot);        if (p != null)            return p.key;        return null;    }         /*      * 查找最大结点：返回tree为根结点的红黑树的最大结点。     */    private RBTNode<T> maximum(RBTNode<T> tree) {        if (tree == null)            return null;        while(tree.right != null)            tree = tree.right;        return tree;    }    public T maximum() {        RBTNode<T> p = maximum(mRoot);        if (p != null)            return p.key;        return null;    }    /*      * 找结点(x)的后继结点。即，查找"红黑树中数据值大于该结点"的"最小结点"。     */    public RBTNode<T> successor(RBTNode<T> x) {        // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。        if (x.right != null)            return minimum(x.right);        // 如果x没有右孩子。则x有以下两种可能：        // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。        // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。        RBTNode<T> y = x.parent;        while ((y!=null) && (x==y.right)) {            x = y;            y = y.parent;        }        return y;    }         /*      * 找结点(x)的前驱结点。即，查找"红黑树中数据值小于该结点"的"最大结点"。     */    public RBTNode<T> predecessor(RBTNode<T> x) {        // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。        if (x.left != null)            return maximum(x.left);        // 如果x没有左孩子。则x有以下两种可能：        // (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。        // (01) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。        RBTNode<T> y = x.parent;        while ((y!=null) && (x==y.left)) {            x = y;            y = y.parent;        }        return y;    }    /*      * 对红黑树的节点(x)进行左旋转     *     * 左旋示意图(对节点x进行左旋)：     *      px                              px     *     /                               /     *    x                               y                     *   /  \      --(左旋)-.           / \                #     *  lx   y                          x  ry          *     /   \                       /  \     *    ly   ry                     lx  ly       *     *     */    private void leftRotate(RBTNode<T> x) {        // 设置x的右孩子为y        RBTNode<T> y = x.right;        // 将 “y的左孩子” 设为 “x的右孩子”；        // 如果y的左孩子非空，将 “x” 设为 “y的左孩子的父亲”        x.right = y.left;        if (y.left != null)            y.left.parent = x;        // 将 “x的父亲” 设为 “y的父亲”        y.parent = x.parent;        if (x.parent == null) {            this.mRoot = y;            // 如果 “x的父亲” 是空节点，则将y设为根节点        } else {            if (x.parent.left == x)                x.parent.left = y;    // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”            else                x.parent.right = y;    // 如果 x是它父节点的左孩子，则将y设为“x的父节点的左孩子”        }                // 将 “x” 设为 “y的左孩子”        y.left = x;        // 将 “x的父节点” 设为 “y”        x.parent = y;    }    /*      * 对红黑树的节点(y)进行右旋转     *     * 右旋示意图(对节点y进行左旋)：     *            py                               py     *           /                                /     *          y                                x                       *         /  \      --(右旋)-.            /  \                     #     *        x   ry                           lx   y       *       / \                                   / \                   #     *      lx  rx                                rx  ry     *      */    private void rightRotate(RBTNode<T> y) {        // 设置x是当前节点的左孩子。        RBTNode<T> x = y.left;        // 将 “x的右孩子” 设为 “y的左孩子”；        // 如果"x的右孩子"不为空的话，将 “y” 设为 “x的右孩子的父亲”        y.left = x.right;        if (x.right != null)            x.right.parent = y;        // 将 “y的父亲” 设为 “x的父亲”        x.parent = y.parent;        if (y.parent == null) {            this.mRoot = x;            // 如果 “y的父亲” 是空节点，则将x设为根节点        } else {            if (y == y.parent.right)                y.parent.right = x;    // 如果 y是它父节点的右孩子，则将x设为“y的父节点的右孩子”            else                y.parent.left = x;    // (y是它父节点的左孩子) 将x设为“x的父节点的左孩子”        }        // 将 “y” 设为 “x的右孩子”        x.right = y;        // 将 “y的父节点” 设为 “x”        y.parent = x;    }    /*     * 红黑树插入修正函数     *     * 在向红黑树中插入节点之后(失去平衡)，再调用该函数；     * 目的是将它重新塑造成一颗红黑树。     *     * 参数说明：     *     node 插入的结点        // 对应《算法导论》中的z     */    private void insertFixUp(RBTNode<T> node) {        RBTNode<T> parent, gparent;        // 若“父节点存在，并且父节点的颜色是红色”        while (((parent = parentOf(node))!=null) && isRed(parent)) {            gparent = parentOf(parent);            //若“父节点”是“祖父节点的左孩子”            if (parent == gparent.left) {                // Case 1条件：叔叔节点是红色                RBTNode<T> uncle = gparent.right;                if ((uncle!=null) && isRed(uncle)) {                    setBlack(uncle);                    setBlack(parent);                    setRed(gparent);                    node = gparent;                    continue;                }                // Case 2条件：叔叔是黑色，且当前节点是右孩子                if (parent.right == node) {                    RBTNode<T> tmp;                    leftRotate(parent);                    tmp = parent;                    parent = node;                    node = tmp;                }                // Case 3条件：叔叔是黑色，且当前节点是左孩子。                setBlack(parent);                setRed(gparent);                rightRotate(gparent);            } else {    //若“z的父节点”是“z的祖父节点的右孩子”                // Case 1条件：叔叔节点是红色                RBTNode<T> uncle = gparent.left;                if ((uncle!=null) && isRed(uncle)) {                    setBlack(uncle);                    setBlack(parent);                    setRed(gparent);                    node = gparent;                    continue;                }                // Case 2条件：叔叔是黑色，且当前节点是左孩子                if (parent.left == node) {                    RBTNode<T> tmp;                    rightRotate(parent);                    tmp = parent;                    parent = node;                    node = tmp;                }                // Case 3条件：叔叔是黑色，且当前节点是右孩子。                setBlack(parent);                setRed(gparent);                leftRotate(gparent);            }        }        // 将根节点设为黑色        setBlack(this.mRoot);    }    /*      * 将结点插入到红黑树中     *     * 参数说明：     *     node 插入的结点        // 对应《算法导论》中的node     */    private void insert(RBTNode<T> node) {        int cmp;        RBTNode<T> y = null;        RBTNode<T> x = this.mRoot;        // 1. 将红黑树当作一颗二叉查找树，将节点添加到二叉查找树中。        while (x != null) {            y = x;            cmp = node.key.compareTo(x.key);            if (cmp < 0)                x = x.left;            else                x = x.right;        }        node.parent = y;        if (y!=null) {            cmp = node.key.compareTo(y.key);            if (cmp < 0)                y.left = node;            else                y.right = node;        } else {            this.mRoot = node;        }        // 2. 设置节点的颜色为红色        node.color = RED;        // 3. 将它重新修正为一颗二叉查找树        insertFixUp(node);    }    /*      * 新建结点(key)，并将其插入到红黑树中     *     * 参数说明：     *     key 插入结点的键值     */    public void insert(T key) {        RBTNode<T> node=new RBTNode<T>(key,BLACK,null,null,null);        // 如果新建结点失败，则返回。        if (node != null)            insert(node);    }    /*     * 红黑树删除修正函数     *     * 在从红黑树中删除插入节点之后(红黑树失去平衡)，再调用该函数；     * 目的是将它重新塑造成一颗红黑树。     *     * 参数说明：     *     node 待修正的节点     */    private void removeFixUp(RBTNode<T> node, RBTNode<T> parent) {        RBTNode<T> other;        while ((node==null || isBlack(node)) && (node != this.mRoot)) {            if (parent.left == node) {                other = parent.right;                if (isRed(other)) {                    // Case 1: x的兄弟w是红色的                      setBlack(other);                    setRed(parent);                    leftRotate(parent);                    other = parent.right;                }                if ((other.left==null || isBlack(other.left)) &&                    (other.right==null || isBlack(other.right))) {                    // Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的                      setRed(other);                    node = parent;                    parent = parentOf(node);                } else {                    if (other.right==null || isBlack(other.right)) {                        // Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。                          setBlack(other.left);                        setRed(other);                        rightRotate(other);                        other = parent.right;                    }                    // Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。                    setColor(other, colorOf(parent));                    setBlack(parent);                    setBlack(other.right);                    leftRotate(parent);                    node = this.mRoot;                    break;                }            } else {                other = parent.left;                if (isRed(other)) {                    // Case 1: x的兄弟w是红色的                      setBlack(other);                    setRed(parent);                    rightRotate(parent);                    other = parent.left;                }                if ((other.left==null || isBlack(other.left)) &&                    (other.right==null || isBlack(other.right))) {                    // Case 2: x的兄弟w是黑色，且w的俩个孩子也都是黑色的                      setRed(other);                    node = parent;                    parent = parentOf(node);                } else {                    if (other.left==null || isBlack(other.left)) {                        // Case 3: x的兄弟w是黑色的，并且w的左孩子是红色，右孩子为黑色。                          setBlack(other.right);                        setRed(other);                        leftRotate(other);                        other = parent.left;                    }                    // Case 4: x的兄弟w是黑色的；并且w的右孩子是红色的，左孩子任意颜色。                    setColor(other, colorOf(parent));                    setBlack(parent);                    setBlack(other.left);                    rightRotate(parent);                    node = this.mRoot;                    break;                }            }        }        if (node!=null)            setBlack(node);    }    /*      * 删除结点(node)，并返回被删除的结点     *     * 参数说明：     *     node 删除的结点     */    private void remove(RBTNode<T> node) {        RBTNode<T> child, parent;        boolean color;        // 被删除节点的"左右孩子都不为空"的情况。        if ( (node.left!=null) && (node.right!=null) ) {            // 被删节点的后继节点。(称为"取代节点")            // 用它来取代"被删节点"的位置，然后再将"被删节点"去掉。            RBTNode<T> replace = node;            // 获取后继节点            replace = replace.right;            while (replace.left != null)                replace = replace.left;            // "node节点"不是根节点(只有根节点不存在父节点)            if (parentOf(node)!=null) {                if (parentOf(node).left == node)                    parentOf(node).left = replace;                else                    parentOf(node).right = replace;            } else {                // "node节点"是根节点，更新根节点。                this.mRoot = replace;            }            // child是"取代节点"的右孩子，也是需要"调整的节点"。            // "取代节点"肯定不存在左孩子！因为它是一个后继节点。            child = replace.right;            parent = parentOf(replace);            // 保存"取代节点"的颜色            color = colorOf(replace);            // "被删除节点"是"它的后继节点的父节点"            if (parent == node) {                parent = replace;            } else {                // child不为空                if (child!=null)                    setParent(child, parent);                parent.left = child;                replace.right = node.right;                setParent(node.right, replace);            }            replace.parent = node.parent;            replace.color = node.color;            replace.left = node.left;            node.left.parent = replace;            if (color == BLACK)                removeFixUp(child, parent);            node = null;            return ;        }        if (node.left !=null) {            child = node.left;        } else {            child = node.right;        }        parent = node.parent;        // 保存"取代节点"的颜色        color = node.color;        if (child!=null)            child.parent = parent;        // "node节点"不是根节点        if (parent!=null) {            if (parent.left == node)                parent.left = child;            else                parent.right = child;        } else {            this.mRoot = child;        }        if (color == BLACK)            removeFixUp(child, parent);        node = null;    }    /*      * 删除结点(z)，并返回被删除的结点     *     * 参数说明：     *     tree 红黑树的根结点     *     z 删除的结点     */    public void remove(T key) {        RBTNode<T> node;         if ((node = search(mRoot, key)) != null)            remove(node);    }    /*     * 销毁红黑树     */    private void destroy(RBTNode<T> tree) {        if (tree==null)            return ;        if (tree.left != null)            destroy(tree.left);        if (tree.right != null)            destroy(tree.right);        tree=null;    }    public void clear() {        destroy(mRoot);        mRoot = null;    }    /*     * 打印"红黑树"     *     * key        -- 节点的键值      * direction  --  0，表示该节点是根节点;     *               -1，表示该节点是它的父结点的左孩子;     *                1，表示该节点是它的父结点的右孩子。     */    private void print(RBTNode<T> tree, T key, int direction) {        if(tree != null) {            if(direction==0)    // tree是根节点                System.out.printf("-(B) is root\n", tree.key);            else                // tree是分支节点                System.out.printf("-(%s) is -'s %6s child\n", tree.key, isRed(tree)?"R":"B", key, direction==1?"right" : "left");            print(tree.left, tree.key, -1);            print(tree.right,tree.key,  1);        }    }    public void print() {        if (mRoot != null)            print(mRoot, mRoot.key, 0);    }}测试12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364/** * Java 语言: 二叉查找树 * * @author skywang * @date 2013/11/07 */public class RBTreeTest {    private static final int a[] = {10, 40, 30, 60, 90, 70, 20, 50, 80};    private static final boolean mDebugInsert = false;    // "插入"动作的检测开关(false，关闭；true，打开)    private static final boolean mDebugDelete = false;    // "删除"动作的检测开关(false，关闭；true，打开)    public static void main(String[] args) {        int i, ilen = a.length;        RBTree<Integer> tree=new RBTree<Integer>();        System.out.printf("== 原始数据: ");        for(i=0; i<ilen; i++)            System.out.printf("%d ", a[i]);        System.out.printf("\n");        for(i=0; i<ilen; i++) {            tree.insert(a[i]);            // 设置mDebugInsert=true,测试"添加函数"            if (mDebugInsert) {                System.out.printf("== 添加节点: %d\n", a[i]);                System.out.printf("== 树的详细信息: \n");                tree.print();                System.out.printf("\n");            }        }        System.out.printf("== 前序遍历: ");        tree.preOrder();        System.out.printf("\n== 中序遍历: ");        tree.inOrder();        System.out.printf("\n== 后序遍历: ");        tree.postOrder();        System.out.printf("\n");        System.out.printf("== 最小值: %s\n", tree.minimum());        System.out.printf("== 最大值: %s\n", tree.maximum());        System.out.printf("== 树的详细信息: \n");        tree.print();        System.out.printf("\n");        // 设置mDebugDelete=true,测试"删除函数"        if (mDebugDelete) {            for(i=0; i<ilen; i++)            {                tree.remove(a[i]);                System.out.printf("== 删除节点: %d\n", a[i]);                System.out.printf("== 树的详细信息: \n");                tree.print();                System.out.printf("\n");            }        }        // 销毁二叉树        tree.clear();    }}
参考资料《玩转数据结构》
https://www.cnblogs.com/skywang12345/p/3624343.html
最新回复(0)