Как написать код для удаления двоичного дерева поиска?

Question

Я написал следующий псевдокод для метода RemoveNode() при работе с BST-х:

If left is null 
Replace n with n.right 
Else if n.right is null 
Replace n with n.left 
Else 
Find Predecessor of n 
Copy data from predecessor to n 
Recursively delete predecessor* 

Я не только хочу этот метод, чтобы удалить или удалить узлы, но я также хочу, чтобы вернуть истину, если удаление успешный.

Это то, что я написал до сих пор, и мне было интересно, есть ли у кого-нибудь отзывы, предложенные изменения или советы, которые помогут мне завершить этот метод. Я также приложу всю свою программу ниже этого метода.

private void removeNode(Node<E> n) { 
     if (n.left == null) { 
     replace(n, n.right); 
     } else if (n.right == null) { 
     replace(n, n.left); 
     } else { 
     //How do I find pred of n 
     //Copy data from pred to n 
     //Recursively delete pred 
     } 

    } 

Вот остальная часть моего кода:

import java.util.Random; 

public class BinarySearchTree<E extends Comparable<? super E>> extends BinaryTree<E> { 

    public boolean contains(E item) { 
     return findNode(item, root) != null; 
    } 

    private Node<E> findNode(E item, Node<E> n) { 
     if (n == null || item == null) return null; 
     int result = item.compareTo(n.data); 
     if (result == 0) { 
     return n; 
     } else if (result > 0) { 
     return findNode(item, n.right); 
     } else { 
     return findNode(item, n.left); 
     } 
    } 

    public E max() { 
     Node<E> m = maxNode(root); 
     return (m != null) ? m.data : null; 
    } 

    private Node<E> maxNode(Node<E> n) { 
     if (n == null) return null; 
     if (n.right == null) return n; 
     return maxNode(n.right); 
    } 

    public E min() { 
     Node<E> m = minNode(root); 
     return (m != null) ? m.data : null; 
    } 

    private Node<E> minNode(Node<E> n) { 
     if (n == null) return null; 
     if (n.left == null) return n; 
     return minNode(n.left); 
    } 

    public E pred(E item) { 
     Node<E> n = findNode(item, root); 
     if (n == null) return null; 
     Node<E> pred = predNode(n); 
     return (pred != null) ? pred.data : null; 
    } 

    private Node<E> predNode(Node<E> n) { 
     assert n != null; 
     if (n.left != null) return maxNode(n.left); 
     Node<E> p = n.parent; 
     while (p != null && p.left == n) { 
     n = p; 
     p = p.parent;   
     } 
     return p; 
    } 

    public E succ(E item) { 
     Node<E> n = findNode(item, root); 
     if (n == null) return null; 
     Node<E> succ = succNode(n); 
     return (succ != null) ? succ.data : null; 
    } 

    private Node<E> succNode(Node<E> n) { 
     assert n != null; 
     if (n.right != null) return minNode(n.right); 
     Node<E> p = n.parent; 
     while (p != null && p.right == n) { 
     n = p; 
     p = p.parent;   
     } 
     return p; 
    } 

    public void add(E item) { 
     if (item == null) return; 
     if (root == null) { 
     root = new Node<>(item, null); 
     } else { 
     addNode(item, root); 
     } 
    } 

    private void addNode(E item, Node<E> n) { 
     assert item != null && n != null; 
     int result = item.compareTo(n.data); 
     if (result < 0) { 
     if (n.left == null) { 
      n.left = new Node<>(item, n); 
     } else { 
      addNode(item, n.left); 
     } 
     } else if (result > 0) { 
     if (n.right == null) { 
      n.right = new Node<>(item, n); 
     } else { 
      addNode(item, n.right); 
     } 
     } else { 
     return; // do not add duplicates 
     } 
    } 


    public boolean remove(E item) { 
     Node<E> n = findNode(item, root); 
     if (n == null) return false; 
     removeNode(n); 
     return true; 
    } 

    private void removeNode(Node<E> n) { 
     if (n.left == null) { 
     replace(n, n.right); 
     } else if (n.right == null) { 
     replace(n, n.left); 
     } else { 
     //How do I find pred of n 
     //Copy data from pred to n 
     //Recursively delete pred 
     } 

    } 

    private void replace(Node<E> n, Node<E> child) { 
     assert n != null; 
     Node<E> parent = n.parent; 
     if (parent == null) { 
     root = child; 
     } else if (parent.left == n) { 
     parent.left = child; 
     } else { 
     parent.right = child; 
     } 
     if (child != null) child.parent = parent; 
    } 


    public String toString() { 
     return inorder(); 
    } 

Answer 1

Код для удаления элемента очень проста.

1. Поиск узла, который вы хотите удалить.
2. Проверьте, есть ли у узла дочерние элементы.
3. Корпус 1 - Остался только ребенок -> Заменить текущий узел левым ребенком.
4. Корпус 2 - имеет только правильный ребенок -> заменить текущий узел на правого ребенка.
5. Случай 3 - Имеет обоих детей -> Найти наименьший элемент в правом дочернем поддереве, заменить текущий узел на этот узел и затем удалить этот узел.

Кодекс может быть реализован рекурсивно следующим образом ->

BinarySearchTree.prototype.remove = function(data) { 
var that = this; 
var remove = function(node,data){ 
    if(node.data === data){ 
     if(!node.left && !node.right){ 
      return null; 
     } 
     if(!node.left){ 
      return node.right; 
     } 
     if(!node.right){ 
      return node.left; 
     } 
     //2 children 
     var temp = that.findMin(node.right); 
     node.data = temp; 
     node.right = remove(node.right,temp); 

    }else if(data < node.data){ 
     node.left = remove(node.left,data); 
     return node; 
    }else{ 
     node.right = remove(node.right,data); 
     return node; 
    } 
    }; 
this.root = remove(this.root,data); 
};