红黑树-详解及Java插入示例

分手后的思念是犯贱 2023-05-29 02:40 13阅读 0赞

### 红黑树-详解及Java插入示例 ###

*  详解
 *  插入分析-自顶向下
 *   *   *  Cur黑
         *  Cur红Brother黑
         *  Cur红Brother红
         *   *   *  Grand黑-圆
                 *  Grand红-方
 *  Java例子
 *  测试
 *  参考

# 详解 #

AVL流行的另外一种变种，操作最坏情况下O(logN)时间

定义：具有下面性质的二叉查找树

*  节点为红色或黑色
 *  根节点为黑色
 *  红色节点的子节点为黑色
 *  从一个节点到Null节点(默认叶子节点为空)，经过黑色树相等

# 插入分析-自顶向下 #

插入时，默认新节点N为红色，插入位置即新节点的parent为Cur

思路：**让Cur的颜色重置为黑色，这样红色的N插入Cur的位置就还是红黑树！**

> **备注**：图中圆为黑，方形为红；  
> N为新节点；  
> Cur为要插入的位置，即N的parent;  
> P为Cur的parent；  
> B为Cur的兄弟brother；  
> G为grand祖父，即N的parent的parent；  
> GT即great曾祖父，Cur的parent的parent的parent

共可以分为下面3大种情况，共5种小情况

### Cur黑 ###

