樹結(jié)構(gòu)合集一

1. AVL樹

AVL樹簡單來說是帶有平衡條件的二叉查找樹.傳統(tǒng)來說是其每個節(jié)點(diǎn)的左子樹和右子樹的高度最多差1(注意不能只保持根節(jié)點(diǎn)平衡).

1

如上圖所示,只有左邊的才是AVL樹,右圖在7這個節(jié)點(diǎn)處平衡被破壞.
我們都知道,刪除和插入意味著有可能打破平衡,如上圖,將6插入的話在8位置的平衡將被打破.這意味著我們需要做一定的修正,稱為旋轉(zhuǎn).
對于失去平衡有四種姿態(tài),LL(左左)，LR(左右)，RR(右右)和RL(右左).下面分別給出示意圖:
2

除了上面的情況之外，還有其它的失去平衡的AVL樹，如下圖：
3

上圖只是易于理解,歸根結(jié)底只有四種姿態(tài):LL,LR,RR,RL.
對于LL與RR我們可以采取單旋轉(zhuǎn)解決,而對于LR與RL我們得采取稍顯復(fù)雜的雙旋轉(zhuǎn).

  • 單旋轉(zhuǎn)

單旋轉(zhuǎn)分為左左單旋轉(zhuǎn)和右右單旋轉(zhuǎn)

4
.
以上是左左單旋轉(zhuǎn)的例子,比較簡單不贅述
5

以上是右右單旋轉(zhuǎn)的例子

  • 雙旋轉(zhuǎn)

6

首先上圖解釋了為什么單旋轉(zhuǎn)無法解決這種狀況,解決這個問題的左右雙旋轉(zhuǎn)如下圖所示:
7

首先我們把子樹Y看成是一個節(jié)點(diǎn)兩個子樹構(gòu)成的,這并不影響啥.仔細(xì)觀察我們會發(fā)現(xiàn),整個過程實(shí)際上是先讓k1節(jié)點(diǎn)做一次右右單旋轉(zhuǎn),再做一次k3節(jié)點(diǎn)的左左單旋轉(zhuǎn).
右左雙旋轉(zhuǎn)如下圖所示,原理類似不再贅述
8

  • AVL實(shí)現(xiàn)

AVL樹的實(shí)現(xiàn)我們用代碼來模擬:

  package com.fredal.structure;
public class AVLTree<T extends Comparable<? super T>> {
   //內(nèi)部節(jié)點(diǎn)類
   private static class AVLNode<T> {
       T element;
       AVLNode<T> left;//左孩子
       AVLNode<T> right;//右孩子
       int height;//當(dāng)前高度

       AVLNode(T theElement) {
           this(theElement, null, null);
       }

       AVLNode(T theElement, AVLNode<T> lt, AVLNode<T> rt) {
           element = theElement;
           left = lt;
           right = rt;
           height = 0;
       }

   }
   
   private AVLNode<T> root;//根節(jié)點(diǎn)

   public AVLTree() {
       root=null;
   }
   //插入
   public void insert(T x){
       root=insert(x,root);
   }
   //刪除
   public void remove(T x){
       root=remove(x,root);
   }
   
   //尋找最小值
   public T findMin(){
       if(isEmpty())
           throw new RuntimeException("空錯誤");
       return findMin(root).element;
   }
   
