3

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

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);
    }
3
  • 1
    Node.remove в таком виде бесполезен. Допустим, у вас есть только корневая вершина со значением 5, вы вызываете корень.remove(5), метод вызывает delete(this, 5), который честно возвращает null (корень.l), который никак не используется. Можно завести класс Tree, у которого будет поле root, и метод remove(int x) { root = delete(root, x); }.
    – zRrr
    13 апр 2016 в 18:45
  • remove работает, когда беру не корень, когда беру корень, дебагер все норм показывает, но в самом ответе получаю ту же ссылку
    – Youlfey
    13 апр 2016 в 18:53
  • @Артем, если вопрос для вас больше не актуален, то выберите ответ, который по вашему мнению был наиболее исчерпывающим (галочка слева от ответа) и тогда вопрос можно будет считать закрытым.Если вы не нашли среди ответов нужный, предложите свой вариант ответа, который раскрывал бы суть вашего вопроса.
    – diofloyk
    14 апр 2016 в 12:43

2 ответа 2

3

В книге "Алгоритмы построение и анализ" Томас Кормен. Разобран алгоритм удаления узла из бинарного дерева поиска.

Процедура удаления разделена на две подпрограммы, являющиеся псевдокодом. Первая: введите сюда описание изображения

И вторая:

введите сюда описание изображения

Где T- ссылка на ваше дерево, z- ссылка на узел который нужно удалить. Полагаю, зная этот алгоритм, для вас не составит труда написать его реализацию.

1

Нужно строку

n.r = delete(n.r, n.r.x);

заменить на

n.r = delete(n.r, n.x);

т.к. иначе вы удаляете не искомое, а ноду справа

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.