Пытался реализовать метод удаления вершины из бинарного дерева. Проблема в том, что когда я хочу удалить корень дерева он не удаляется, подскажите где ошибка.
private static Node delete(Node n, int x) {
if(n == null) return n;
if (x > n.x) n.r = delete(n.r, x);
else if (x < n.x) n.l = delete(n.l, x);
else if (n.r != null && n.l != null) {
n.x = n.r.minimum().x;
n.r = delete(n.r, n.r.x);
}
else {
if (n.r != null) n = n.r;
else n = n.l;
}
return n;
}
public void remove(int x){
delete(this, x);
}
Ответ
В книге "Алгоритмы построение и анализ" Томас Кормен.
Разобран алгоритм удаления узла из бинарного дерева поиска.
Процедура удаления разделена на две подпрограммы, являющиеся псевдокодом.
Первая:
И вторая:
Где T- ссылка на ваше дерево, z- ссылка на узел который нужно удалить.
Полагаю, зная этот алгоритм, для вас не составит труда написать его реализацию.
Комментариев нет:
Отправить комментарий