AA樹

紅黑樹的編程相當(dāng)復(fù)雜,AA樹是一顆帶有條件的紅黑樹,相當(dāng)情況下簡化了紅黑樹的編程.

1. AA樹規(guī)定只有右孩子才能是紅色節(jié)點(diǎn).
2. 我們不再記錄顏色,而是用level和每個(gè)節(jié)點(diǎn)存在一起.level實(shí)際上相當(dāng)與紅黑樹的black-height.
3. 紅節(jié)點(diǎn)的level與其父節(jié)點(diǎn)相同
4. 黑節(jié)點(diǎn)的level比其父節(jié)點(diǎn)低1
5. 樹葉節(jié)點(diǎn)level為1

我們把顏色轉(zhuǎn)化為層次來看,可以發(fā)現(xiàn)左兒子必然比它的父節(jié)點(diǎn)恰好低1,右兒子可能比父節(jié)點(diǎn)低0或1.
水平鏈接出現(xiàn)在一個(gè)節(jié)點(diǎn)與相等層次的兒子之間的連接,由上面那些性質(zhì)我們可以發(fā)現(xiàn),水平鏈接一般都是向右的.

23

1. 水平左鏈接,這違反了AA樹自身的條件.
2. 連續(xù)右鏈接,這相當(dāng)于違反了紅黑樹中紅節(jié)點(diǎn)的孩子不能也是紅的.

對于上面兩種情況,我們可以相應(yīng)采用skew方法以及split方法處理.

24

25

  package com.fredal.structure;
public class AATree<AnyType extends Comparable<? super AnyType>>
{
    //內(nèi)部節(jié)點(diǎn)類
   private static class AANode<AnyType>
   {

       AANode( AnyType theElement, AANode<AnyType> lt, AANode<AnyType> rt )
       {
           element = theElement;
           left    = lt;
           right   = rt;
           level   = 1;
       }

       AnyType         element;      
       AANode<AnyType> left;        
       AANode<AnyType> right;        
       int             level;        // 層次
   }
   
   private AANode<AnyType> root;
   private AANode<AnyType> nullNode;
   
   private AANode<AnyType> deletedNode;
   private AANode<AnyType> lastNode;
   
   public AATree( )
   {
       nullNode = new AANode<AnyType>( null, null, null );
       nullNode.left = nullNode.right = nullNode;
       nullNode.level = 0;
       root = nullNode;
   }

   public void insert( AnyType x )
   {
       root = insert( x, root );
   }
   public void remove( AnyType x )
   {
       deletedNode = nullNode;
       root = remove( x, root );
   }
   //最小值
   public AnyType findMin( )
   {
       if( isEmpty( ) )
           return null;

       AANode<AnyType> ptr = root;

       while( ptr.left != nullNode )
           ptr = ptr.left;

       return ptr.element;
   }
   //最大值
   public AnyType findMax( )
   {
       if( isEmpty( ) )
           return null;

       AANode<AnyType> ptr = root;

       while( ptr.right != nullNode )
           ptr = ptr.right;

       return ptr.element;
   }
   //尋找值并返回
   public AnyType find( AnyType x )
   {
       AANode<AnyType> current = root;
       nullNode.element = x;

       for( ; ; )
       {
           if( x.compareTo( current.element ) < 0 )
               current = current.left;
           else if( x.compareTo( current.element ) > 0 ) 
               current = current.right;
           else if( current != nullNode )
               return current.element;
           else
               return null;
       }
   }
   //情空
   public void makeEmpty( )
   {
       root = nullNode;
   }
   //判空
   public boolean isEmpty( )
   {
       return root == nullNode;
   }
   //插入
   private AANode<AnyType> insert( AnyType x, AANode<AnyType> t )
   {
       if( t == nullNode )
           t = new AANode<AnyType>( x, nullNode, nullNode );//初始化
       else if( x.compareTo( t.element ) < 0 )
           t.left = insert( x, t.left );
       else if( x.compareTo( t.element ) > 0 )
           t.right = insert( x, t.right );
       else
           ;//重復(fù)值
       t = skew( t );//先skew 再split
       t = split( t );
       return t;
   }
   //刪除
   private AANode<AnyType> remove( AnyType x, AANode<AnyType> t )
   {
       if( t != nullNode )
       {
           // 往下搜索并設(shè)置lastnode和deletenode
           lastNode = t;
           if( x.compareTo( t.element ) < 0 )
               t.left = remove( x, t.left );
           else
           {
               deletedNode =  t;//要?jiǎng)h除的值
               t.right = remove( x, t.right );//找右子樹最小值
           }

           //在底層 直接刪除
           if( t==lastNode)
           {
               if( deletedNode == nullNode || x.compareTo( deletedNode.element ) != 0 )
                   throw new RuntimeException( x.toString( ) );
               deletedNode.element = t.element;
               t = t.right;//必定有右孩子
           }
           //不在底層 需要重新平衡
           else
               if( t.left.level < t.level - 1 || t.right.level < t.level - 1 )//低兩層 因?yàn)橛衝ullNode
               {
                   if( t.right.level > --t.level )//右子樹降一層
                       t.right.level = t.level;
                   t = skew( t );//三次skew
                   t.right = skew( t.right );
                   t.right.right = skew( t.right.right );
                   t = split( t );//兩次split
                   t.right = split( t.right );
               }
       }
       return t;
   }

