バイナリ検索ツリーの削除のコードを書くには？

Question

BSTのと協力しながら、私はがremoveNode（）メソッドについては、以下の疑似コードを書かれている：

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* 

だけでなく、私はこの方法では、ノードを削除したり、削除したいが、私はまた、削除場合、それは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 
     } 

    } 

は、私のコードの残りの部分である：

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