Удаление узла в BST

Question

Я работаю над методом удаления узла из BST. В том же методе я рекурсивно ищу узел для удаления, а также сохранение родительского элемента этого узла. Однако единственная проблема заключается в том, что я не уверен, как сделать корневой узел равным родительскому узлу (поскольку удаление происходит в родительском узле) в case2.

public Node delete(Node root, int data) 
{ 

    // base case - if tree is empty 
    if (root == null) 
     return root; 

    // find the node to be deleted and keep track of parent 
    if (data < root.data) 
    { 
     parent = root; 
     System.out.println("parent node: " + parent.data); 
     root.left = delete(root.left, data); 
    } 
    else if (data > root.data) 
    { 
     parent = root; 
     System.out.println("parent node: " + parent.data); 
     root.right = delete(root.right, data); 


    // delete node 
    } 
    else 
    { 
     // case 1: deletion node has no subtrees 
     if (root.left == null && root.right == null) 
     { 
      System.out.println(data + " successfully deleted from tree (case1)"); 
      root = null; 
     } 

     // case 2: deletion node has only one subtree 
     else if (root.left != null && root.right == null) 
     { 
      Node temp = root.left; 
      if(parent.left.data == root.left.data) 
      { 
       parent.left = null; 
       System.out.println(data + " successfully deleted from tree (case2)"); 
       parent.left = temp; 
       root = parent; // parent was sent when searching for the node 

      } 
      else if(parent.right.data == root.data) 
      { 
       parent.right = null; 
       System.out.println(data + " successfully deleted from tree (case2)"); 
       parent.left = temp; 
       root = parent; // parent was sent when searching for the node 
      } 

     } 
     else if (root.left == null && root.right != null) 
     { 
      // same logic 
     } 
    } 

    return root; 

} 

Answer 1

Вы должны добавить еще одну функцию для вызова функции удаления для этого

class BST{ 
     private Node root=null; 

     private Node parent=null;// just for use by the deletion function 
     public void delete(int data){ 
      Node dummy_node=new Node(0);//can be initialized to anything. 
      dummy_node.setLeft(root); //right is null; 
      parent=dummy_node; 
      root=your_delete(this.root,data); 
      dymmy_node=null; 
     } 
     public Node your_delete(Node root, int data) { 
      //your code here 
     } 
    } 

Это будет работать, но Автошоу в лучший способ сделать удаление. здесь: http://www.algolist.net/Data_structures/Binary_search_tree/Removal