   private static <AnyType> AANode<AnyType> skew( AANode<AnyType> t )
   {
       if( t.left.level == t.level )
           t = rotateWithLeftChild( t );
       return t;
   }
   
   private static <AnyType> AANode<AnyType> split( AANode<AnyType> t )
   {
       if( t.right.right.level == t.level )
       {
           t = rotateWithRightChild( t );
           t.level++;
       }
       return t;
   }

   private static <AnyType> AANode<AnyType> rotateWithLeftChild( AANode<AnyType> k2 )
   {
       AANode<AnyType> k1 = k2.left;
       k2.left = k1.right;
       k1.right = k2;
       return k1;
   }

   private static <AnyType> AANode<AnyType> rotateWithRightChild( AANode<AnyType> k1 )
   {
       AANode<AnyType> k2 = k1.right;
       k1.right = k2.left;
       k2.left = k1;
       return k2;
   }  

   public static void main( String [ ] args )
   {
       AATree<Integer> tree=new AATree<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( "最大值最小值尋找錯(cuò)誤!" );

       for( int i = 2; i < NUM; i += 2 )
           if( tree.find(i)!=i )
               System.out.println( "偶數(shù)缺失" + i );

       for( int i = 1; i < NUM; i += 2 )
           if( tree.find(i)!=null)
               System.out.println( "奇數(shù)多余" + i );
   }
}

treap樹

treap樹是一種二叉查找樹,但是十分簡單.顧名思義我們可以知道,它是堆和樹的合體,在樹中維護(hù)了一個(gè)"優(yōu)先級",而優(yōu)先級具有堆性質(zhì).
采用隨機(jī)數(shù)的方式為"優(yōu)先級"賦值,并且滿足堆性質(zhì),而同時(shí)節(jié)點(diǎn)本身的值滿足二叉查找樹性質(zhì).

26

27

28

29

  package com.fredal.structure;
public class TreapTree<T extends Comparable<? super T>> {

    //內(nèi)部節(jié)點(diǎn)類
    static class TreapNode<T>{
        T element;
        TreapNode<T> left;
        TreapNode<T> right;
        int priority;//優(yōu)先級
        
        private static Random random=new Random();//隨機(jī)數(shù)產(chǎn)生器

        TreapNode(T element, TreapNode<T> left, TreapNode<T> right) {
            this.element = element;
            this.left = left;
            this.right = right;
            this.priority = random.RandomInt();//隨機(jī)產(chǎn)生
        }
        
        TreapNode(T element){
            this(element, null, null);
        }
        
    }
    private TreapNode<T> root;
    private TreapNode<T> nullNode;
    
    public TreapTree(){
        nullNode=new TreapNode<T>(null);
        nullNode.left=nullNode.right=nullNode;
        nullNode.priority=Integer.MAX_VALUE;//設(shè)為無限大
        root=nullNode;
    }
    
    public void insert(T x){
        root=insert(x,root);
    }
    //插入操作
    private TreapNode<T> insert(T x, TreapNode<T> t) {
        if(t==nullNode)
            return new TreapNode<T>(x, nullNode, nullNode);
        int res=x.compareTo(t.element);
        if(res<0){
            t.left=insert(x, t.left);
            if(t.left.priority<t.priority)//左左旋轉(zhuǎn)
                t=rotateL(t);
        }else if(res>0){
            t.right=insert(x, t.right);
            if(t.right.priority<t.priority)
                t=rotateR(t);
        }
        return t;
    }
    
