Ошибка метода удаления двоичного дерева поиска

Question

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

У меня уже есть методы поиска головы узла, getValue(), а также поиск левого и правого поддеревьев, getLeft() и getRight(). У меня также есть метод isEmpty(), который проверяет, пусто ли дерево.

Это мой код в настоящее время, где х узел должен быть удален и является бинарное дерево поиска:

public static Tree delete(int x, Tree a) { 
     if (a.isEmpty()) { 
      return new Tree(); 
     } if (x>a.getValue()) { 
      return delete(x, a.getRight()); 
     } else if (x<a.getValue()) { 
      return delete(x, a.getLeft()); 
     } else { 
      if (a.getLeft().isEmpty()&&a.getRight().isEmpty()) { 
       return new Tree(); 
      } if (a.getRight().isEmpty()) { 
       return delete(x, a.getLeft()); 
      } if (a.getLeft().isEmpty()) { 
       return delete(x, a.getRight()); 
      } else { 
       return new Tree(); //not yet completed 
      } 
     } 
    } 

Может кто-нибудь дать мне какие-либо подсказки относительно того, почему это будет происходить? Заранее спасибо

Edit: Вот код, который в конечном счете работал, если кто-то случается наткнуться этот вопрос

public static Tree delete(int x, Tree a) { 
     if (a.isEmpty()) { 
      return new Tree(); 
     } if (x>a.getValue()) { 
      return new Tree(a.getValue(), a.getLeft(), delete(x, a.getRight())); 
     } else if (x<a.getValue()) { 
      return new Tree(a.getValue(), delete(x, a.getLeft()), a.getRight()); 
     } else { 
      if (a.getLeft().isEmpty()&&a.getRight().isEmpty()) { 
       return new Tree(); 
      } if (a.getRight().isEmpty()) { 
       return new Tree(a.getLeft().getValue(), delete(a.getLeft().getValue(), a.getLeft()), a.getRight()); 
      } if (a.getLeft().isEmpty()) { 
       return new Tree(a.getRight().getValue(), a.getLeft(), delete(a.getRight().getValue(), a.getRight())); 
      } else { 
       return new Tree(max(a.getLeft()), delete(max(a.getLeft()), a.getLeft()), a.getRight()); 
      } 
     } 
    } 

Answer 1

Этот метод возвращает пустое дерево вместо установки влево или вправо, как пустой. Вот почему вы думаете, что он удаляет верхний узел. Также не похоже, что он обрабатывает удаление самого узла, только дочерние узлы.

Answer 2

Вы никогда ничего не удаляете. Есть два способа сделать это.

1. Создание structureal копии дерева, пока узел не будет удален, а затем взять одного из детей и вставить другие выбранный ребенок результата вставки является результатом дерева.

2. Поиск родительского узла узла, который должен быть удален, и изменить принадлежность к узлу как одного из дочерних элементов, а затем добавить другое дочернее поддерево в родительское дерево. В основном здесь у вас есть древовидный класс, который обрабатывает вставку и имеет корень. Удаление корня - это особый случай с повторным связыванием вместо изменения узла.

Если вы делаете алгоритм поиска с возвратом, когда возвращаясь к предыдущему дереву необходимо # 1 является единственным выбором, и он будет делиться столько структурой с предыдущей версией дерева. Если вы хотите повторить и обновить структуру данных, чтобы отразить что-то, где вам никогда не понадобится eprevious state # 2, это лучший выбор.