How I can implement delete code in my BST?

Question

I have this code about binary search tree , I want Calculated efficancy for insert , delete and find max and min value in BST

I make it for insert like that

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

I have this delete code and want modify it be suitable for my insert code but I can not get out put

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

my delete method that I want call it in 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 );
        }
    }

Answer 1

I think essentially in the swap method, you are swapping the data. If so, then the following code will do it.

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

The complexity for insertion is, O(h) where h is the hight of the tree. In the best case (where the tree is balanced) it is O(log N) where N is the number of nodes. In the worst case (where the tree is NOT balanced, which is the case in BST) it is O(N) where N is the number of nodes.

this logic is applicable to max and min.

First find the node that contains the given data. For example, Node n = find(data); then call 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

        } 
    }