    // 右右單旋轉(zhuǎn)
    private static TreapNode rotateR(TreapNode k1) {
        TreapNode k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;
        return k2;
    }

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

    public void remove(T x){
        root=remove(x,root);
    }
    private TreapNode<T> remove(T x, TreapNode<T> t) {
        if(t!=nullNode){
            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.priority<t.right.priority)
                    t=rotateL(t);//左左旋轉(zhuǎn)
                else
                    t=rotateR(t);//右右旋轉(zhuǎn)
                if(t!=nullNode)
                    t=remove(x, t);//繼續(xù)遞歸
                else
                    t.left=nullNode;//旋轉(zhuǎn)后剛好等于刪除節(jié)點(diǎn)
            }
        }
        return t;
    }

    //最小值
    public T findMin(){
        if(isEmpty())
            throw new RuntimeException("空樹");
        TreapNode<T> ptr=root;
        while(ptr.left!=nullNode)
            ptr=ptr.left;
        return ptr.element;
    }
    //最大值
    public T findMax(){
        if(isEmpty())
            throw new RuntimeException("空樹");
        TreapNode<T> ptr=root;
        while(ptr.right!=nullNode)
            ptr=ptr.right;
        return ptr.element;
    }
    //是否存在
    public boolean contains(T x){
        TreapNode<T> current=root;
        nullNode.element=x;
        for(;;){
            int res=x.compareTo(current.element);
            if(res<0)
                current=current.left;
            else if(res>0)
                current=current.right;
            else
                return current!=nullNode;
        }
    }
    //情空
    public void makeEmpty(){
        root=nullNode;
    }
    //判空
    public boolean isEmpty(){
        return root==nullNode;
    }
    //打印
    public void printTree(){
        if(isEmpty())
            System.out.println("這是空樹");
        else
            printTree(root);
    }
    
    private void printTree(TreapNode<T> t) {
        if(t!=nullNode){
            printTree(t.left);
            System.out.println(t.element.toString());
            printTree(t.right);
        }
    }
    
    public static void main(String[] args) {
        TreapTree<Integer> tree=new TreapTree<Integer>();
        tree.insert(6);
        tree.insert(10);
        tree.insert(8);
        tree.insert(12);
        tree.insert(14);
        tree.insert(16);
        tree.printTree();
        tree.makeEmpty();
        
        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( "最大值最小值尋找錯(cuò)誤!" );

        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 );
    }
}

k-d樹

如果要篩選出年齡30到35歲之間并且年薪在20萬到50萬的人士,這種問題叫做二維范圍查找.當(dāng)然相應(yīng)地還有k維.
我們可以使2-d樹(k-d樹)來解決問題,它的性質(zhì)如下.
在奇數(shù)層上的分支按照第一個(gè)關(guān)鍵字進(jìn)行二叉排序.在偶數(shù)層上按照第二個(gè)關(guān)鍵字進(jìn)行排序.
性質(zhì)非常簡單,編碼也非常簡單.注意如果關(guān)鍵字重復(fù)了,我們默認(rèn)把它放到右子樹,如果重復(fù)太多顯然是比較壞的情況.
k-d樹最壞情況是O(N),不像二叉查找樹那樣有紅黑樹等等最壞情況(O log N)的變種,因?yàn)樾D(zhuǎn)在這行不通.
k近鄰搜索是關(guān)于k-d樹的經(jīng)典的例子,首先通過二叉樹搜索（比較待查詢節(jié)點(diǎn)和分裂節(jié)點(diǎn)的分裂維的值笼恰，小于等于就進(jìn)入左子樹分支猫妙，等于就進(jìn)入右子樹分支直到葉子結(jié)點(diǎn)），順著“搜索路徑”很快能找到最近鄰的近似點(diǎn)倦畅，也就是與待查詢點(diǎn)處于同一個(gè)子空間的葉子結(jié)點(diǎn)驰弄；然后再回溯搜索路徑蝠筑，并判斷搜索路徑上的結(jié)點(diǎn)的其他子結(jié)點(diǎn)空間中是否可能有距離查詢點(diǎn)更近的數(shù)據(jù)點(diǎn)，如果有可能揩懒，則需要跳到其他子結(jié)點(diǎn)空間中去搜索（將其他子結(jié)點(diǎn)加入到搜索路徑）。重復(fù)這個(gè)過程直到搜索路徑為空挽封。我們在這不做代碼演示.
給出k-d樹,應(yīng)該說2-d數(shù)基本的插入以及篩選范圍的代碼實(shí)例

  package com.fredal.structure;
