紅黑樹

一、二叉搜索樹

image

二叉搜索樹，也稱有序二叉樹,排序二叉樹，具有以下特性：

1、是一棵二叉樹

2、若任意節(jié)點(diǎn)的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；

3、若任意節(jié)點(diǎn)的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；

4、任意節(jié)點(diǎn)的左、右子樹也分別為二叉查找樹。

5、沒有鍵值相等的節(jié)點(diǎn)。

二叉樹的插入：

image

插入的結(jié)點(diǎn)總是作為某一葉子節(jié)點(diǎn)的子結(jié)點(diǎn)（插入后的樹必須也是二叉樹）

二叉樹的刪除：（刪除后的樹必須也是二叉樹）

1、節(jié)點(diǎn)為葉子節(jié)點(diǎn)直接刪除

2、節(jié)點(diǎn)有一個(gè)葉子節(jié)點(diǎn)，則刪除該節(jié)點(diǎn)后將其葉子節(jié)點(diǎn)上移為新的父節(jié)點(diǎn)

3、節(jié)點(diǎn)有兩個(gè)葉子節(jié)點(diǎn)，則刪除該節(jié)點(diǎn)后將其右子樹的中序列第一個(gè)節(jié)點(diǎn)（也就是右子樹中的最小節(jié)點(diǎn)）上移為新的父節(jié)點(diǎn)，并將該節(jié)點(diǎn)的右節(jié)點(diǎn)（該節(jié)點(diǎn)必定無左節(jié)點(diǎn)）替代其原位置。

image

二、紅黑樹

紅黑樹（Red-Black Tree ：R-B Tree），它一種特殊的二叉搜索樹。

在線動態(tài)紅黑樹（https://www.cs.usfca.edu/~galles/visualization/RedBlack.html）

image

紅黑樹的特性：（必須滿足二叉搜索樹的特性）

（1）每個(gè)節(jié)點(diǎn)或者是黑色，或者是紅色。

（2）根節(jié)點(diǎn)是黑色。

（3）每個(gè)葉子節(jié)點(diǎn)是黑色。（注意：這里的葉子節(jié)點(diǎn)均為NULL ?。。。?/p>

（4）如果一個(gè)節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的。

（5）從一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。

因?yàn)樘匦?5)，確保沒有一條路徑會比其他路徑長出倆倍（黑-紅-黑-紅-黑 ：黑-黑-黑）。因而，紅黑樹是相對是接近平衡的二叉樹。

無論是插入還是刪除，最重要的就是要保證RBT的特性5


public class Node {
    private String colour = RBTree.RED;
    private Integer value;
    
    private Node fatherNode;
    private Node leftNode;
    private Node rightNode;
    
    private static int length=1;


    public Node( int value) {
        super();
        this.value = value;
    }
    
    public String getColour() {
        return colour;
    }

    public void setColour(String colour) {
        this.colour = colour;
    }

    public Integer getValue() {
        return value;
    }

    public void setValue(Integer value) {
        this.value = value;
    }
    
    public void setFatherNode(Node fatherNode) {
        this.fatherNode = fatherNode;
    }

    public Node setLeftNode(Node leftNode){
        this.leftNode=leftNode;
        if(leftNode!=null){
            leftNode.setFatherNode(this);;
        }
        length++;
        return leftNode;
    }
    
    public Node setRightNode(Node rightNode){
        this.rightNode=rightNode;
        if(rightNode!=null){
            rightNode.setFatherNode(this);
        }
        length++;
        return rightNode;
    }
    
    public Node getLeftNode() {
        return leftNode;
    }

    public Node getRightNode() {
        return rightNode;
    }

    public Node getFatherNode() {
        return fatherNode;
    }

    @Override
    public String toString() {
        // TODO Auto-generated method stub
        return this.getColour()+":"+this.getValue();
    }
}

插入：

0、插入位置一定為非空的葉子節(jié)點(diǎn)（符合二叉搜索樹）

