红黑树插入节点

作者: sunpy | 来源:发表于2018-02-27 15:10 被阅读9次

什么是红黑树

红黑树是带有着色性质的二叉查找树。

性质如下：
① 每一个节点或者着成红色或者着成黑色。
② 根节点为黑色。
③ 每个叶子节点为黑色。（指的是指针指向为NULL的叶子节点）
④ 如果一个节点是红色的，那么它的子节点必须是黑色的。
⑤ 从一个节点到一个NULL指针的每一条路径必须包含相同数目的黑色节点。
推论：有n个节点的红黑树的高度最多是2log(N+1) 。

红黑树旋转操作的原理

下述代码注释搭配图片便于理解

右旋操作：

1.jpg

说明：将rbn节点和c节点顺时针旋转到b的下面，然后调整位置。
代码实现：

//顺时针右旋  
public static void rotateByRight(RBNode rbn){  
    RBNode b =rbn.getLchild();  
    //旋转后结果调整，rbn的左孩子为e  
    rbn.setLchild(b.getRchild());  
    //如果b的右孩子e存在就确定e的父节点为rbn  
    if(b.getRchild() !=null){  
        b.getRchild().setParent(rbn);  
    }  
    //确定b的父节点为原rbn的父节点  
    b.setParent(rbn.getParent());  
    if(rbn.getParent() ==null){  
        root =;  
    }else{  
        //确定rbn是否为父节点的右孩子节点  
        if(rbn ==rbn.getParent().getRchild()){  
            rbn.getParent().setRchild(b);  
        }else{  
            rbn.getParent().setLchild(b);  
        }  
    }  
    //确定b的右孩子为rbn  
    b.setRchild(rbn);  
    //确定rbn的父节点为b  
    rbn.setParent(b);  
}

左旋操作：

2.jpg

说明：将rbn节点和c节点逆时针旋转到d的下面，然后调整位置。

代码实现：

//逆时针左旋  
public static void rotateByLeft(RBNode rbn){  
    RBNode d =rbn.getRchild();  
    //确定rbn的右孩子为e  
    rbn.setRchild(d.getLchild());  
    //如果e不为空，那么确定e的父节点为rbn  
    if(d.getLchild() !=null){  
        d.getLchild().setParent(rbn);  
    }  
    //确定d的父节点为rbn的父节点  
    d.setParent(rbn.getParent());  
    if(rbn.getParent() ==null){  
        root =;  
    }else{  
        //确定rbn是否为其父节点的左孩子节点，目得是为了确定d的父节点的左孩子还是右孩子为d  
        if(rbn ==rbn.getParent().getLchild()){  
            rbn.getParent().setLchild(d);  
        }else{  
            rbn.getParent().setRchild(d);  
        }  
    }  
    //确定d的左孩子为rbn  
    d.setLchild(rbn);  
    //确定rbn的父节点为d  
    rbn.setParent(d);  
}

红黑树插入元素的原理

关于红黑树插入节点后为了保持红黑树的特性，主要进行的操作就是换颜色和旋转操作。

情况1：父节点是黑色，插入新节点为红色。

3.png

解决办法：
由于新节点父节点为黑色，直接插入即可。

情况2：父节点为红色，叔叔节点为红色，插入新节点为红色，插入新节点为父节点的左孩子节点。（红叔左父左插入情况）

4.png
解决办法：
为了保持新节点为红色，如果此时父节点为红色就不满足性质4.所以父节点需要调整为黑色，但是这样祖节点到NL叶子节点，就会出现数目不同的黑色节点了。不满足性质5了。所以祖节点需要调整为红色节点满足性质。这样叔叔也就得调整为黑色了，要不就不满足性质4和性质5.
总结：红父->黑父红叔->黑叔黑祖->红祖

情况3：父节点为红色，叔叔节点为红色，插入新节点为红色，插入新节点为父节点的右孩子节点。（红叔左父右插入情况）

5.png
解决办法：
这种情况同情况2一样，无须旋转，只是颜色不满足性质，只需调整颜色即可。
总结： 红父->黑父红叔->黑叔黑祖->红祖

情况4：父节点为红色，叔叔节点为黑色，插入新节点为红色，插入新节点为父节点的左孩子节点。（黑叔左父左插入情况）