//2-d樹
public class KDTree<T extends Comparable<? super T>> {
    private static class KDNode<T>{
        T[] data;//數(shù)組形式
        KDNode<T> left;
        KDNode<T> right;
        
        KDNode(T item[]){
            data=(T[]) new Comparable[2];
            data[0]=item[0];
            data[1]=item[1];
            left=right=null;
        }
    }    
    
    private KDNode<T> root;//根節(jié)點(diǎn)
    
    public KDTree(){
        root=null;
    }
    
    public void insert(T[] x){
        root=insert(x,root,0);
    }
    //插入
    private KDNode<T> insert(T[] x, KDNode<T> t, int level) {
        if(t==null)
            t=new KDNode<T>(x);
        else if(x[level].compareTo(t.data[level])<0)
            t.left=insert(x, t.left, 1-level);//每層關(guān)鍵字更替
        else//相同的話都?xì)w到右子樹
            t.right=insert(x, t.right, 1-level);
        return t;
    }
    
    public void printRange(T[] low,T[] high){
        printRange(low,high,root,0);
    }
    //篩選方法
    private void printRange(T[] low, T[] high, KDNode<T> t, int level) {
        if(t!=null){
            if(low[0].compareTo(t.data[0])<=0&&
                    low[1].compareTo(t.data[1])<=0&&
                    high[0].compareTo(t.data[0])>=0&&
                    high[1].compareTo(t.data[1])>=0)
                System.out.println(t.data[0]+","+t.data[1]);//輸出
            if(low[level].compareTo(t.data[level])<=0)
                printRange(low, high, t.left, 1-level);//下界 下一層
            if(high[level].compareTo(t.data[level])>=0)
                printRange(low, high, t.right, 1-level);//上界 下一層
        }
    }
    
    public static void main(String[] args) {
        KDTree<Integer> t=new KDTree<Integer>();
        for(int i=300;i<370;i++){
            Integer[] it=new Integer[2];
            it[0]=i;
            it[1]=2500-i;
            t.insert(it);
        }
        
        Integer[] low={300,2100};
        Integer[] high={350,2200};
        
        t.printRange(low, high);
    }
}

B樹

在大規(guī)模存儲(chǔ)數(shù)據(jù)的時(shí)候,往往樹深度過深而導(dǎo)致性能不佳,那么顯然需要想辦法減少深度,一個(gè)自然的想法即是一個(gè)節(jié)點(diǎn)有多個(gè)孩子,類似多叉樹這樣.
B樹是為了磁盤或其它存儲(chǔ)設(shè)備而設(shè)計(jì)的一種多叉（下面你會(huì)看到已球，相對于二叉臣镣，B樹每個(gè)內(nèi)結(jié)點(diǎn)有多個(gè)分支，即多叉）平衡查找樹,我們這里暫且不討論B+,B*等.
我們可以用階段定義B樹,也可以用度定義B樹,以度為例子,一顆度為m的B樹:

1. 每個(gè)非根的內(nèi)結(jié)點(diǎn)至多有m個(gè)子女智亮，每個(gè)非根的結(jié)點(diǎn)必須至少含有m-1個(gè)關(guān)鍵字忆某，如果樹是非空的，則根結(jié)點(diǎn)至少包含一個(gè)關(guān)鍵字阔蛉；
2. 每個(gè)結(jié)點(diǎn)可包含至多2m-1個(gè)關(guān)鍵字弃舒。所以一個(gè)內(nèi)結(jié)點(diǎn)至多可有2m個(gè)子女。如果一個(gè)結(jié)點(diǎn)恰好有2m-1個(gè)關(guān)鍵字状原，我們就說這個(gè)結(jié)點(diǎn)是滿的

插入:插入相對來說比較簡單

1. 利用前述的B-樹的查找算法查找關(guān)鍵字的插入位置聋呢。若找到，則說明該關(guān)鍵字已經(jīng)存在颠区，直接返回削锰。否則查找操作必失敗于某個(gè)最低層的非終端結(jié)點(diǎn)上。
2. 判斷該結(jié)點(diǎn)是否還有空位置毕莱。即判斷該結(jié)點(diǎn)的關(guān)鍵字總數(shù)是否滿足n<=m-1器贩。若滿足，則說明該結(jié)點(diǎn)還有空位置朋截，直接把關(guān)鍵字k插入到該結(jié)點(diǎn)的合適位置上蛹稍。若不滿足，說明該結(jié)點(diǎn)己沒有空位置部服，需要把結(jié)點(diǎn)分裂成兩個(gè)唆姐。

