AVLツリーの挿入と削除---Java実現

AVLツリーの定義:バランス条件付きの二叉ルックアップツリーは、その左右のサブツリーの高さ差が1以下である.木の回転によってバランスを保つ.ここでは、高さ値を保存することにより、削除と挿入が可能です.

public class AvlTree<T extends Comparable super T>> {
    //     
    private AvlNode root;
    //    
    private static class AvlNode<T>{
        AvlNode left;//   
        AvlNode right;//   
        T data;//   
        int height;//  
        public AvlNode(T data){
            this(data,null,null);
        }
        public AvlNode(T d,AvlNode l,AvlNode r){
            left=l;
            right=r;
            data=d;
            height=0;
        }
    }

    public AvlTree(){
        clear();
    }

    private int height(AvlNode t){
        return t==null?-1:t.height;
    }

    public boolean isEmpty(){
        return root==null;
    }

    public void insert(T data){
        root=insert(root,data);
    }

    public int getHeight(){
        return height(root);
    }

    public void clear(){
        root=null;
    }

    public void remove(T data){
        root=remove(root,data);
    }

    public T findMin(){
        return findMin(root).data;
    }

    public void printTree(){
        printTree(root);
    }

    private void printTree(AvlNode t){
        if(t==null)
            return;
        printTree(t.left);
        System.out.println(t.data);
        printTree(t.right);
    }

    private AvlNode findMin(AvlNode t){
        if(isEmpty()){
            return null;
        }
        if(t.left==null)
            return t;
        else
            return findMin(t.left);
    }

    //    
    private AvlNode doubleWithRightChild(AvlNode k3) {
        k3.right=rotateWithLeftChild(k3.right);
        return rotateWithRightChild(k3);
    }

    //    
    private AvlNode rotateWithRightChild(AvlNode k2) {
        AvlNode k1 = k2.right;
        k2.right=k1.left;
        k1.left=k2;
        k2.height=Math.max(height(k2.left), height(k2.right))+1;
        k1.height=Math.max(height(k1.left), height(k1.right))+1;
        return k1;
    }

    //             
    private AvlNode doubleWithLeftChild(AvlNode k3) {
        k3.left=rotateWithRightChild(k3.left);
        return rotateWithLeftChild(k3);
    }

    //    
    private AvlNode rotateWithLeftChild(AvlNode k2) {
        AvlNode 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), height(k1.right))+1;
        return k1;
    }

挿入

private AvlNode insert(AvlNode t, T data) {
        if(t==null){
            return new AvlNode(data);
        }
        int comparaResult =data.compareTo(t.data);
        if(comparaResult<0){
            t.left=insert(t.left,data);
            if(height(t.left)-height(t.right)==2){//     
                if(data.compareTo(t.left.data)<0){
                    t=rotateWithLeftChild(t);
                }else{
                    t=doubleWithLeftChild(t);
                }
            }
        }
        else if(comparaResult>0){
            t.right=insert(t.right,data);
            if(height(t.right)-height(t.left)==2){
                if(data.compareTo(t.right.data)>0){
                    t=rotateWithRightChild(t);
                }else{
                    t=doubleWithRightChild(t);
                }
            }
            }
        else
            ;//    ，    。
        t.height=Math.max(height(t.left), height(t.right))+1;
        return t;
    }

2.削除:削除が非常に頻繁ではないなら、不活性な削除が一番いいです.本稿ではこのような戦略を採用していない.

private AvlNode remove(AvlNode t,T data){
        if(t==null)
            return t;//    
        int compareResult = data.compareTo(t.data);
        if(compareResult<0){//   
            t.left=remove(t.left,data);

            //             ，   ，                   
            if (height(t.right) - height(t.left) == 2) {
                //     ，   
                if (height(t.right.right)>=height(t.right.left)) {
                    t = rotateWithRightChild(t);
                } else {//     ，   
                    t = doubleWithRightChild(t);
                }

            }
        }else if(compareResult>0){//   
            t.right=remove(t.right,data);
            if (height(t.left) - height(t.right) == 2  ) {
                if(t.left!=null){
                if (height(t.left.left)>=height(t.left.right)) {
                    t = rotateWithLeftChild(t);
                } else {
                    t = doubleWithLeftChild(t);
                }
                }
            }
        //         ，           
        }else if(t.left!=null&&t.right!=null){
        //    ，                         
            boolean iooo=(t.right==findMin(t.right)&&t.right.right==null);//    
            t.data=findMin(t.right).data;//              
            t.right=remove(t.right,t.data);//          
            if(iooo){//      ，       ，    
                t=rotateWithLeftChild(t);
            }
        }else{//         ，        
            t=t.left!=null?t.left:t.right;
        }
        if (t != null) {//    
        t.height = Math.max(height(t.left), height(t.right)) + 1;
        }
        return t;
    }