6.png
解决办法：
这种情况单纯通过换色是无法控制红黑树性质的满足。通过右旋来满足平衡条件。
总结：右旋红父->黑父黑祖->红祖

情况5：父节点为红色，叔叔节点为黑色，插入新节点为红色，插入新节点为父节点的右孩子节点。（黑叔左父右插入情况）

7.png
解决办法：
这种使用上面的右旋会发现，就会出现两个值的节点和三个子节点的情况。我们先局部左旋父节点。然后将祖节点和叔节点右旋转。
总结：左旋右旋黑祖->红祖红新->黑新

情况6：父节点为红色，叔叔节点为红色，插入新节点为红色，插入新节点为父节点的左孩子节点。（红叔右父左插入情况）

8.png
解决办法：
这种情况和情况2差不多，就是调整颜色就可以了，主要原因就可以发现父节点和叔叔节点都是红色，这样直接调整颜色，就会满足红黑树性质。
总结：红父->黑父红叔->黑叔黑祖->红祖

情况7：父节点为红色，叔叔节点为红色，插入新节点为红色，插入新节点为父节点的右孩子节点。（红叔右父右插入情况）

9.png
解决办法：
这种情况和情况3一样，都是只是调整下颜色就好。
总结：红父->黑父红叔->黑叔黑祖->红祖

情况8：父节点为红色，叔叔节点为黑色，插入新节点为红色，插入新节点为父节点的右孩子节点。（黑叔右父右插入情况）

10.png
解决办法：
这种情况会出现旋转了，因为叔节点和父节点颜色不同，所以单纯调整颜色不能满足性质了。就采用将祖节点和叔节点左旋，作为父节点的左孩子树。
总结：左旋红父->黑父黑祖->红祖

情况9：父节点为红色，叔叔节点为黑色，插入新节点为红色，插入新节点为父节点的左孩子节点。（黑叔右父左插入情况）

11.png
解决办法：
这种情况类似于情况5，如果我们直接左旋祖节点和叔节点，那么就会出现2节点，3孩子情况。所以为了避免这种冲突。就先进行局部旋转，先将父节点右旋，然后将祖节点和叔节点左旋。
总结：右旋左旋黑祖->红祖红新->黑新

全面总结

黑父，直接插入新节点即可。

红叔，就调整颜色即可。

黑叔，需要进行旋转操作。

红黑树插入元素完整代码实现

颜色枚举：

public enum Color {  
      
    RED("0","红色"),  
    BLACK("1","黑色");  
    private String name = ;  
    private String value =;  
    private Color(String name, String value) {  
        this.name=name;  
        this.value=value;  
    }  
    public String getName() {  
        return name;  
    }  
    public void setName(String name) {  
        this.name = name;  
    }  
    public String getValue() {  
        return value;  
    }  
    public void setValue(String value) {  
        this.value = value;  
    }  
    public static Color getEnumByName(String name){  
        if ( == name) {  
            return null;  
        }  
        for (Color type : values()) {  
            if (type.getName().equals(name.trim()))  
                return type;  
        }  
        return null;  
    }  
      
    public static Map<String, String> toMap() {  
        Map<String, String> enumDataMap = new LinkedHashMap<String, String>();  
        for (Color type : values()) {  
            enumDataMap.put(type.getName(), type.getValue());  
        }  
        return enumDataMap;  
    }  
      
}

红黑树节点数据的结构定义：

public class RBNode {  
  
    private Integer data;  
    //红黑树中节点对应的颜色  
    private Color color;  
    //红黑树中当前节点的左孩子节点  
    private RBNode lchild;  
    //红黑树中当前节点的右孩子节点  
    private RBNode rchild;  
    //红黑树中当前节点的父节点  
    private RBNode parent;  
    public RBNode(){}  
    public RBNode(Integer data){  
        this.data =data;  
    }  
    public RBNode(Integer data,Color color,RBNode parent,RBNode lchild,RBNode rchild){  
        this.data =data;  
        this.color =color;  
        this.parent =parent;  
        this.lchild =lchild;  
        this.rchild =rchild;  
    }  
      