分裂的方法是：生成一新結(jié)點(diǎn)。把原結(jié)點(diǎn)上的關(guān)鍵字和k按升序排序后饲宿，從中間位置把關(guān)鍵字（不包括中間位置的關(guān)鍵字）分成兩部分厦酬。左部分所含關(guān)鍵字放在舊結(jié)點(diǎn)中，右部分所含關(guān)鍵字放在新結(jié)點(diǎn)中瘫想，中間位置的關(guān)鍵字連同新結(jié)點(diǎn)的存儲(chǔ)位置插入到父結(jié)點(diǎn)中仗阅。如果父結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)也超過（m-1），則要再分裂国夜，再往上插减噪。直至這個(gè)過程傳到根結(jié)點(diǎn)為止。

30

31

32

33

刪除:在B-樹上刪除關(guān)鍵字k的過程分兩步完成：

1. 利用B-樹的查找算法找出該關(guān)鍵字所在的結(jié)點(diǎn)车吹。然后根據(jù) k所在結(jié)點(diǎn)是否為葉子結(jié)點(diǎn)有不同的處理方法筹裕。
2. 若該結(jié)點(diǎn)為非葉結(jié)點(diǎn)，且被刪關(guān)鍵字為該結(jié)點(diǎn)中第i個(gè)關(guān)鍵字key[i]窄驹，則可從指針son[i]所指的子樹中找出最小關(guān)鍵字Y朝卒，代替key[i]的位置，然后在葉結(jié)點(diǎn)中刪去Y乐埠。

因此抗斤，把在非葉結(jié)點(diǎn)刪除關(guān)鍵字k的問題就變成了刪除葉子結(jié)點(diǎn)中的關(guān)鍵字的問題了囚企。在B-樹葉結(jié)點(diǎn)上刪除一個(gè)關(guān)鍵字的方法是
首先將要?jiǎng)h除的關(guān)鍵字 k直接從該葉子結(jié)點(diǎn)中刪除。然后根據(jù)不同情況分別作相應(yīng)的處理瑞眼，共有三種可能情況：

1. 如果被刪關(guān)鍵字所在結(jié)點(diǎn)的原關(guān)鍵字個(gè)數(shù)不貧困龙宏，說明刪去該關(guān)鍵字后該結(jié)點(diǎn)仍滿足B-樹的定義。只需從該結(jié)點(diǎn)中直接刪去關(guān)鍵字即可伤疙。
2. 如果被刪關(guān)鍵字所在結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)沒脫貧银酗，說明刪去該關(guān)鍵字后該結(jié)點(diǎn)將不滿足B-樹的定義，需要調(diào)整徒像。
   調(diào)整過程為：如果其左右兄弟結(jié)點(diǎn)中有“多余”的關(guān)鍵字,即與該結(jié)點(diǎn)相鄰的右（左）兄弟結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目多余黍特。則可將右（左）兄弟結(jié)點(diǎn)中最小（大）關(guān)鍵字上移至雙親結(jié)點(diǎn)厨姚。而將雙親結(jié)點(diǎn)中行瞥骸（大）于該上移關(guān)鍵字的關(guān)鍵字下移至被刪關(guān)鍵字所在結(jié)點(diǎn)中,相當(dāng)于一次旋轉(zhuǎn)。
3. 如果左右兄弟結(jié)點(diǎn)中沒有“多余”的關(guān)鍵字谬墙，即與該結(jié)點(diǎn)相鄰的右（左）兄弟結(jié)點(diǎn)中的關(guān)鍵字?jǐn)?shù)目均貧困1今布。這種情況比較復(fù)雜。需把要?jiǎng)h除關(guān)鍵字的結(jié)點(diǎn)與其左（或右）兄弟結(jié)點(diǎn)以及雙親結(jié)點(diǎn)中分割二者的關(guān)鍵字合并成一個(gè)結(jié)點(diǎn),即在刪除關(guān)鍵字后拭抬，該結(jié)點(diǎn)中剩余的關(guān)鍵字加指針部默，加上雙親結(jié)點(diǎn)中的關(guān)鍵字Ki（是雙親結(jié)點(diǎn)指向該刪除關(guān)鍵字結(jié)點(diǎn)的左（右）兄弟結(jié)點(diǎn)的指針）所指的兄弟結(jié)點(diǎn)中去。如果因此使雙親結(jié)點(diǎn)中關(guān)鍵字個(gè)數(shù)貧困了造虎，則對此雙親結(jié)點(diǎn)做同樣處理傅蹂。以致于可能直到對根結(jié)點(diǎn)做這樣的處理而使整個(gè)樹減少一層。