   //尋找最大值
   public T findMax(){
       if(isEmpty())
           throw new RuntimeException("空錯誤");
       return findMax(root).element;
   }
   //是否存在
   public boolean contains(T x){
       return contains(x,root);
   }
   //清空
   public void empty(){
       root=null;
   }
   //判空
   public boolean isEmpty(){
       return root==null;
   }
   //打印樹
   public void printTree(){
       if(isEmpty())
           System.out.println("空樹");
       else 
           printTree(root);
   }
   //判斷是否平衡
   public void check(){
       check(root);
   }
   //判斷是否平衡
   private int check(AVLNode<T> t) {
       if(t==null)
           return -1;
       if(t!=null){
           int hl=check(t.left);
           int hr=check(t.right);
           if(Math.abs(height(t.left)-height(t.right))>1||
                   height(t.left)!=hl||height(t.right)!=hr)
               System.out.println("出錯了");
       }
       return height(t);
   }
   //獲取高度
   private int height(AVLNode<T> t){
       return t==null?-1:t.height;
   }
   //中序遍歷
   private void printTree(AVLNode<T> t) {
       if(t!=null){
           printTree(t.left);
           System.out.println(t.element);
           printTree(t.right);
       }
   }
   //是否包含 遞歸遍歷
   private boolean contains(T x, AVLNode<T> t) {
       while(t!=null){
           int res=x.compareTo(t.element);
           if(res<0)
               t=t.left;
           else if(res>0)
               t=t.right;
           else 
               return true;//找到了
       }
       return false;
   }
   //尋找最小值
   private AVLNode<T> findMin(AVLNode<T> t) {
       if(t==null)
           return t;
       while(t.left!=null)
           t=t.left;
       return t;
   }
   //尋找最大值
   private AVLNode<T> findMax(AVLNode<T> t) {
       if(t==null)
           return t;
       while(t.right!=null)
           t=t.right;
       return t;
   }
   //插入操作
   private AVLNode<T> insert(T x, AVLNode<T> t) {
       if(t==null)
           return new AVLNode<T>(x, null, null);//插入當(dāng)前的元素
       int res=x.compareTo(t.element);
       if(res<0)
           t.left=insert(x, t.left);
       else if(res>0)
           t.right=insert(x, t.right);
       else;//沖突了
       return balance(t);//確保平衡
   }
   //刪除操作
   private AVLNode<T> remove(T x, AVLNode<T> t) {
       if( t == null )
           return t;   // 啥也不做         
       int res = x.compareTo( t.element );            
       if( res < 0 )
           t.left = remove( x, t.left );
       else if( res > 0 )
           t.right = remove( x, t.right );
       else if( t.left != null && t.right != null ) //兩個 孩子
       {
           t.element = findMin( t.right ).element;//尋找右子樹最小的
           t.right = remove( t.element, t.right );
       }
       else
           t = ( t.left != null ) ? t.left : t.right;//一個孩子 這種情況只有一層
       return balance( t );
   }
   //確保平衡狀態(tài)
   private AVLNode<T> balance(AVLNode<T> t) {
       if(t==null)
           return t;
       if(height(t.left)-height(t.right)>1)//左子樹比右子樹深兩層及以上
           if(height(t.left.left)>=height(t.left.right))
               t=singleRotateLL(t);//左左單旋轉(zhuǎn)
           else
               t=doubleRotateLR(t);//左右雙旋轉(zhuǎn)
       else 
       if(height( t.right ) - height( t.left )>1)//右子樹比左子樹深兩層以上
           if(height( t.right.right ) >= height( t.right.left ))//右右單旋轉(zhuǎn)
               t=singleRotateRR(t);
           else 
               t=doubleRotateRL(t);//右左雙旋轉(zhuǎn)
       t.height=Math.max(height(t.left), height(t.right))+1;
       return t;
   }
   //右右單旋轉(zhuǎn)
   private AVLNode<T> singleRotateRR(AVLNode<T> k1) {
       AVLNode<T> k2 = k1.right;
       k1.right=k2.left;
       k2.left=k1;
       k1.height = Math.max( height( k1.left ), height( k1.right ) ) + 1;
       k2.height = Math.max( height( k2.right ), k1.height ) + 1;
       return k2;
   }
   //左左單旋轉(zhuǎn)
   private AVLNode<T> singleRotateLL(AVLNode<T> k2) {
       AVLNode<T> k1 = k2.left;
       k2.left = k1.right;
       k1.right = k2;
       k2.height = Math.max( height( k2.left ), height( k2.right ) ) + 1;
       k1.height = Math.max( height( k1.left ), k2.height ) + 1;
       return k1;
   }
   //右左雙旋轉(zhuǎn)
   private AVLNode<T> doubleRotateRL(AVLNode<T> k1) {
       //右子樹先左左單旋轉(zhuǎn)
       k1.right=singleRotateLL(k1.right);
       return singleRotateRR(k1);//再整個右右單旋轉(zhuǎn)
   }
   //左右雙旋轉(zhuǎn)
   private AVLNode<T> doubleRotateLR(AVLNode<T> k3) {
       //左子樹先右右單旋轉(zhuǎn)
       k3.left=singleRotateRR(k3.left);
       return singleRotateLL(k3);//再整個左左單旋轉(zhuǎn)
   }
   
   public static void main(String[] args) {
       AVLTree<Integer> tree=new AVLTree<Integer>();
       for(int i=1;i<=7;i++){
           tree.insert(i);
           tree.check();
       }
       tree.printTree();
       System.out.println("---------");
       for(int i=10;i<=16;i++){
           tree.insert(i);
           tree.check();
       }
       tree.insert(8);
       tree.insert(9);
       tree.printTree();
       System.out.println("----------");
       System.out.println(tree.findMin());
       System.out.println(tree.findMax());
       System.out.println(tree.root.height);
       System.out.println("--------------");
       System.out.println("沒有輸出說明成功了...");
       final int NUM=10000;
       for(int i=37;i!=0;i=(i+37)%NUM){//隨機(jī)插入
           //System.out.println(i);
           tree.insert(i);
       }
       for(int i=1;i<NUM;i+=2){//刪除所有奇數(shù)
           tree.remove(i);
       }
       for(int i=2;i<NUM;i+=2){
           if(!tree.contains(i))
               System.out.println("應(yīng)該存在的偶數(shù)缺失");
       }
       for(int i=1;i<NUM;i+=2){
           if(tree.contains(i))
               System.out.println("不該存在的奇數(shù)存在");
       }
   }
}

可以看到測試類里我們使用了偽隨機(jī)插入,這和線性同余稍有區(qū)別.足夠大的隨機(jī)數(shù)驗(yàn)證保證了AVL樹的強(qiáng)壯.

2.伸展樹

