BSTで削除コードを実装する方法は？

Question

私は、挿入のために計算efficancyをしたい、バイナリ検索ツリーについては、このコードを持って、私はその

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

のような挿入のためにそれを作るBST

で最大値と最小値を削除し、見つける私は、この削除のコードを持っていますそして、したい、それは私の挿入コードに適して修正するが、私は出ることができない私は、メイン

でそれを呼び出したい

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

私のdeleteメソッドを置きます210

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(Node a, Node b) { if(a != null && b != null) { int data = a.data; a.data = b.data; b.data = data; } }

挿入のための複雑さは、hは木の絶頂であるO（H）です。 最良の場合（ツリーが均衡している場合）はO（log N）です（Nはノードの数）。 最悪の場合（ツリーが均衡していない場合、BSTの場合）、O（N）です（Nはノードの数です）。

このロジックは、最大値と最小値を適用することができます。

まず、与えられたデータが含まれているノードを見つけます。たとえば、 ノード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 

     } 
    }