總之算凿，設(shè)所刪關(guān)鍵字為非終端結(jié)點(diǎn)中的Ki份蝴，則可以指針Ai所指子樹中的最小關(guān)鍵字Y代替Ki，然后在相應(yīng)結(jié)點(diǎn)中刪除Y氓轰。對任意關(guān)鍵字的刪除都可以轉(zhuǎn)化為對最下層關(guān)鍵字的刪除婚夫。

34

35

36

37

實(shí)現(xiàn):

  package com.fredal.structure;

import java.util.Stack;

public class BTree {

    private int T;//度
    private Node root;//根
    //內(nèi)部節(jié)點(diǎn)類
    public class Node {
        int n;//個(gè)數(shù)
        int key[] = new int[2*T-1];
        Node child[] = new Node[2*T];
        boolean leaf = true;
        //試匹配
        public int Find(int k){
            for (int i = 0 ; i < this.n ; i++) {
                if (this.key[i] == k) {
                    return i;
                }
            }
            return -1;
        };
    }
    
    public BTree(int _T) {
        T = _T;
        root = new Node();
        root.n = 0;
        root.leaf = true;//剛開始都是樹葉
    }
    //搜索    
    private Node Search (Node x,int key) {
        int i = 0;
        if (x == null) return x;
        for (i = 0 ; i < x.n ; i++) {
            if (key < x.key[i])
                break;
            if (key == x.key[i])//找到了1
                return x;
        }
        if (x.leaf)
            return null;//沒東西查了
        else 
            return Search(x.child[i],key);//找子節(jié)點(diǎn)去
    }
    //插入
    public void Insert (final int key) {
        Node r = root;
        if (r.n == 2*T - 1 ) {//滿了
            Node s = new Node();
            root = s;//root上升
            s.leaf = false;//變成不是葉子
            s.n = 0;
            s.child[0] = r;
            Split(s,0,r);//分裂
            _Insert(s,key);//直接插入
        } else {
            _Insert(r,key);//直接插入
        }
    }
    //分裂(合并) x-父節(jié)點(diǎn) pos-是第幾個(gè)孩子 y-要分裂的節(jié)點(diǎn)
    private void Split (Node x , int pos , Node y) {
        Node z = new Node();
        z.leaf = y.leaf;
        z.n = T - 1;//更新大小
        for (int j = 0 ; j < T - 1 ; j++) {
            z.key[j] = y.key[j+T];//賦值 對半分
        }
        if (! y.leaf) {//不是葉子節(jié)點(diǎn) 重新分配子節(jié)點(diǎn)
            for (int j = 0 ; j < T ; j++) 
                z.child[j] = y.child[j+T];//子節(jié)點(diǎn)也分對半
        }
        y.n = T-1;//更新大小
        for (int j = x.n ; j >= pos+1 ; j--)
            x.child[j+1] = x.child[j];//挪位
        x.child[pos+1] = z;//插入     
        for (int j = x.n-1 ; j >= pos ; j--)//挪位
            x.key[j+1] = x.key[j];
        x.key[pos] = y.key[T-1];//插入
        x.n = x.n + 1;
    }
    //根不滿時(shí)候插入
    final private void _Insert (Node x , int k) {   
        if (x.leaf) {//葉子節(jié)點(diǎn) 直接插入
            int i = 0;
            for (i = x.n-1 ; i >= 0 && k < x.key[i] ; i--)
                x.key[i+1] = x.key[i];
            x.key[i+1] = k;
            x.n = x.n + 1; 
        } else {
            int i = 0;
            for (i = x.n-1 ; i >= 0 && k < x.key[i] ; i--){};//找合適的孩子節(jié)點(diǎn)插
            i++;
            Node tmp = x.child[i];
            if (tmp.n == 2*T -1) {//孩子節(jié)點(diǎn)滿了
                Split(x,i,tmp);//分裂與合并
                if ( k > x.key[i])//再找一遍
                    i++;
            }
            _Insert(x.child[i], k);//插入子節(jié)點(diǎn)
        }
        
    }
    
