Удалить узел в двоичном дереве поиска

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 

Answer 1

root = null; не делать то, что вы думаете, что он делает. Он изменяет только значение локальной переменной. Он не меняет дерево. Краткая метафора:

Подумайте о классе студентов. Студенты - это узлы в дереве. Они указывают друг на друга, что определяет родительское дерево в дереве. Теперь, если другой студент (скажем, Джон, т. Е. Параметр функции) должен был прийти и указать на одного из учеников на «дереве» (скажем, Сара), говоря, что root = null; будет эквивалентен Джону, который теперь нигде не указывает, изменить Сару и то, что указывают другие ученики.

Уверены, что в моей метафоре есть некоторые дыры, но я надеюсь, что вы получите основную идею.

Вам нужно сделать что-то вроде node.setLeft(null); или node.setRight(null);, чтобы на самом деле сменить дерево.

Для этого потребуется немало изменений, которые я вам дачу, чтобы выяснить (this или this может оказать какую-то помощь), но обратите внимание, что для этого вам, очевидно, придется проверить левого и правого детей вместо (просто) корня.

Я также предлагаю вам взглянуть на Red-black trees (или аналогичный), поскольку они обеспечивают более эффективные способы удаления узлов, а также позволяют сбалансировать дерево.