Как я могу реализовать удалить код в моем BST? - PullRequest
Новая
       14

Как я могу реализовать удалить код в моем BST?

0 голосов
/ 27 декабря 2011

У меня есть этот код о бинарном дереве поиска, я хочу Расчетную эффективность для вставки, удаления и поиска максимального и минимального значения в 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 ;-)");
    }
}

мой метод удаления, который я хочу вызвать в main 

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

1 Ответ

1 голос
/ 27 декабря 2011

Я думаю, что по существу в методе подкачки вы меняете данные.Если это так, то следующий код сделает это.

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) это O (N), где N - количество узлов.

эта логика применима к максимальным и минимальным значениям.

Сначала найдите узел, который содержит данные.Например, Node 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

        } 
    }
...