    public void Show () {
        Show(root);
    }
    //打印
    private void Show (Node x) {
        assert(x == null);
        System.out.print(x.leaf +":" );
        for ( int i = 0 ; i < x.n ; i++) {
            System.out.print(x.key[i]+ " ");
        }
        System.out.println();
        if (!x.leaf) {
            for (int i = 0 ;i <  x.n + 1; i++) {
                Show(x.child[i]);//輸出子節(jié)點(diǎn)
            }
        }
    }
    
    public void Remove (int key) {
        Node x = Search(root, key);
        if (x == null) {
            return;
        }
        Remove(root,key);
    }
    //刪除    
    private void Remove (Node x , int key) {
        int pos = x.Find(key);//先試匹配
        if (pos != -1) {//找到了 說明當(dāng)前就包含要?jiǎng)h除的
            if (x.leaf) {//刪除的是葉子節(jié)點(diǎn)
                int i = 0 ;
                for (i = 0 ; i < x.n && x.key[i] != key ; i++){};//找到刪除位置
                for ( ; i < x.n ; i++) {
                    if (i != 2*T - 2){
                        x.key[i] = x.key[i+1];
                    }
                }
                x.n--;
                return;
            }
            if (!x.leaf){//刪除的不是葉子節(jié)點(diǎn)
                    Node pred = x.child[pos];//當(dāng)前節(jié)點(diǎn)元素的右節(jié)點(diǎn)
                    int predKey = 0;
                    if (pred.n >= T) {//不貧困
                        for (;;) {
                            if (pred.leaf) {//是葉子
                                predKey = pred.key[pred.n - 1];
                                break;
                            } else {//繼續(xù)往下 循環(huán)直到葉子
                                pred = pred.child[pred.n];
                            }
                        }
                        Remove (pred, predKey);//葉子 直接刪除
                        x.key[pos] = predKey;//移到父節(jié)點(diǎn)去
                        return;
                    }
                    //自己貧困了 看看兄弟節(jié)點(diǎn)
                    Node nextNode = x.child[pos+1];
                    if (nextNode.n >= T) {//兄弟節(jié)點(diǎn)不貧困
                        int nextKey = nextNode.key[0];
                        if (!nextNode.leaf){//不是葉子
                            nextNode = nextNode.child[0];
                            for (;;) {
                                if (nextNode.leaf) {//是葉子
                                    nextKey = nextNode.key[nextNode.n-1];
                                    break;
                                } else {
                                    nextNode = nextNode.child[nextNode.n];//往下降直到葉子
                                }
                            }
                        }
                        Remove(nextNode, nextKey);//刪除
                        x.key[pos] = nextKey;//移到父節(jié)點(diǎn)
                        return;
                    }
                    //都貧困
                    int temp = pred.n + 1;
                    pred.key[pred.n++] = x.key[pos];//先從父節(jié)點(diǎn)借一個(gè)
                    for (int i = 0, j = pred.n ; i < nextNode.n ; i++) {//和兄弟合并
                        pred.key[j++] = nextNode.key[i];
                        pred.n++;
                    }
                    for (int i = 0 ; i < nextNode.n+1 ; i++){//子節(jié)點(diǎn)也合并
                        pred.child[temp++] = nextNode.child[i];
                    }               
                    x.child[pos] = pred;//更新
                    for (int i = pos ; i < x.n ; i++) {//父節(jié)點(diǎn)關(guān)鍵字更新
                        if (i != 2*T - 2) {
                            x.key[i] = x.key[i+1];
                        }
                    }
                    for (int i = pos+1 ; i < x.n+1 ; i++) {//父節(jié)點(diǎn)孩子節(jié)點(diǎn)更新
                        if (i != 2*T - 1) {
                            x.child[i] = x.child[i+1];
                        }
                    }
                    x.n--;//個(gè)數(shù)遞減
                    if (x.n == 0) {
                        if (x == root) {
                            root = x.child[0];
                        }
                        x = x.child[0];
                    }
                    Remove(pred,key);//刪除
                    return;
            }
        } else {//沒找到 當(dāng)前不包含刪除的
            for (pos = 0 ; pos < x.n ; pos++) {
                if (x.key[pos] > key)//尋找包含目標(biāo)的孩子節(jié)點(diǎn)
                    break;
            }
            Node tmp = x.child[pos];//找到的這個(gè)節(jié)點(diǎn)
            if (tmp.n >= T) {//不貧困 就刪除(不一定就找到了,可能只是包含)
                Remove (tmp,key);
                return;
            }
            if (true) {
                Node nb = null;
                int devider = -1;
                if (pos != x.n && x.child[pos+1].n >= T) {//右孩子不貧困
                    devider = x.key[pos];
                    nb = x.child[pos+1];
                    x.key[pos] = nb.key[0];//父節(jié)點(diǎn)借用孩子節(jié)點(diǎn)
                    tmp.key[tmp.n++] = devider;//借用父節(jié)點(diǎn),相當(dāng)于一次旋轉(zhuǎn)
                    tmp.child[tmp.n] = nb.child[0];//借用兄弟節(jié)點(diǎn)
                    for (int i = 1 ; i < nb.n ; i++) {//重新挪位置
                        nb.key[i-1] = nb.key[i];
                    }
                    for (int i = 1 ; i <= nb.n ; i++) {
                        nb.child[i-1] = nb.child[i];
                    }
                    nb.n--;
                    Remove(tmp,key);//刪除
                    return;
                } else if (pos != 0 && x.child[pos-1].n >= T){//左孩子不貧困,和上面類似
                    devider = x.key[pos-1];
                    nb = x.child[pos-1];
                    x.key[pos-1] = nb.key[nb.n-1];
                    Node child = nb.child[nb.n];
                    nb.n--;
                    for(int i = tmp.n ; i > 0 ; i--) {
                        tmp.key[i] = tmp.key[i-1];
                    }
                    tmp.key[0] = devider;
                    for(int i = tmp.n + 1 ; i > 0 ; i--) {
                        tmp.child[i] = tmp.child[i-1];
                    }
                    tmp.child[0] = child;
                    tmp.n++;
                    Remove(tmp,key);
                    return;
                } else {//都貧困 合并
                    Node lt = null;//左孩子
                    Node rt = null;//右孩子
                    boolean last = false;
                    if (pos != x.n) {
                        devider = x.key[pos];
                        lt = x.child[pos]; 
                        rt = x.child[pos+1];
                    } else {
                        devider = x.key[pos-1];
                        rt = x.child[pos];
                        lt = x.child[pos-1];
                        last = true;
                        pos--;
                    }
                    for (int i = pos; i < x.n-1  ; i++){
                        x.key[i] = x.key[i+1];
                    }

                    for(int i = pos+1 ; i < x.n ; i++) {
                        x.child[i] = x.child[i+1];
                    }
                    x.n--;
                    lt.key[lt.n++] = devider;
                    for (int i = 0, j = lt.n; i < rt.n+1 ; i++,j++) {
                        if (i < rt.n) {
                            lt.key[j] = rt.key[i];
                        }
                        lt.child[j] = rt.child[i];
                    }
                    lt.n += rt.n;
                    if (x.n == 0) {
                        if (x == root) {
                            root = x.child[0];
                        }
                        x = x.child[0];
                    }
                    Remove(lt,key);                 
                    return;
                }               
            }
        }
    }