直接插入即可(新节点为左子树或右子树）；

左或右

Cur

### Cur红Brother黑 ###

若parent为红，Cur只能为黑，故parent必为黑;  
进行一次单旋转即可，下面以向右单旋转为例（左Brother、向左单旋转的例子同理）

*  Cur为新根，且修改为黑；
 *  原来根P为Cur的子，修改为红

左或右

Cur

左或右

Cur

### Cur红Brother红 ###

如下图所示。目的让左右子树为黑（即下面的Cur或Brother为黑，N可以直接插入到Cur或Brother上）。

思路：从顶往下查找Cur，Cur的左右子树都为红色，进行处理，

grand为红或者黑2种情况

Cur

Brother

##### Grand黑-圆 #####

*  P、Cur、B均颜色反置即可，结果如下所示

Cur

Brother

##### Grand红-方 #####

这种情况是最复杂的。祖父grand为红，曾祖父great必然为黑，处理思路为对曾祖父这个子树进行处理，返回根节点为黑的新数（根节点可能部位曾祖父了！）

*  GT、G、P若不在一个方向上，则G、P进行一次单旋转
 *  GT、G、P已在一个方向上，GT、G进行一次单旋转

> 等同：不在一个方向上就进行双旋转，否则单旋转

下面以GT、G、P不在一个方向上示例。下面为原图

Cur

Brother

下面G、P向左旋转，P及其左右子树颜色反置

Brother

Cur

可以看到PG都为红色，且等同于GT、G、P在一个方向上的情况。所以要把P红色上冒，**其实GT、P、a相当于上面第2大种情况了！！Cur(这里为P)红、B(这里为a)黑！！**  
GT、P进行向右旋转，在修改P、GT的颜色即可(P黑⚪，GT红方）：

Brother

Cur

Brother

Cur

# Java例子 #

package com.ydfind.datastructure.tree;
    
    /**
     * 红黑树
     * @param <T> 数据的类型
     * @author ydfind
     * @date 2019.11.1
     */
    public class MyRedBlackTree<T extends Comparable<? super T>>{
    
        /**
         * 黑色
         */
        private static final int BLACK = 1;
        /**
         * 红色
         */
        private static final int RED   = 0;
    
        private RedBlackNode<T> header;
        private RedBlackNode<T> nullNode;
        // 当前节点、父、祖父、曾祖父节点
        private RedBlackNode<T> current;
        private RedBlackNode<T> parent;
        private RedBlackNode<T> grand;
        private RedBlackNode<T> great;
        /*************************************************节点类**********************************/
        /**
         * 红黑树节点 类
         * @param <T>
         */
        private static class RedBlackNode<T> {
            T data;
            RedBlackNode<T> left;
            RedBlackNode<T> right;
            int color;
    
            RedBlackNode(T data){
                this(data, null, null );
            }
    
            RedBlackNode(T data, RedBlackNode<T> left, RedBlackNode<T> right) {
                this.data = data;
                this.left = left;
                this.right = right;
                // 默认节点为黑色
                this.color = MyRedBlackTree.BLACK;
            }
        }
    
    
        public MyRedBlackTree(){
            // 初始化根节点和空节点（默认的叶子节点）
            nullNode = new RedBlackNode<>(null);
            nullNode.left = nullNode.right = nullNode;
            header = new RedBlackNode<>(null);
            header.left = header.right = nullNode;
        }
    
        private final int compare(T item, RedBlackNode<T> t){
            if(t == header){
                // header默认为空，默认比其他都小
                return 1;
            }else{
                return item.compareTo(t.data);
            }
        }
    
        public void insert(T item){
            // 默认都等于头节点
            current = parent = grand = header;
            nullNode.data = item;
            int cp;
            while ((cp = compare(item, current)) != 0){// 会有相等的时候吗？？？？？？？？是不是插入后，和自己比较就相等了
                // 往下面一个节点
                great = grand;
                grand = parent;
                parent = current;
                // 第一个节点必然再header的右边
                current = cp < 0 ? current.left : current.right;
    
                // 两个子节点为红，重新确定红黑色
                if(current.left.color == RED && current.right.color == RED){
                    handleReorient(item);
                }
            }
            // 找到对应节点current不为空，无法进行插入
            if(nullNode != current){
                return;
            }
            // 执行插入操作
            current = new RedBlackNode<>(item, nullNode, nullNode);
            if(compare(item, parent) < 0){
                parent.left = current;
            }else{
                parent.right = current;
            }
            handleReorient(item);
        }
    
        /**
         * 全局变量current两个子节点为红，重新确定红黑色
         */
        private void handleReorient(T item){// current等变量传入这里会不会有问题?????????????????????
            current.color = RED;
            current.left.color = BLACK;
            current.right.color = BLACK;
            if(parent.color == RED){
                grand.color = RED;
                if((compare(item, parent) < 0) != (compare(item, grand) < 0)){
                    // 需要进行双旋转
                    // 第一步：current、parent两个节点进行，传入parent的parent即grand
                    parent = rotate(item, grand);
                }
                // 单旋转或双旋转的第二步
                // 这里可能会使insert中current往前了，是不是会多了一层????????????????
                current = rotate(item, great);
                // 新树根默认黑色，这样树上面的节点的结构
                current.color = BLACK;
            }
            header.right.color = BLACK;
        }
        /***************************************************旋转************************************/
    
        /**
         * 对parent的left或right节点，进行 单旋转 或 双旋转中单旋转;
         * 并将新子树的树根 重新赋值；
         * 其中颜色需要外部处理
         * @param item
         * @param parent
         * @return
         */
        private RedBlackNode<T> rotate(T item, RedBlackNode<T> parent){
            if(compare(item, parent) < 0){
                // 判断LL，还是LR型，单旋转后面的L或R
                parent.left = compare(item, parent.left) < 0 ?
                        rotateWithLeftChild(parent.left) :
                        rotateWithRightChild(parent.left);
                return parent.left;
            }else{
                parent.right = compare(item, parent.right) < 0 ?
                        rotateWithLeftChild(parent.right) :
                        rotateWithRightChild(parent.right);
                return parent.right;
            }
        }
    
        /**
         * 左子树，向右单旋转
         */
        private RedBlackNode<T> rotateWithLeftChild( RedBlackNode<T> k2 ){
            RedBlackNode<T> k1 = k2.left;
            k2.left = k1.right;
            k1.right = k2;
            return k1;
        }
    
        /**
         * 右子树，向左单旋转
         */
        private RedBlackNode<T> rotateWithRightChild( RedBlackNode<T> k1 )
        {
            RedBlackNode<T> k2 = k1.right;
            k1.right = k2.left;
            k2.left = k1;
            return k2;
        }
        /*******************************************打印***********************************************/
        public void printTree() {
            if(isEmpty()) {
                System.out.println("Empty tree");
            } else {
                System.out.println("\n中序：left data right--------------");
                printTree(header.right);
                System.out.println("\n先序：data left right--------------");
                printPreTree(header.right);
            }
        }
    
        private void printPreTree( MyRedBlackTree.RedBlackNode<T> t ) {
            if(t != nullNode){
                if(t.color == BLACK) {
                    System.out.print(t.data + " ");
                }else {
                    System.out.print(t.data + "_ ");
                }
                if(t.right != nullNode || t.left != nullNode) {
                    printPreTree(t.left);
                    printPreTree(t.right);
                }
            }
        }
    
        private void printTree( MyRedBlackTree.RedBlackNode<T> t ) {
            if(t != nullNode){
                if(t.left != nullNode) {
                    printTree(t.left);
                }
                if(t.color == BLACK) {
                    System.out.print(t.data + " ");
                }else {
                    System.out.print(t.data + "_ ");
                }
                if(t.right != nullNode) {
                    printTree(t.right);
                }
            }
        }
    
        public boolean isEmpty( ) {
            return header.right == nullNode;
        }
    }

# 测试 #

package com.ydfind.datastructure.avl;
    
    import com.ydfind.datastructure.tree.MyRedBlackTree;
    import org.junit.Test;
    
    public class RedBlackTreeTest {
    
        @Test
        public void testInsert(){
            MyRedBlackTree redBlackTree = new MyRedBlackTree();
            int[] items = {10, 85, 15, 70, 20, 60, 30, 50, 65, 80, 90, 40, 5, 55};
            for(int item: items) {
                redBlackTree.insert(item);
            }
            redBlackTree.printTree();
            System.out.print("\n");
        }
    }

运行结果

中序：left data right--------------
    5_ 10 15 20 30 40_ 50 55_ 60_ 65 70 80_ 85 90_ 
    先序：data left right--------------
    30 15 10 5_ 20 70 60_ 50 40_ 55_ 65 85 80_ 90_

利用先序和中序，还愿图如下：

左

5红

40红

55红

60红

80红

90红

与《数据结构与算法分析-C语言描述》中P351下面的图示一致

# 参考 #

*  《数据结构与算法分析-C语言描述》第2版
 *  《数据结构与算法分析-Java语言描述》第3版