伸展樹同樣是一顆二叉查找樹.對于AVL樹而言,沒插入一次就會呈現(xiàn)旋轉(zhuǎn),影響了插入和刪除的效率,此時一個新的變種伸展樹就被提出了.
它的優(yōu)秀性能基于以下情況,如果我們每次都查詢相同的節(jié)點(diǎn)或者頻繁查詢該節(jié)點(diǎn),AVL樹在節(jié)點(diǎn)越來越多的情況下呈現(xiàn)下旋,復(fù)雜度只會遞增.而伸展樹的想法就是,查詢一個節(jié)點(diǎn)的時候就通過一些列類似AVL旋轉(zhuǎn)把它頂?shù)礁?jié)點(diǎn).這樣下次如果還是訪問該節(jié)點(diǎn),就特別方便.
基本上我們考慮以下兩種狀況,之字形與一字型.假設(shè)我們要查找X節(jié)點(diǎn),那么:

9

以上是之字形旋轉(zhuǎn),可以看到,類似于AVL的雙旋轉(zhuǎn).
還有一字型如下所示:
10

這種情況像是加強(qiáng)版的單旋轉(zhuǎn),需要做兩次單旋轉(zhuǎn).
當(dāng)然還有一種狀況,就是純粹的單旋轉(zhuǎn),比如X節(jié)點(diǎn)就是根節(jié)點(diǎn)的孩子,那么只要單旋轉(zhuǎn)一次就行了.
接下來將自頂向下伸展樹,這真是一種極好的實(shí)現(xiàn)方式,使得之字形與單旋轉(zhuǎn)幾乎不用工作,而一字型只需要一次單旋轉(zhuǎn)即可,剩余的工作交給分離與合并即可.
11

上圖即是三種情況分別對應(yīng)的操作(單旋轉(zhuǎn)查找Y,一字型查找Z,之字形查找Z),這種伸展方式把樹分為L樹,M樹與R樹,然后自頂向下查找元素,僅僅在一字型這種狀況時候需要先進(jìn)行單旋轉(zhuǎn)操作預(yù)處理.比較目標(biāo)與根節(jié)點(diǎn)的值,目標(biāo)小就把根節(jié)點(diǎn)分離到R樹,目標(biāo)更大就把根節(jié)點(diǎn)分離到L樹...一直到尋找到目標(biāo)或者尋找到離目標(biāo)最近的那個數(shù).
分離到最后一層后,再進(jìn)行合并操作即可:
12