    public void Task (int a, int b){
        Stack<Integer> st = new Stack<Integer>();
        FindKeys(a,b,root,st);
        while (st.isEmpty() == false) {
            this.Remove(root,st.pop());
        }
    }
    
    private void FindKeys (int a, int b, Node x, Stack<Integer> st){
        int i = 0;
        for (i = 0 ; i < x.n && x.key[i] < b; i++) {
            if ( x.key[i] > a  ) {
                st.push(x.key[i]);
            }
        }
        if (!x.leaf) {
            for (int j = 0 ; j < i+1 ; j++) {
                FindKeys(a,b,x.child[j],st);
            }
        }
    }
    
    public boolean Contain(int k) {
        if (this.Search(root, k) != null) {
            return true;
        } else {
            return false;
        }
    }
    
    public static void main(String[] args) {
        BTree t=new BTree(3);
        t.Insert(3);
        t.Insert(14);
        t.Insert(7);
        t.Insert(1);
        t.Insert(8);
        t.Insert(5);
        t.Insert(11);
        t.Insert(17);
        t.Insert(13);
        t.Insert(6);
        t.Insert(23);
        t.Insert(12);
        t.Insert(20);
        t.Insert(9);
        t.Insert(87);
        t.Insert(34);
        t.Show();
        System.out.println("-----");
        t.Remove(7);
        t.Remove(6);
        t.Remove(1);
        t.Remove(11);
        t.Show();
    }
    
}