    public RBNode getParent() {  
        return parent;  
    }  
    public void setParent(RBNode parent) {  
        this.parent = parent;  
    }  
    public Integer getData() {  
        return data;  
    }  
    public void setData(Integer data) {  
        this.data = data;  
    }  
    public Color getColor() {  
        return color;  
    }  
    public void setColor(Color color) {  
        this.color = color;  
    }  
    public RBNode getLchild() {  
        return lchild;  
    }  
    public void setLchild(RBNode lchild) {  
        this.lchild = lchild;  
    }  
    public RBNode getRchild() {  
        return rchild;  
    }  
    public void setRchild(RBNode rchild) {  
        this.rchild = rchild;  
    }  
}

主程序代码：

public class RBTree {    
      
    private static RBNode root =;    
        
    //顺时针右旋    
    public static void rotateByRight(RBNode rbn){    
        RBNode b =rbn.getLchild();    
        rbn.setLchild(b.getRchild());    
        if(b.getRchild() !=null){    
            b.getRchild().setParent(rbn);    
        }    
        b.setParent(rbn.getParent());    
        if(rbn.getParent() ==null){    
            root =;    
        }else{    
            if(rbn ==rbn.getParent().getRchild()){    
                rbn.getParent().setRchild(b);    
            }else{    
                rbn.getParent().setLchild(b);    
            }    
        }    
        b.setRchild(rbn);    
        rbn.setParent(b);    
    }    
        
    //逆时针左旋    
    public static void rotateByLeft(RBNode rbn){    
        RBNode d =rbn.getRchild();    
        rbn.setRchild(d.getLchild());    
        if(d.getLchild() !=null){    
            d.getLchild().setParent(rbn);    
        }    
        d.setParent(rbn.getParent());    
        if(rbn.getParent() ==null){    
            root =;    
        }else{    
            if(rbn ==rbn.getParent().getLchild()){    
                rbn.getParent().setLchild(d);    
            }else{    
                rbn.getParent().setRchild(d);    
            }    
        }    
        d.setLchild(rbn);    
        rbn.setParent(d);    
    }    
        
        
        
    //红黑树插入节点    
    private static void insertRBNode(RBNode insertNode){    
        RBNode tempRoot =root;    
        //给红黑树插入节点，先不考虑局部平衡问题    
        while(tempRoot !=null){    
            if(insertNode.getData()<tempRoot.getData()){    
                if(tempRoot.getLchild() !=null){    
                    tempRoot =tempRoot.getLchild();    
                }else{    
                    tempRoot.setLchild(insertNode);    
                    insertNode.setParent(tempRoot);    
                    break;    
                }    
            }else if(insertNode.getData()>tempRoot.getData()){    
                if(tempRoot.getRchild() !=null){    
                    tempRoot =tempRoot.getRchild();    
                }else{    
                    tempRoot.setRchild(insertNode);    
                    insertNode.setParent(tempRoot);    
                    break;    
                }    
            }    
        }    
        //插入节点设置为红色    
        insertNode.setColor(Color.RED);    
        insertNode.setLchild(null);    
        insertNode.setRchild(null);    
        adjustRBTree(insertNode);    
    }    
        
