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

Question

Я выполняю задание, реализуя собственное двоичное дерево поиска. Дело в том, что у нас есть собственная реализация узла, его родительский доступ напрямую не доступен.

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

Можете ли вы, пожалуйста, помочь, что я делаю неправильно?

Это метод удалить:

void remove(E elem) { 
    if(elem != null){ 
     if (root != null && contains(elem)) { 
      removeFromSubtree(elem, root, null); 
     } 
    } 
} 

void removeFromSubtree(E elem, Node<E> current, Node<E> parent) { 

    if(elem.less(current.contents)){ 
     if(current.left == null) return ; 
     removeFromSubtree(elem, current.left, current); 
    } else if(elem.greater(current.contents)){ 
     if(current.right == null)return; 
     removeFromSubtree(elem, current.right, current); 
    } else { 
     if(current.left != null && current.right != null){ 
      //both children 
      if(parent == null){ 
       Node<E> n = new Node<>(null, null); 
       n.left = root; 
       removeFromSubtree(root.contents, n, null); 
       root = n.left; 
       root.setParent(null); 
      } 
      E min = subtreeMin(current.right); 
      current.contents = min; 
      removeFromSubtree(min, current.right, current); 
     } else if(current.left != null){ 
      //left child 
      if (parent == null) { 
        root = current.left; 
        current.left.setParent(null); 
        return ; 
       } 
      setParentChild(current, parent, current.left); 
     } else if(current.right != null){ 
      //right child 
      if (parent == null) { 
       root = current.right; 
       current.right.setParent(null); 
       return ; 
      } 
      setParentChild(current, parent, current.right); 
     } else { 
      if (parent == null) { 
       root = null; 
       return ; 
      } 
      setParentChild(current, parent, null); 
     } 
    } 
} 

узлы используют общий интерфейс

class Node<E extends DSAComparable<E>> 

, который имеет только методы Comparation. Похоже, что этот

interface DSAComparable<E extends DSAComparable<E>> { 
    boolean less(E other); 
    boolean greater(E other); 
    boolean equal(E other); 
} 

Я использую другой methon внутри Вытащите, который устанавливает ребенок родительского узла, в зависимости, если его левый ребенок или право ребенка.

void setParentChild(Node<E> node, Node<E> parent,Node<E> value){ 
    if(parent!= null){ 
     if (parent.left == node) { 
      parent.left = value; 
     } else { 
      parent.right = value; 
     } 
     if(value!= null) value.setParent(parent); 
    } 
} 

Метод subtreeMin (Node узел) находит наименьшее значение в поддереве (самый левый)

Answer 1

Понимание кода не так просто, так как она до сих пор не хватает деталей.

Я бы назвал такую ​​реализацию двоичного поиска , который вы можете найти в Интернете.

См. Например, номер Algorithms, 4th Ed..