0

二分探索木に関するこのコードがあります。挿入、削除、およびBSTの最大値と最小値の計算効率が必要です

そんな挿入用に作ってます

public static void main(String args[]) {
    BinarySearchTree bst = new BinarySearchTree();
    Random random = new Random(System.currentTimeMillis());
    int[] randoms = new int[1000];

    Random randGen = new Random();
    long start = System.currentTimeMillis();
    for (int i = 0; i < randoms.length; i++) {
        bst.insert(random.nextInt(10));
    }

    System.out.println("\n sorted :");
    random.nextInt(10);
    bst.inorderTraversal();
    long end = System.currentTimeMillis();
    System.out.println("\n Running Time for insert ");

    System.out.println(end - start);
}

この削除コードがあり、挿入コードに適したものに変更したいのですが、出力できません

public static void main(String[] args){
        pBSTRemoveNode tree = null;
        int[] numbers = {56,86,71,97,82,99,65,36,16,10,28,52,46};
        System.out.print("inserting: ");
        for(int i = 0;i<numbers.length;i++){
            Integer n = new Integer(numbers[i]);
            System.out.print(" "+n);
            tree = tree_AddNumber(tree,n);
        }
        System.out.print("\ntree: ");
        tree_InOrderPrint(tree);
        for(int j = 0;j < numbers.length;j++){
            Integer n = new Integer(numbers[j]);
            System.out.print("\nremove: "+n+" tree: ");
            tree = tree_removeNumber(tree,n);
            tree_InOrderPrint(tree);
        }
        System.out.println("\ndone ;-)");
    }
}

メインで呼び出したい削除メソッド

public void delete( Node node, int data ) {
        if( node == null ) {
            return;
        }

        else if ( data == node.data) {

            if( node.left == null ) {
                swap( node, node.right ); 
            } 

            else if( node.right == null ) {
                swap( node, node.left );
            } 

            else {
                Node minNode = node.right;

                while( minNode.left != null ) {
                    minNode = minNode.left;
                }

                if( minNode.parent != node ) {
                    swap( minNode, minNode.right );
                    minNode.right = node.right;
                    minNode.right.parent = minNode;
                }

                swap( node, minNode );
                minNode.left = node.left;
                minNode.left.parent = minNode;
            }  
        } 
        // Continue searching in the left subtree.
        else if( data < node.data) {
            delete( node.left, data );
        } 
        // Continue searching in the right subtree.
        else {
            delete( node.right, data );
        }
    }
4

1 に答える 1

1

基本的に swap メソッドでは、データを交換していると思います。もしそうなら、次のコードはそれを行います。

void swap(Node a, Node b) { if(a != null && b != null) { int data = a.data; a.data = b.data; b.data = data; } }

挿入の複雑さは O(h) で、h はツリーの高さです。最良の場合 (ツリーのバランスがとれている場合) は、O(log N) で、N はノードの数です。最悪の場合 (BST の場合のように、ツリーのバランスが取れていない場合)、N はノードの数である O(N) です。

このロジックは max と min に適用されます。

最初に、指定されたデータを含むノードを見つけます。たとえば、ノード n = find(data); 次に、delete(n) を呼び出します。

public void delete( Node node) {
         if( node == null ) {
            return;
         }
         if( node.left == null ) {
                swap( node, node.right );
                node.right=null;
         } 
         else if( node.right == null ) {
                swap( node, node.left );
                node.left=null;
         } 
         else {
             Node minNode = node.right;
             while( minNode.left != null ) {
                  minNode = minNode.left;
             }
             swap( node, minNode );
             delete(minNode); // call recursively until you find a node whose left or right is null

        } 
    }
于 2011-12-27T02:02:38.573 に答える