上面即是自頂向下伸展樹的伸展方法(查找)方法的全過程.我們得到的是剛好是目標(biāo),或者目標(biāo)的前驅(qū)或后繼.那么我們在執(zhí)行插入操作的時候.僅僅是考慮插入數(shù)與根節(jié)點(diǎn)的大小關(guān)系插入即可,因?yàn)楦?jié)點(diǎn)的所有左子樹必然小于插入數(shù),根節(jié)點(diǎn)的右子樹必然大于插入數(shù).不用擔(dān)心子樹層及后面...
刪除的邏輯同樣很簡單,不再贅述.

  package com.fredal.structure; public class SplayTree<T extends Comparable<? super T>> {
    //內(nèi)部節(jié)點(diǎn)類
    private static class BinaryNode<T>{
        T element;
        BinaryNode<T> left;//左子樹
        BinaryNode<T> right;//右子樹
        public BinaryNode(T element) {
            this(element, null, null);
        }
        public BinaryNode(T element, BinaryNode<T> left, BinaryNode<T> right) {
            this.element = element;
            this.left = left;
            this.right = right;
        }    
    }  
    private BinaryNode<T> root;
    private BinaryNode<T> nullNode;//表示null引用
    private BinaryNode<T> newNode=null;//用于各種插入
    private BinaryNode<T> header=new BinaryNode<T>(null);//用于展開 作為頭節(jié)點(diǎn)

    public SplayTree(){
        nullNode=new BinaryNode<T>(null);
        nullNode.left=nullNode.right=nullNode;
        root=nullNode;
    }   
    //插入操作 進(jìn)行展開操作后 只要比較和根節(jié)點(diǎn)的大小進(jìn)行一次操作即可
    public void insert(T x){
        if(newNode==null)
            newNode=new BinaryNode<T>(null);
        newNode.element=x;
        if(root==nullNode){
            newNode.left=newNode.right=nullNode;
            root=newNode;
        }
        else{
            root=splay(x,root);//伸展操作 將目標(biāo)或者離目標(biāo)最近的那個頂?shù)礁?            int res=x.compareTo(root.element);
            if(res<0){
                newNode.left=root.left;
                newNode.right=root;
                root.left=nullNode;
                root=newNode;
            }else if(res>0){
                newNode.right=root.right;
                newNode.left=root;
                root.right=nullNode;
                root=newNode;
            }else
                return;//重復(fù)了
        }
        newNode=null;
    }
    //刪除操作
    public void remove(T x){
        if(!contains(x))//不包含 就返回
            return;
        BinaryNode<T> newTree;
        root=splay(x, root);
        if(root.left==nullNode)
            newTree=root.right;//左邊為空 直接右子樹接上 
        else{
            newTree=root.left;
            newTree=splay(x, newTree);//找到左子樹最大的作為根
            newTree.right=root.right;
        }
        root=newTree;
    }
    //尋找最大值
    public T findMax(){
        if(isEmpty())
            throw new RuntimeException("空了");
        BinaryNode<T> t=root;
        while(t.right!=nullNode)
            t=t.right;//找到最大值
        root=splay(t.element, root);//并伸展到根
        return t.element;
    }
    //尋找最小值
    public T findMin(){
        if(isEmpty())
            throw new RuntimeException("空了");
        BinaryNode<T> t=root;
        while(t.left!=nullNode)
            t=t.left;//找到最小值
        root=splay(t.element, root);//并伸展到根
        return t.element;
    }
    //是否包含
    public boolean contains(T x){
        if(isEmpty())
            return false;
        root=splay(x, root);
        return root.element.compareTo(x)==0;
    }
    //清空
    public void empty(){
        root=nullNode;
    }
    //判空
    public boolean isEmpty(){
        return root==nullNode;
    }
    //內(nèi)部方法展開 找到一個剛好等于或者剛好大于或者剛好小于目標(biāo)的數(shù)
    private BinaryNode<T> splay(T x, BinaryNode<T> t) {
        BinaryNode<T> leftTree,rightTree;//L R樹
        header.left=header.right=nullNode;
        leftTree=rightTree=header;
        nullNode.element=x;//保證匹配
        for(;;){
            int res=x.compareTo(t.element);
            if(res<0){
                //"一字型"旋轉(zhuǎn)
                if(x.compareTo(t.left.element)<0)
                    t=rotateL(t);
                if(t.left==nullNode)
                    break;
                //分離到R樹 同時備份在header中
                rightTree.left=t;
                rightTree=t;
                t=t.left;               
            }else if(res>0){
                //"一字型旋轉(zhuǎn)"
                if(x.compareTo(t.right.element)>0)
                    t=rotateR(t);
                if(t.right==nullNode)
                    break;
                //分離到L樹 同時備份在header中
                leftTree.right=t;
                leftTree=t;
                t=t.right;
            }else
                break;
        }
        //最后一次分裂
        leftTree.right=t.left;
        rightTree.left=t.right;
        //合并操作
        //注意header.right相當(dāng)于leftTree.right
        t.left = header.right;
        //header.left相當(dāng)于righttree.left
        t.right = header.left;
        return t;
    }
    //右右單旋轉(zhuǎn)
    private BinaryNode<T> rotateR(BinaryNode<T> k1) {
        BinaryNode<T> k2 = k1.right;
        k1.right=k2.left;
        k2.left=k1;
        return k2;
    }
    //左左單旋轉(zhuǎn)
    private BinaryNode<T> rotateL(BinaryNode<T> k2) {
        BinaryNode<T> k1 = k2.left;
        k2.left=k1.right;
        k1.right=k2;
        return k1;
    }    
    public static void main(String[] args) {
        SplayTree<Integer> tree=new SplayTree<Integer>();
        final int NUM=40000;
        System.out.println("如果程序不輸出就成功了....");
        for(int i=37;i!=0;i=(i+37)%NUM)
            tree.insert(i);//偽隨機(jī)
        for(int i=1;i<NUM;i+=2)
            tree.remove(i);//刪除所有奇數(shù)
        if( tree.findMin( ) != 2 || tree.findMax( ) != NUM - 2 )
            System.out.println( "最大值最小值尋找錯誤!" );
        for( int i = 2; i < NUM; i += 2 )
            if( !tree.contains( i ) )
                System.out.println( "偶數(shù)缺失" + i );
        for( int i = 1; i < NUM; i += 2 )
            if( tree.contains( i ) )
                System.out.println( "奇數(shù)多余" + i );
    }
}

總結(jié)伸展樹就是一個"頂"字.

3.紅黑樹

紅黑樹不愧是最難的數(shù)據(jù)結(jié)構(gòu)之一...
R-B Tree,紅黑樹,同樣是一顆特殊的二叉查找樹變種.
紅黑樹擁有四大性質(zhì):

  1. 每個節(jié)點(diǎn)或者是紅色,或者是黑色.
  2. 根是黑色的
  3. 如果一個節(jié)點(diǎn)是紅色的,那么其子節(jié)點(diǎn)必須是黑色的.
  4. 從一個節(jié)點(diǎn)到一個null引用(即邏輯末尾)的每一條路徑必須包含相同數(shù)目的黑色節(jié)點(diǎn).
    我們用雙圈表示紅色,一個例子如下:
    13

    紅黑樹的復(fù)雜度為(O log(N)),效率十分高,應(yīng)用十分廣泛,如java中的TreeSet,TreeMap,Linux虛擬內(nèi)存管理.

  • 復(fù)雜度相關(guān)證明

