データ構造-Java実装-ツリー

13163 ワード

データ構造の基礎

フォークルックアップツリー

AVLツリー

ツリーを巡る

…(続き)1、二叉のルックアップツリーが二叉のルックアップツリーになる性質は、ツリー内の各ノードXに対して、左のサブツリーのすべての項目の値はXの値より小さいが、その右のサブツリーのすべての項目の値はXの値より大きい.

//     
public class BinarySearchTree>
{
    //   
    private static class BinaryNode
    {
        BinaryNode(AnyType theElement)
        {this(theElement, null, null);}

        BinaryNode(AnyType theElement, BinaryNode lt, BinaryNode rt)
        {element=theElement; left=lt; right=rt;}

        AnyType element;  //    
        BinaryNode left;  //         
        BinaryNode right;  //         
    }

    //   
    private BinaryNode root;

    public BinarySearchTree()
      { root=null;}

    public void makeEmpty()
      { root=null;}
    public boolean isEmpty()
      { return root==null;}
    //contains  (    )
    private boolean contains(AnyType x,BinaryNode t)
    {
        //    ，         ，         false
        if(t==null)
            return false;

        int compareResult = x.compareTo(t.element);

        if(compareResult<0)
            return contains(x,t.left);  //     ，             
        else if(compareResult>0)
            return contains(x,t.right);  //     ，             
        else
            return true;  //    ，     ！
    }

    //findMin  (    )
    private BinaryNode findMin(BinaryNode t)
    {
        if(t==null)
            return null;
        eles if(t.left==null)
            return t;
        return findMin(t.left);
    }

    //findMax  (     ，    )
    private BinaryNode findMax(BinaryNode t)
    {
        if(t!=null)
            while(t.right!=null)
                t=t.right;

        return t;

    }

    //insert  
    private BinaryNode insert(AnyType x, BinaryNode t)
    {
        if(t==null)
            return new BinaryNode(x,null,null);

        int compareResult=x.compareTo(t.element);
        //    ，    t.left t.right           
        if(compareResult<0)
            t.left=insert(x,t.left);  
        else if(compareResult>0)
            t.right=insert(x,t.right);
        else
            ;  //       
        return t;  //t       
    }
    //remove  
    private BinaryNode remove(AnyType x, BinaryNode t)
    {
        if(t==null)
            return t;

        int compareResult = x.compareTo(t.element);
        //     
        if(compareResult<0)
            t.left=remove(x,t.left);
        else if(compareResult>0)
            t.right =remove(x,t.right);
        //               
        //           
        else(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 t;
    }   
}

2、AVLツリー
一つのAVLツリーは、各ノードの左サブツリーと右サブツリーの高さの最大差1の二叉ルックアップツリー(空のツリーの高さは−1と定義されている)である.

//AVL 
//   
private static class AvlNode
{
    AvlNode(AnyType theElement)
    {this(theElement,null,null);}

    AvlNode(AnyType theElement, AvlNode lt,AvlNode rt)
    {element=theElement;left=lt;right=rt;}

    AnyType element;
    AvlNode left;
    AvlNode right;
    int height;  //    
}
//         
private int height(AvlNode t)
{
    return t==null?-1:t.height;
}

private AvlNode insert(AnyType x, AvlNode t)
{
    if(t==null)
        return new AvlNode(x, null, null);

    int compareResult=compare(x,t.element);  //compare            Comparator    

    if(compareResult<0)  //          
    {
        t.left=insert(x,t.left);  //                   
        if(height(t.left)-height(r.right)==2)  //==2      
            if(compare(x,t.left.element)<0)  //x         ，     ，     
                t=rotateWhithLeftChild(t);
            else  //      ，     
                t=doubleWithLeftChild(t);
    }
    else if(compareResult>0)  //          
    {
        t.right=insert(x,t.right);  //                   
        if(height(t.right)-height(t.left)==2)  //==2     
            if(compare(x,t.right.element)>0)  //x         ，     ，     
                t=rotateWhithRightChild(t);
            else
                t=doubleWithRightChild(t);              
    }
    else
        ;  //       
    t.height=Math.max(height(t.left),height(t.right))+1;  //          
    return t;
}
//     
private AvlNode rotateWhithLeftChild(AvlNode k2)
{
    AvlNode k1=k2.left;  //k2    
    k2.left=k1.right;  //  k2  k1     ，k1            k2     
    k1.right=k2;  //k1  ，k2  k1     
    k2.height=Math.max(height(k2.left),height(k2,right))+1;
    k1.height=Math.max(height(k1.left),k2.height)+1;
    return k1;
}
//     
private AvlNode doubleWithLeftChild(AvlNode k3)
{
    k3.left=rotateWhithRightChild(k3.left); //         
    return rotateWhithLeftChild(k3);  //         
}
//

3、木の遍歴

//    
//     
public printTree()
{
    if(isEmpty())
        System.out.println("Empty tree");
    else
        printTree(root);
}

private void printTree(BinaryNode t)
{
    if(t!=null)
    {
        printTree(t.left);
        System.out.println(t.element);
        printTree(t.right);
    }
}
//    
//       
private int height(Binary t)
{
    if(t==null)
        return -1;
    else
        return 1+Math.max(height(t.left),height(t.right));
}
//    
//

jBPM 4.4:Execution Serviceサービス