1、插入的節(jié)點(diǎn)為紅節(jié)點(diǎn)（為了滿足特性5），若插入的是空樹，則需要變?yōu)楹谏榱藵M足特性2）

-- 調(diào)整樹

2、若插入節(jié)點(diǎn)的父節(jié)點(diǎn)為黑色，即可滿足所有的特性（直接插入即可）

3、若插入節(jié)點(diǎn)的父節(jié)點(diǎn)為紅色，（即一定存在黑色祖父節(jié)點(diǎn)，因?yàn)橐獫M足特性2和特性4），叔節(jié)點(diǎn)也為紅色，只需將父、叔節(jié)點(diǎn)變?yōu)楹谏?，祖父?jié)點(diǎn)變?yōu)榧t色，然后再以祖父節(jié)點(diǎn)視為插入節(jié)點(diǎn)，進(jìn)入步驟2重新調(diào)整樹

4、插入N節(jié)點(diǎn)后,N的父節(jié)點(diǎn)為紅色,叔叔節(jié)點(diǎn)為黑色,且N是右子

解決:以N節(jié)點(diǎn)父節(jié)點(diǎn)為新節(jié)點(diǎn)N,并以N為支點(diǎn)進(jìn)行左旋,父節(jié)點(diǎn)變黑，原祖父節(jié)點(diǎn)變紅，繼續(xù)判定旋轉(zhuǎn)后的節(jié)點(diǎn)N是否滿

5、插入:插入N節(jié)點(diǎn)后,N的父節(jié)點(diǎn)為紅色,叔叔節(jié)點(diǎn)為黑色,且N是左子

解決:N父節(jié)點(diǎn)變黑色,祖父節(jié)點(diǎn)變紅色,祖父節(jié)點(diǎn)為支點(diǎn)進(jìn)行右旋。

package tree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
/**
 * 紅黑樹 
 * @author heqichao
 *
 */
public class RBTree {
    private Node tree;  //記錄樹結(jié)構(gòu)
    public static String BLACK="黑";
    public static String RED="紅";
    private Map<Integer,List> printMap;
    
    /**
     * 打印樹結(jié)構(gòu)
     */
    public void print(){
        printMap=new HashMap<Integer,List>();
        setPrintMap(tree,0);
        Iterator<Map.Entry<Integer, List>> it =printMap.entrySet().iterator();
        while(it.hasNext()){
             Map.Entry<Integer, List> entry=it.next();
             List list =entry.getValue();
             Iterator  listIt =list.iterator();
             while(listIt.hasNext()){
                 System.out.print(listIt.next());
                 System.out.print(",");
             }
             System.out.println();
        }
    }
    private void setPrintMap(Node node ,int i){
        if(printMap.get(i) ==null){
            printMap.put(i, new ArrayList());
        }
        if(node == null){
            //printMap.get(i).add(RBTree.BLACK+":NULL");
            return;
        }
        printMap.get(i).add(node.toString());
        i++;
        setPrintMap(node.getLeftNode(), i);
        setPrintMap(node.getRightNode(), i);
    }
    
