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

Question

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

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

Вот мой соответствующий код

private boolean hasChildren(Node x) {
    return (x.left != null || x.mid != null || x.right != null);
}

private void reHang(Node x) {
    if (hasChildren(x)) {
        if (x.left != null) {
            x.parent.mid = x.left;
            x.left.right = x.right;
        } else if (x.right != null) {
            x.parent.mid = x.right;
        }
    }
}

private boolean remove(Node x, String key, int d) {
  if (x == null) return false;
  char c = key.charAt(d);
  if (c < x.c) {
      if (!remove(x.left, key, d)) {
          x.left = null;
      }
  } else if (c > x.c) {
      if (!remove(x.right, key, d)) {
          x.right = null;
      }
  } else if (d < key.length() - 1) {
      if (!remove(x.mid, key, d + 1)) {
          x.mid = null;
          if (x.val != null) return true;
      }
  } else {
      x.val = null;
  }

  reHang(x);
  return hasChildren(x);
}

private class Node
{
    private Value val;
    private char c;
    private Node left, mid, right, parent;
}

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

private Node getMidPath(Node x) {
    if (x.left != null) return getMidPath(x.left);
    if (x.mid == null) return x;
    return getMidPath(x.mid);
}

Каждый узел, у которого нет x.mid, должен иметь набор x.val, что не всегда имеет место после удаления, то есть у меня есть грязные узлы.

Любая помощь будет принята с благодарностью.

Answer 1

Вы должны увидеть троичное дерево в том месте, где оно было: Некоторое вложенное двоичное дерево, но на каждом уровне в качестве ключа используется только символ, а не вся строка.Идите вниз по вашим двоичным деревьям, пока не истощится строка.Здесь у вас будет две в конечном итоге ссылки одна на фактические данные и одна две на фактическое поддерево для более длинной строки с одинаковым префиксом.Теперь установите данные на нуль.Если ссылка на поддерево пуста, удалите узел.Когда теперь все поддерево пусто, переходите к поддереву на один символ раньше.Здесь установите ссылку на поддерево на ноль.Теперь обе ссылки являются нулевыми удалить узел.Когда теперь все поддерево пусто, переходите к поддереву на один символ раньше.И так далее