java - 二分探索木のノードを削除する

Question

BST のテスト コードがあります。BST は作成されますが、ノードの削除が正しく機能しません。以下の削除コードが正しいかどうか、または削除メソッドの変更が非常に役立つかどうかを示唆する助けがあれば、非常に役立ちます。

public class BinarySearchTree {
  public BinarySearchTree() {
    super();
  }

  private class BinarySearchTreeNode{
    private int data;
    private BinarySearchTreeNode left;
    private BinarySearchTreeNode right;

    public BinarySearchTreeNode(){
    }

    public BinarySearchTreeNode(int data){
      this.data = data;
    }

    public void setData(int data) {
      this.data = data;
    }

    public int getData() {
      return data;
    }

    public void setLeft(BinarySearchTree.BinarySearchTreeNode left) {
      this.left = left;
    }

    public BinarySearchTree.BinarySearchTreeNode getLeft() {
      return left;
    }

    public void setRight(BinarySearchTree.BinarySearchTreeNode right) {
      this.right = right;
    }

    public BinarySearchTree.BinarySearchTreeNode getRight() {
      return right;
    }
  }

  public BinarySearchTreeNode insertRec(BinarySearchTreeNode root,int data){
    if(root == null){
      root = new BinarySearchTreeNode(); 
      root.setData(data);
      root.setLeft(null);
      root.setRight(null);
    }else{
        if(data < root.getData())
          root.setLeft(insertRec(root.getLeft(), data));
        else if(data > root.getData())
          root.setRight(insertRec(root.getRight(), data));
    }

    return root;
  }

  public void insertNonRec(BinarySearchTreeNode root,int data){
    if(root == null){
      root = new BinarySearchTreeNode(data); 
      root.setLeft(null);
      root.setRight(null);
    }else{
      if(data < root.getData()){
        if(root.getLeft() != null){
          insertNonRec(root.getLeft(),data);
        }else{
          root.setLeft(new BinarySearchTreeNode(data));
        }
      }else if(data > root.getData()){
        if(root.getRight() != null){
          insertNonRec(root.getRight(), data);
        }else{
          root.setRight(new BinarySearchTreeNode(data));
        }
      }
    }
  }

  public void delete(BinarySearchTreeNode root,int data){
    BinarySearchTreeNode temp;
    if(root == null){
      System.out.println("No elemets in BST.");
    }else if(data < root.getData()){
      delete(root.getLeft(),data);
    }else if(data > root.getData()){
      delete(root.getRight(),data);
    }else{
      if((root.getLeft() != null) && (root.getRight() != null)){
        // Replace with largest in left subtree 
        temp = findMax(root.getLeft());
        root.setData(temp.getData());
        delete(root.getLeft(),temp.getData());
      }else if(root.getLeft() != null || root.getRight() != null){
        // One child
        if(root.getLeft() == null){
          //root = root.getRight();
          root.setData(root.getRight().getData());
          root.setRight(null);
        }else if(root.getRight() == null){
          //root = root.getLeft();
          root.setData(root.getLeft().getData());
          root.setLeft(null);
        }
      }else{
        root = null;
      }
    }
  }

  public BinarySearchTreeNode findMax(BinarySearchTreeNode root){
    if(root == null)
      return null;

    while(root.getRight() != null)
      root = root.getLeft();

    return root;
  }

  public BinarySearchTreeNode findMin(BinarySearchTreeNode root){
    if(root == null)
      return null;

    while(root.getLeft() != null)
      root = root.getLeft();

    return root;
  }

  public void inOrderRec(BinarySearchTreeNode root){
    if(root != null){
      inOrderRec(root.getLeft());
      System.out.print(root.getData() + " ");
      inOrderRec(root.getRight());
    }
  }

  public static void main(String args[]){
    BinarySearchTree tree = new BinarySearchTree();
    BinarySearchTreeNode root = tree.insertRec(null, 10);

    tree.insertNonRec(root, 5);
    tree.insertNonRec(root, 20);
    tree.insertNonRec(root, 4);
    tree.insertNonRec(root, 8);
    tree.insertNonRec(root, 12);
    tree.insertNonRec(root, 30);
    tree.insertNonRec(root, 11);
    tree.insertNonRec(root, 13);

    System.out.println("InOrder Traversal :");
    tree.inOrderRec(root);

    tree.delete(root, 20);

    System.out.println("");
    System.out.println("InOrder Traversal :");
    tree.inOrderRec(root);
  }
}

出力:

InOrder Traversal :
4 5 8 10 11 12 13 20 30 

InOrder Traversal :
4 5 8 10 11 12 13 11 30