    /**
     * 插入元素
     * @param num 元素值
     * @return
     */
    public  Node put(int num){
        //0、插入的節(jié)點(diǎn)一定為紅色的非NULL的"葉子節(jié)點(diǎn)"
        Node insertNode =new Node(num);
        //1、如果樹為空，則直接將該節(jié)點(diǎn)變?yōu)楦?jié)點(diǎn)（變黑色為了滿足特性2）
        if(tree ==null ){
            insertNode.setColour(BLACK);
            tree=insertNode;
            return tree;
        }
        boolean hasValue =insert(tree,insertNode);
        if(!hasValue){
            Node fatherNode =insertNode.getFatherNode();
            //2、如果插入節(jié)點(diǎn)的父節(jié)點(diǎn)為黑色，則已滿足所有特性，直接結(jié)束
            if(BLACK.equals(fatherNode.getColour())){
                return tree;
            }else{
                //3、如果插入節(jié)點(diǎn)的父節(jié)點(diǎn)為紅色(祖父節(jié)點(diǎn)一定為黑色)，則需要按情況旋轉(zhuǎn)或  重新著色
                addNodeAdjust(insertNode);
            }
        }
        return tree;
    }
    private  boolean insert(Node tree,Node insertNode){
        //查找結(jié)點(diǎn)的對應(yīng)位置并插入
        if(tree.getValue() == insertNode.getValue()){
            return true;
        }else if( tree.getValue() > insertNode.getValue() ){ // 往左樹查找
            if(tree.getLeftNode()!=null ){
                return insert(tree.getLeftNode(), insertNode);
            }else{
                tree.setLeftNode(insertNode);
            }
        }else{
            if(tree.getRightNode()!=null ){ //往右樹查找
                return insert(tree.getRightNode(),insertNode);
            }else{
                tree.setRightNode(insertNode);
            }
        }
        return false;
    }
    
    /**
     * 調(diào)整樹結(jié)構(gòu),根據(jù)情況旋轉(zhuǎn)和著色
     * @param insertNode 基準(zhǔn)節(jié)點(diǎn)
     */
    private  void addNodeAdjust(Node insertNode){
        if(insertNode == null){
            return;
        }
        //如果調(diào)整導(dǎo)致根節(jié)點(diǎn)變紅，則直接令根節(jié)點(diǎn)變黑
        if(insertNode.getFatherNode() == null){
            insertNode.setColour(BLACK);
            return;
        }
        if(BLACK.equals(insertNode.getFatherNode().getColour())){
            return;
        }
        Node fatherNode =insertNode.getFatherNode();
        //3、如果插入節(jié)點(diǎn)的父節(jié)點(diǎn)為紅色(祖父節(jié)點(diǎn)一定為黑色)，則需要按情況旋轉(zhuǎn)或  重新著色
            //3.1 如果插入節(jié)點(diǎn)的叔節(jié)點(diǎn)也為紅色，只需將父、叔節(jié)點(diǎn)變?yōu)楹谏娓腹?jié)點(diǎn)變?yōu)榧t色，然后再以祖父節(jié)點(diǎn)視為插入節(jié)點(diǎn)，重新調(diào)整樹
        Node uncleNode =fatherNode.getFatherNode().getLeftNode();
        if(uncleNode == fatherNode){
            uncleNode=fatherNode.getFatherNode().getRightNode();
        }
        if(uncleNode!=null && RED.equals(uncleNode.getColour())){
            fatherNode.setColour(BLACK);
            uncleNode.setColour(BLACK);
            fatherNode.getFatherNode().setColour(RED);
            addNodeAdjust(fatherNode.getFatherNode());
        }else{
            //3.2插入節(jié)點(diǎn)的叔節(jié)點(diǎn)為黑色（注：叔節(jié)點(diǎn)為NULL，也是黑色!!!）
                Node grandFather =fatherNode.getFatherNode();
                if(insertNode.getValue()<fatherNode.getValue()){
                    //3.2.1插入節(jié)點(diǎn)在父節(jié)點(diǎn)左樹，則右轉(zhuǎn)
                    if(grandFather!=null && grandFather.getValue()< fatherNode.getValue()){
                    //    6
                    //          10
                    //       8         8為插入點(diǎn),先右轉(zhuǎn)后再左轉(zhuǎn)
                        turnRight(insertNode); 
                        turnLeft(insertNode);
                        //繼續(xù)檢查調(diào)整
                        addNodeAdjust(insertNode.getFatherNode());
                    }else{
                    //          14
                    //      10
                    //   8             8為插入點(diǎn),直接右轉(zhuǎn)
                        turnRight(insertNode.getFatherNode());
                        //繼續(xù)檢查調(diào)整  
                        addNodeAdjust(fatherNode.getFatherNode());
                    }
                }else{
                    //3.2.2插入節(jié)點(diǎn)在父節(jié)點(diǎn)右樹，則左轉(zhuǎn)
                    if(grandFather!=null && grandFather.getValue()>fatherNode.getValue()){
                    //           10
                    //      6
                    //         8       8為插入點(diǎn),先左轉(zhuǎn)后再右轉(zhuǎn)
                        turnLeft(insertNode);
                        turnRight(insertNode);
                        //繼續(xù)檢查調(diào)整
                        addNodeAdjust(insertNode.getFatherNode());
                    }else{
                    //   4
                    //      6 
                    //         8     8為插入點(diǎn),直接左轉(zhuǎn)轉(zhuǎn)
                        turnLeft(insertNode.getFatherNode());
                        //繼續(xù)檢查調(diào)整
                        addNodeAdjust(fatherNode.getFatherNode());
                    }
                }
        }
    }
    