    //调整红黑树    
    public static void adjustRBTree(RBNode rbNode){    
        //定义父节点    
        RBNode parent =rbNode.getParent();    
        while(parent !=null && parent.getColor().equals(Color.RED)){    
            //定义祖父节点    
            RBNode grandParent =parent.getParent();    
            //如果父节点是祖父节点的左孩子    
            if(parent.equals(grandParent.getLchild())){    
                RBNode uncleNode =grandParent.getRchild();    
                //情况2、情况3：红叔    
                if(uncleNode !=null && uncleNode.getColor().equals(Color.RED)){    
                    uncleNode.setColor(Color.BLACK);    
                    parent.setColor(Color.BLACK);    
                    grandParent.setColor(Color.RED);    
                }else if(uncleNode !=null && uncleNode.getColor().equals(Color.BLACK) && parent.getLchild().equals(rbNode)){    
                    //情况4：黑叔，当前节点是左孩子    
                    rotateByRight(grandParent);    
                    parent.setColor(Color.BLACK);    
                    grandParent.setColor(Color.RED);    
                }else if(uncleNode !=null && uncleNode.getColor().equals(Color.BLACK) && parent.getRchild().equals(rbNode)){    
                    //情况5：黑叔，当前节点是右孩子    
                    rotateByLeft(parent);    
                    rotateByRight(grandParent);    
                    rbNode.setColor(Color.BLACK);    
                    grandParent.setColor(Color.RED);    
                }else{  
                    break;  
                }  
            }else{//如果父节点是祖父节点的右孩子    
                RBNode uncleNode =grandParent.getLchild();    
                //情况6、情况7：红叔    
                if(uncleNode !=null && uncleNode.getColor().equals(Color.RED)){    
                    uncleNode.setColor(Color.BLACK);    
                    parent.setColor(Color.BLACK);    
                    grandParent.setColor(Color.RED);    
                }else if(uncleNode !=null && uncleNode.getColor().equals(Color.BLACK) && parent.getRchild().equals(rbNode)){    
                    //情况8：黑叔，当前节点是右孩子    
                    rotateByLeft(grandParent);    
                    parent.setColor(Color.BLACK);    
                    grandParent.setColor(Color.RED);    
                }else if(uncleNode !=null && uncleNode.getColor().equals(Color.BLACK) && parent.getLchild().equals(rbNode)){    
                    //情况9：黑叔，当前节点是左孩子    
                    rotateByRight(parent);    
                    rotateByLeft(grandParent);    
                    grandParent.setColor(Color.RED);    
                    rbNode.setColor(Color.BLACK);    
                }else{  
                    break;  
                }  
            }    
        }    
        root.setColor(Color.BLACK);    
    }    
        
    public static void queryRBNodeByPre(RBNode root){    
        if(root !=null){    
            System.out.print(root.getData()+"["+root.getColor().getValue()+"]"+" - ");    
            queryRBNodeByPre(root.getLchild());    
            queryRBNodeByPre(root.getRchild());    
        }else{    
            return;    
        }    
    }    
        
    /*递归方式遍历红黑树    
     * root:为遍历红黑树的根节点    
     * 中序方式    
     * */    
    public static void queryRBNodeByOrder(RBNode root) {    
        if(root !=null ){    
            queryRBNodeByOrder(root.getLchild());    
            System.out.print(root.getData()+"["+root.getColor().getValue()+"]"+" - ");    
            queryRBNodeByOrder(root.getRchild());    
        }else{    
            return;    
        }    
    }    
   
    public static void main(String[] args) {    
        root =new RBNode(13,Color.BLACK,null,null,null);    
        insertRBNode(new RBNode(8));    
        insertRBNode(new RBNode(17));    
        insertRBNode(new RBNode(1));    
        insertRBNode(new RBNode(11));    
        insertRBNode(new RBNode(15));    
        insertRBNode(new RBNode(25));    
        insertRBNode(new RBNode(6));    
        insertRBNode(new RBNode(22));    
        insertRBNode(new RBNode(27));    
        /*initRBTree(new RBNode(6), root);    
        initRBTree(new RBNode(5), root);    
        initRBTree(new RBNode(4), root);    
        queryRBNodeByOrder(root);    
        System.out.println();    
        queryBSTNodeByPre(root);    
        System.out.println();    
        System.out.println("旋转值：");    
        //rotateByLeft(root.getLchild());    
        rotateByRight(root.getRchild());*/    
        queryRBNodeByPre(root);    
        System.out.println();    
        System.out.println("----------------");    
        queryRBNodeByOrder(root);   
          
        /*RBNode rbNode =getMinRchild(root);  
        System.out.println(rbNode.getData());*/  
    }    
}

测试用例

12.jpg

测试结果

13.png

问题

在插入节点的时候，我直接使用root全局变量来操作的，发现程序的根节点被替换了，程序出现了问题。

后来才想到全局变量是在堆中开辟空间的，而堆是共享区域。方法体内定义的变量是在栈中开辟空间的，是在每个线程私有的区域，如果为了防止全局变量被修改，那么在方法中调用全局变量时，可以单独复制一份，以防止出现全局变量被修改。

如果读者发现博客中出现问题，谢谢评论指出。

参考

http://www.cnblogs.com/dongritengfei/archive/2010/06/16/1759209.html

http://www.cnblogs.com/skywang12345/p/3245399.html#commentform

https://www.ibm.com/developerworks/cn/java/j-lo-tree/index.html?ca=drs-

数据结构与算法分析（c语言）