java - 如何在 BST 中实现删除代码？

Question

我有一段关于二叉搜索树的代码，我想要计算插入、删除和查找 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 );
        }
    }

Answer 1

我认为本质上在交换方法中，您正在交换数据。如果是这样，那么下面的代码将执行此操作。

void swap(节点 a, 节点 b) { if(a!= null && b!= null) { int 数据 = a.data; a.数据=b.数据； b.数据=数据； } }

插入的复杂度是 O(h)，其中 h 是树的高度。 在最好的情况下(树是平衡的)它是 O(log N)，其中 N 是节点数。 在最坏的情况下(树不平衡，BST 就是这种情况)，它的复杂度为 O(N)，其中 N 是节点数。

此逻辑适用于最大值和最小值。

首先找到包含给定数据的节点。例如， 节点 n = find(数据); 然后调用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

        } 
    }