    /**
     * 將節(jié)點(diǎn)設(shè)置為根節(jié)點(diǎn)
     * @param node 
     */
    private void setRoot(Node node){
        Node srcRoot =node.getFatherNode();
        node.setFatherNode(null);
        if(srcRoot.getValue() <node.getValue()){
            srcRoot.setRightNode(node.getLeftNode());
            node.setLeftNode(srcRoot);
        }else{
            srcRoot.setLeftNode(node.getRightNode());
            node.setRightNode(srcRoot);
        }
        node.setColour(BLACK);
        srcRoot.setColour(RED);
        tree=node;
    }
    
    /**
     * 左轉(zhuǎn)
     * @param node基準(zhǔn)節(jié)點(diǎn)
     */
    private  void turnLeft(Node node){
        Node fatherNode =node.getFatherNode();
        Node grandFatherNode =fatherNode.getFatherNode();
        if(grandFatherNode == null){
            setRoot(node);
        }else{
            if(grandFatherNode.getValue()<fatherNode.getValue()){
                grandFatherNode.setRightNode(node);
            }else{
                grandFatherNode.setLeftNode(node);
            }
            fatherNode.setRightNode(node.getLeftNode());        
            node.setLeftNode(fatherNode);
            node.setColour(BLACK);
            fatherNode.setColour(RED);
        }
    }
    
    /**
     * 右轉(zhuǎn)
     * @param node 基準(zhǔn)節(jié)點(diǎn)
     */
    private  void turnRight(Node node){
        Node fatherNode =node.getFatherNode();
        Node grandFatherNode =fatherNode.getFatherNode();
        if(grandFatherNode == null){
            setRoot(node);
        }else{
            if(grandFatherNode.getValue()<fatherNode.getValue()){
                grandFatherNode.setRightNode(node);
            }else{
                grandFatherNode.setLeftNode(node);
            }
            fatherNode.setLeftNode(node.getRightNode());
            node.setRightNode(fatherNode);
            node.setColour(BLACK);
            fatherNode.setColour(RED);
        }
    }
    
    /**
     * 獲取元素節(jié)點(diǎn)
     * @param tree
     * @param num
     * @return
     */
    public String get(int num){
        Node node =get(tree, num);
        if(node !=null){
            return node.toString();
        }
        return null;
    }
    private Node get(Node tree,int num){
        if(tree != null){
            if(tree.getValue() == num){
                return tree;
            }else if( tree.getValue() > num){ // 往左樹查找
                if(tree.getLeftNode()!=null ){
                    return get(tree.getLeftNode(), num);
                }
            }else{
                if(tree.getRightNode()!=null ){ //往右樹查找
                    return get(tree.getRightNode(), num);
                }
            }
        }
        return null;
    }
    
    private Node getRearNode(Node node){
        if(node.getLeftNode() == null){
            return node;
        }else{
            return getRearNode(node.getLeftNode());
        }
        
    }
    
    private void copyNodeValue(Node src,Node des){
        des.setValue(src.getValue());
    }
}

刪除：
后補(bǔ)。

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容