首先我們將會證明一顆含有n個節(jié)點(diǎn)的紅黑樹高度至多為2log(n+1).這個命題將保證查找操作是一種對數(shù)的操作,復(fù)雜度為O(log n).
然后上述命題的逆否命題為"高度為h的紅黑樹，它的包含的內(nèi)節(jié)點(diǎn)個數(shù)至少為 2h/2-1個".我們只需證明這個就行
從某個節(jié)點(diǎn)x出發(fā)（不包括該節(jié)點(diǎn)）到達(dá)一個葉節(jié)點(diǎn)的任意一條路徑上，黑色節(jié)點(diǎn)的個數(shù)稱為該節(jié)點(diǎn)的黑高度(x's black height)，記為bh(x).關(guān)于bh(x),我們可以得到兩點(diǎn):
a. 根據(jù)特性4,即從一個節(jié)點(diǎn)到一個null引用(即邏輯末尾)的每一條路徑必須包含相同數(shù)目的黑色節(jié)點(diǎn).得知bh(x)是唯一的.
b. 根據(jù)特性3.即如果一個節(jié)點(diǎn)是紅色的,那么其子節(jié)點(diǎn)必須是黑色的.得知bh(x)≥h/2.進(jìn)而得到證明"高度為h的紅黑樹,它包含的黑節(jié)點(diǎn)個數(shù)至少為2bh(x)-1個"即可.
接下來通過"數(shù)學(xué)歸納法"證明上述結(jié)論.

  1. 樹的高度為0,bh(x)為0,2bh(x)-1為0.命題成立.
  2. 假設(shè),當(dāng)樹高度為h-1,它包含的個數(shù)至少為2bh(x)-1-1.成立.
    當(dāng)樹的高度為h的時候,根節(jié)點(diǎn)x的左右子樹,高度為h-1,黑高度為bh(x)或bh(x)-1.
    則節(jié)點(diǎn)x所包含的節(jié)點(diǎn)至少是 ( 2bh(x)-1-1 ) + ( 2bh(x)-1-1 )+1 = 2bh(x)-1.原命題成立.

  • 插入

首先我們講旋轉(zhuǎn)時候都用avl樹的術(shù)語,和紅黑樹的旋轉(zhuǎn)正好相反,講的各種情況的鏡像也不再贅述...
這里是分為自底向上插入和自頂向下插入.首先默認(rèn)n為當(dāng)前點(diǎn),p為父節(jié)點(diǎn),g為祖父節(jié)點(diǎn),u為叔叔節(jié)點(diǎn),t為兄弟節(jié)點(diǎn),先講自底向上的插入:

  1. 如果插入的是根節(jié)點(diǎn),那么直接把此節(jié)點(diǎn)涂黑
  2. 插入的節(jié)點(diǎn)的父親是黑色的,啥也不做.

  3. n的叔叔即u是紅色的,這時候需要遞歸,我們在g上進(jìn)行遞歸


    14

  4. u是黑色的,n是右孩子,對p進(jìn)行右右單旋轉(zhuǎn)變到狀態(tài)5


    15

  5. u是黑色的,n是左孩子,對g點(diǎn)左左單旋轉(zhuǎn)


    16

情況3使得自底向上插入需要增加父親指針,結(jié)構(gòu)體變大,編程特麻煩.
所以我們考慮用自頂向下插入實(shí)現(xiàn),一個思路就是,使得u永遠(yuǎn)是黑色的,就是避免了情況3的出現(xiàn).
首先一種情況是碰到當(dāng)前節(jié)點(diǎn)有兩個紅兒子,那么就需要翻轉(zhuǎn)兩個孩子和當(dāng)前節(jié)點(diǎn)的顏色即可.如下:

17

這種情況只有在n的父節(jié)點(diǎn)也是紅色的時候才會沖突,同時我們可以保證叔叔節(jié)點(diǎn)u一定是黑色的.那么自然而然可以參考上面的情況4與5解決問題.

  • 刪除

同樣有自底向上和自頂向下兩種,算法導(dǎo)論以及大部分的博客都寫的自底向上的刪除.這種方法要分好多種情況,而且比較難理解,我自己看得云里霧里.具體可以參考(http://blog.csdn.net/v_JULY_v/article/details/6105630) ,有六篇...
我還是來講講自頂向下刪除,相對容易理解而且編碼簡單,雖然也蠻復(fù)雜.
首先可以分為兩個大類A和B,然后我們按步驟step區(qū)分順序.實(shí)在不想畫圖,網(wǎng)上找了圖,白色代表紅色,黑色代表黑色.x為當(dāng)前節(jié)點(diǎn),p為父節(jié)點(diǎn),t為兄弟節(jié)點(diǎn)
Step1:
Step1A:表示x的兩個孩子都是黑色的,下面分為三種情況
Step1A1:T有兩個黑色的孩子,p,x,t節(jié)點(diǎn)變色

18

Step1A2:T有一個紅色的左孩子,x,p變色,右左雙旋轉(zhuǎn):
19

Step1A3:T有一個紅色的右孩子,或者兩個都是紅色(這個放在上面也行的),這個..一字型旋轉(zhuǎn).x,p,t,r都變色
20

現(xiàn)在我們得到了紅色的x節(jié)點(diǎn),開始判斷:
Step1_2A:
Step1_2A1:不是要刪除的節(jié)點(diǎn):繼續(xù)下降,回到Step1初始階段
Step1_2A2:是要刪除的節(jié)點(diǎn):判斷是不是葉子節(jié)點(diǎn).如果是就直接刪除.不是的話,就要用右子樹上的最小值或者左子樹上的最大值代替x節(jié)點(diǎn)中的值.同時往右下或者左下降,回到Step1...
接下來是B情況了
Step1B:x至少有一個紅色的孩子,這里我們先判斷x是否是要找的值
Step1_2B1:x是要找的值:除了不用判斷是不是葉子節(jié)點(diǎn)外,和Step1_2A2相同...
Step1_2B2:x不是:那么繼續(xù)下降,分為兩種情況,落在紅孩子或者黑孩子上
Step1_2B2_1:落在紅色的節(jié)點(diǎn)上,回到Step1_2A.
Step1_2B2_2:落在黑色的節(jié)點(diǎn)上
21

22

把上面那幅圖的情況變成下面那副圖的情況,p,t變色,p右右單旋轉(zhuǎn).然后轉(zhuǎn)到了Step1A,或者Step1B.
我們以及完成了把當(dāng)前節(jié)點(diǎn)變成紅色,并且達(dá)到葉子節(jié)點(diǎn)刪除的過程.
Step2:把根節(jié)點(diǎn)染成黑色

  • 自頂向下紅黑樹的實(shí)現(xiàn)

刪除和插入都是采用自頂向下的,其實(shí)編碼有非常多要注意的地方.

  package com.fredal.structure;
import javax.print.attribute.standard.Finishings;
import javax.swing.border.Border;
public class RedBlackTree<T extends Comparable<? super T>> {
   // 內(nèi)部節(jié)點(diǎn)類
   private static class RedBlackNode<T> {
       T element;
       RedBlackNode<T> left;
       RedBlackNode<T> right;
       int color;// 顏色

       public RedBlackNode(T element) {
           this(element, null, null);
       }

       public RedBlackNode(T element, RedBlackNode<T> left,
               RedBlackNode<T> right) {
           this.element = element;
           this.left = left;
           this.right = right;
           color = RedBlackTree.BLACK;
       }

   }

   private static RedBlackNode header;// 頭結(jié)點(diǎn)
   private static RedBlackNode nullNode;// 邏輯空節(jié)點(diǎn)
   private static final int BLACK = 1;
   private static final int RED = 0;

   private static RedBlackNode current;
   private static RedBlackNode parent;
   private static RedBlackNode grand;
   private static RedBlackNode great;// 曾祖父
   private static RedBlackNode brother;// 兄弟節(jié)點(diǎn)

   public RedBlackTree() {
       nullNode = new RedBlackNode<T>(null);
       nullNode.left = nullNode.right = nullNode;
       header = new RedBlackNode<T>(null);
       header.left = header.right = nullNode;// 初始化
   }
      
   // 自頂向下插入
   public void insert(T item) {
       current = parent = grand = header;// 初始化
       nullNode.element = item;

       while (compare(item, current) != 0) {
           great = grand;
           grand = parent;
           parent = current;
           current = compare(item, current) < 0 ? current.left : current.right;

           // 如果有兩個紅孩子 進(jìn)行處理
           if (current.left.color == RED && current.right.color == RED)
               handleReorient(item);
       }

       if (current != nullNode)// 重復(fù)了
           return;
       current = new RedBlackNode<T>(item, nullNode, nullNode);// 插入節(jié)點(diǎn)
       if (compare(item, parent) < 0)
           parent.left = current;
       else
           parent.right = current;
       handleReorient(item);// 處理一下葉子 左右兩個null引用染黑
   }

   // 處理操作
   private void handleReorient(T item) {
       // 染色
       current.color = RED;
       current.left.color = BLACK;
       current.right.color = BLACK;

       if (parent.color == RED) {// 只有這種情況需要翻轉(zhuǎn)
           grand.color = RED;
           if ((compare(item, grand) < 0) != (compare(item, parent) < 0))// 之字形
               rotate(item, grand);// 先變成一字型
           current = rotate(item, great);
           current.color = BLACK;
       }
       header.right.color = BLACK;// 根節(jié)點(diǎn)染黑
   }

   private RedBlackNode<T> rotate(T item, RedBlackNode<T> parent) {
       if (compare(item, parent) < 0)
           // 返回旋轉(zhuǎn)后的根節(jié)點(diǎn)
           return parent.left = compare(item, parent.left) < 0 ? 
                   rotateL(parent.left): // LL旋轉(zhuǎn)
                   rotateR(parent.left);// LR旋轉(zhuǎn)
       else
           return parent.right = compare(item, parent.right) < 0 ? 
                   rotateL(parent.right): // RL旋轉(zhuǎn)
                   rotateR(parent.right);// RR旋轉(zhuǎn)
   }

   // 右右單旋轉(zhuǎn)
   private static RedBlackNode rotateR(RedBlackNode k1) {
       RedBlackNode k2 = k1.right;
       k1.right = k2.left;
       k2.left = k1;
       return k2;
   }

   // 左左單旋轉(zhuǎn)
   private static RedBlackNode rotateL(RedBlackNode k2) {
       RedBlackNode k1 = k2.left;
       k2.left = k1.right;
       k1.right = k2;
       return k1;
   }

   private int compare(T item, RedBlackNode<T> t) {
       if (t == header)// 由于我們把header.right作為根
           return 1;
       else
           return item.compareTo(t.element);
   }

   // 清空
   public void makeEmpty() {
       header.right = nullNode;
   }

   // 判空
   public boolean isEmpty() {
       return header.right == nullNode;
   }

   // 尋找最大值
   public T findMax() {
       if (isEmpty())
           throw new RuntimeException("這是空樹");
       RedBlackNode<T> itr = header.right;
       while (itr.right != nullNode)
           itr = itr.right;
       return itr.element;
   }

   // 尋找最小值
   public T findMin() {
       if (isEmpty())
           throw new RuntimeException("這是空樹");
       RedBlackNode<T> itr = header.right;
       while (itr.left != nullNode)
           itr = itr.left;
       return itr.element;
   }

   // 尋找值
   public RedBlackNode<T> find(T x, RedBlackNode<T> t) {
       RedBlackNode<T> parent = nullNode;
       while (t != nullNode && t.element != x) {
           parent = t;
           if (x.compareTo(t.element) < 0)
               t = t.left;
           else
               t = t.right;
       }
       if (t == nullNode)
           return parent;
       else
           return t;
   }

   // 是否包含
   public boolean contains(T x) {
       nullNode.element = x;
       current = header.right;
       for (;;) {
           if (x.compareTo((T) current.element) < 0)
               current = current.left;
           else if (x.compareTo((T) current.element) > 0)
               current = current.right;
           else if (current != nullNode)
               return true;
           else
               return false;
       }
   }

   // 打印樹
   public void printTree() {
       if (isEmpty())
           System.out.println("這是課空樹");
       else
           printTree(header.right,0);
   }

   // 中序遍歷
   private void printTree(RedBlackNode<T> t,int depth) {
       if (t != nullNode) {
           printTree(t.left,depth+1);
           for(int i=0;i<depth;i++)
               System.out.print("  ");
           System.out.println(t.element + ":"
                   + (t.color == 1 ? "black" : "red"));
           printTree(t.right,depth+1);
       }
   }

   // 刪除節(jié)點(diǎn)
   public void remove(T item) {
       header.color = RED;
       current = header.right;
       brother = header.left;
       grand = great = parent = header;

       while (current != nullNode) {
           // 1A
            if (current.left.color == BLACK && current.right.color == BLACK) {
               // 1A1
                if (brother.left.color == BLACK && brother.right.color == BLACK) {
                   parent.color = BLACK;
                   current.color = RED;
                   if(brother!=nullNode)
                    brother.color = RED;
               }
               // 要考慮鏡像
               else {
                   solve1A23();
               }
               // 完成染色current為紅色 父節(jié)點(diǎn)為黑色 開始判斷
               if (current.element == item)
                   item = findItem(item);// 完成前進(jìn)或者完成刪除
               else
                   normalDown(item);// 繼續(xù)下降
           } else {// 1B
                   // 先進(jìn)行判斷
               if (current.element != item)
                   normalDown(item);// 下降
               else
                   item = findItem(item);
               if (current == nullNode)
                   break;
               // 已經(jīng)完成下降
               if (current.color == BLACK) {// 下降到黑色
                   solve1B();
               } else if (current.element != item)// 下降到紅色 不是要找的 繼續(xù)下降
                   normalDown(item);
               else
                   item = findItem(item);
           }
       }
       // 2
       header.color = BLACK;
       header.right.color = BLACK;// 復(fù)原
   }
   //解決1A2和1A3
   private static void solve1A23(){
       if (parent.left == current) {// 左孩子
           if (brother.left.color == RED) {// 1A2
               current.color = RED;
               parent.color = BLACK;
               parent.right = rotateL(brother);
               if (grand.right == parent)
                   grand.right = rotateR(parent);
               else
                   grand.left = rotateR(parent);
           } else {// 1A3
               current.color = RED;
               parent.color = BLACK;
               brother.color = RED;
               brother.right.color = BLACK;

               if (grand.right == parent)
                   grand.right = rotateR(parent);
               else
                   grand.left = rotateR(parent);
           }
       } else {// 右孩子 鏡像操作
           if (brother.right.color == RED) {// 1A2
               current.color = RED;
               parent.color = BLACK;
               parent.left = rotateR(brother);
               if (grand.left == parent)
                   grand.left = rotateL(parent);
               else
                   grand.right = rotateL(parent);
           } else {// 1A3
               current.color = RED;
               parent.color = BLACK;
               brother.color = RED;
               brother.left.color = BLACK;

               if (grand.right == parent)
                   grand.right = rotateL(parent);
               else
                   grand.left = rotateL(parent);
           }
       }
   }
   //解決1B情況
   private static void solve1B(){
       brother.color = BLACK;
       parent.color = RED;
       if (parent.left == current) {
           if (grand.left == parent)
               grand.left = rotateR(parent);
           else
               grand.right = rotateR(parent);
           brother = parent.right;
       } else {// 鏡像
           if (grand.left == parent)
               grand.left = rotateL(parent);
           else
               grand.right = rotateL(parent);
           brother = parent.left;
       }
   }
   // 下降
   private void normalDown(T item) {
       if (compare(item, current) < 0) {
           grand = parent;
           parent = current;
           brother = parent.right;
           current = current.left;
       } else {
           grand = parent;
           parent = current;
           brother = parent.left;
           current = current.right;
       }

   }

   private T findItem(T item) {
       T temp;
       RedBlackNode<T> toDelete;
       // 先判斷是否是葉子節(jié)點(diǎn)
       if (current.left == nullNode && current.right == nullNode) {
           if (parent.right == current)// 左孩子
               parent.right = nullNode;
           else
               parent.left = nullNode;
           current = nullNode;
           temp = item;
       } else {// 不是葉子節(jié)點(diǎn)
           if (current.right != nullNode) {// 右子樹找一個最小的
               toDelete = find(item, current.right);
               current.element = toDelete.element;
               temp = toDelete.element;
               if (toDelete.color == RED) {// 找到的是紅色節(jié)點(diǎn)
                   current.right = deleteNode(toDelete, current.right);
                   current = nullNode;
               } else {
                   grand = parent;
                   parent = current;
                   brother = parent.left;
                   current = current.right;//下降循環(huán)直到葉子
               }
           } else {// 從左子樹找一個最大的
               toDelete = find(item, current.left);
               current.element = toDelete.element;
               temp = toDelete.element;
               if (toDelete.color == RED) {// 找到的是紅色節(jié)點(diǎn)
                   current.left = deleteNode(toDelete, current.left);
                   current = nullNode;
               } else {
                   grand = parent;
                   parent = current;
                   brother = parent.right;
                   current = current.left;//下降循環(huán)直到葉子
               }
           }
       }
       return temp;
   }

   // 刪除節(jié)點(diǎn)
   private RedBlackNode<T> deleteNode(RedBlackNode<T> target, RedBlackNode<T> t) {
       RedBlackNode<T> origin = t;
       RedBlackNode<T> parent = nullNode;
       while (t != target) {
           parent = t;
           if (target.element.compareTo(t.element) < 0)
               t = t.left;
           else
               t = t.right;
       }
       if (t == origin) {
           RedBlackNode<T> temp;
           if (t.right != nullNode)
               temp = t.right;
           else
               temp = t.left;
           return temp;
       }
       if (parent.right == t) {
           if (t.right != nullNode)
               parent.right = t.right;
           else
               parent.right = t.left;
       } else {
           if (t.right != nullNode)
               parent.left = t.right;
           else
               parent.left = t.left;
       }
       return origin;
   }

   public static void main(String[] args) {
       RedBlackTree<Integer> t = new RedBlackTree<Integer>();
       t.insert(10);
       t.insert(85);
       t.insert(15);
       t.insert(70);
       t.insert(20);
       t.insert(60);
       t.insert(30);
       t.insert(50);
       t.insert(65);
       t.insert(80);
       t.insert(90);
       t.insert(40);
       t.insert(5);
       t.insert(55);
       t.insert(45);
       t.printTree();
       System.out.println();
       t.remove(30);
       t.printTree();
       System.out.println();
       t.remove(40);
       t.printTree();
        System.out.println();
        t.remove(5);
        t.printTree();
        System.out.println();
        t.remove(70);
        t.printTree();
        System.out.println();
        t.remove(90);
        t.printTree();
        System.out.println();
        t.remove(85);
        t.printTree();
        System.out.println();
        t.remove(20);
        t.printTree();
        System.out.println();
        t.remove(45);
        t.printTree();
        System.out.println();
        t.remove(50);
        t.printTree();
        System.out.println();
        t.remove(55);
        t.printTree();
        System.out.println();
        t.remove(60);
        t.printTree();
        System.out.println();
        System.out.println();
        t.remove(80);
        t.printTree();
        System.out.println();
        t.remove(10);
        t.printTree();
        System.out.println();
        t.remove(15);
        t.printTree();
        System.out.println();
   }
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

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

  • 背景 一年多以前我在知乎上答了有關(guān)LeetCode的問題, 分享了一些自己做題目的經(jīng)驗(yàn)。 張土汪：刷leetcod...
    土汪閱讀 12,890評論 0贊 33
  • 紅黑樹是平衡二叉查找樹的一種。為了深入理解紅黑樹，我們需要從二叉查找樹開始講起。 BST 二叉查找樹（Binary...
    kanehe閱讀 1,454評論 0贊 8
  • 紅黑樹為一棵二叉搜索樹，它為每個結(jié)點(diǎn)增加一個變量存儲結(jié)點(diǎn)顏色，利用結(jié)點(diǎn)顏色對樹的形狀進(jìn)行約束，使其近似平衡（并非完...
    LRC_cheng閱讀 532評論 0贊 1
  • 成都的秋和夏總是纏纏綿綿，直到十一月，也不盡然是完全的秋，偶爾還要來個二十多度，給人一種快要夏天的錯覺。街道上，...
    yi梓君閱讀 288評論 0贊 0
  • 最近睡眠一般吧，因?yàn)槔献鰤?，早晨起來很累，像沒有睡一般，這就是淺睡眠吧同時，最近做了很多奇怪的夢1、去知乎一對情侶...
    田田kyle閱讀 174評論 0贊 0

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