Построй дерево(5)

28
Недоступна

Добавлять в дерево элементы мы можем, теперь займись удалением: необходимо реализовать метод remove(Object o), который будет удалять элемент дерева имя которого было полученного в качестве параметра.

Вы не можете решать эту задачу, т.к. не залогинены.

Комментарии (242)

популярные
новые
старые

Для того, чтобы оставить комментарий Вы должны авторизоваться

Олег Пономарев

Уровень 33

18 февраля, 18:46

Решал последнюю подзадачу 2 вечера, уже было отчаялся и хотел искать подсказки в обсуждении, но выпил сладкого чаю, успокоился, привел мысли в порядок ... в итоге решил с первой попытки! У меня такой вариант удаления элемента, возможно кому то поможет разобраться: 1. Рекурсивно обхожу удаляемую ветку, начиная с заданного элемента и каждому элементу записываю в значение имени null. Сами элементы пока не удаляю, иначе не получится их все обойти. Как реализовать рекурсивный обход подсмотрел здесь: https://habr.com/ru/post/144850/ 2. С помощью listIterator перебираю элементы всего дерева и удаляю те, у которых имя == null. А еще ide подсказала как сделать это в одну строку:

tree.removeIf(current -> current.elementName == null);

3. Дополнил метод add: если не находится ни один узел с возможностью добавить child, то в цикле ищу первый элемент с максимальным значением linе (принадлежность узла строке в иерархии элементов) и ему разрешаю добавлять child, затем повторно вызываю метод add. Удачи, все получится!

LE_Anonymous #3029647

Уровень 37

6 февраля, 10:23

The list size is 15 The expected parent is 3. The actual parent is 3 The expected parent is null. The actual parent is null The expected parent is null. The actual parent is null The expected parent is 9. The actual parent is 1 (!!!!!!!) и все прошло на ура!! странно Всего эту задачу решили 4843 учеников. Expected: true. Actual: true The expected parent is 1. The actual parent is 1

Александр Сергеев

Уровень 37

6 января, 18:42

3 дня, 150 строк, одна попытка и прединсультное состояние.

Fermi Arch

Уровень 24

26 ноября 2022, 10:50

запускаю в idea все тест совпадают запускаю в webide результаты отличаются как так? 20 как и положено стал левым для 1го даже первый пункт почему не не засчитывает, хотя у меня все точно удаляется второй пункт тоже совпадает по задаче последний тоже //update результаты совпадают теперь, но тест не проходит...

The list size is 15
The expected parent is 3. The actual parent is 3
The expected parent is null. The actual parent is null
After delete "15" The list size is 14
After delete "3" The list size is 11
The expected parent is null. The actual parent is null
The expected parent is 9. The actual parent is 9
Expected: true. Actual: true
The expected parent is 1. The actual parent is 1

Юрий Митрясов

Уровень 41

9 ноября 2022, 18:08

Очередь для хранения "потомков" не делал как в некоторых комментариях. Метод remove реализовал через промежуточный рекурсивный метод removeChild, в котором проходился слева направо по всем потомкам.

void removeChild (Entry<String> current) {

        if (current.leftChild != null) {
            removeChild(current.leftChild);
        }
        if (current.rightChild != null) {
            removeChild(current.rightChild);
        }
        current.leftChild = null;
        current.rightChild = null;
        Entry<String> currentParent = current.parent;
        if (current == currentParent.leftChild) current.parent.leftChild = null;
        if (current == currentParent.rightChild) current.parent.rightChild = null;
        list.remove(current);
        size--;
    }

Логику метода add менял незначительно: 1. Создаем флаг, который проверяет isAvailableToAddChildren() для всех элементов из list; 2. Если данный флаг==false, то для всех потомков "нижнего" уровня переводим переменные availableToAddLeftChildren, availableToAddRightChildren в true. 3. Еще раз пробегаемся по списку и добавляем новый элемент

Bandiu Band

Уровень 40

27 октября 2022, 03:16

Вирішив за 3 години (мені повезло). В лоб, створив список List<Entry<String>> в якому зберігав посилання на всі елементи (в порядку додавання), написав свій метод видалення з цього списку (рідний не працює, ми самі його "відключили", і я просто створював копію без цілевого елементу), при видаленні елементу з основного списку, в його батька(мати🙃) повертаю здатність мати дитину з "правильної" сторони, через рекурсію викликаю видалення всіх його дітей. Читаючи коментарі були думки що, надовго застряв, але очі бояться руки роблять. Р.S з моїм кодом говорити про оптимізацію не можна, але мені лінь після схвальної відповіді Валі, городити велосипед.

Zakhar Kuropiatnyk

Уровень 41

3 октября 2022, 23:25

Заставили попотеть(когда увидел готовое решение - вспотел еще больше) в предыдущей задаче решил добавлением индекса к Энтри (индекс нового родителя всегда равен size/2) и думал, что на все окей, но эта часть с удалением.... игра в кошки мышки - наворотил такого показать страшно, но оказалось что ничего есть решения пострашнее - короткий план решения может поможет: в нашем дереве создал две переменные int - текущий индекс, и новый индекс, и простой List<Integer> - удаленные индексы 1 - добавление: - если лист заполняется новыми данными и ничего не удалялось - размер будет равен текущему индексу, индекс родителя = текущий индекс / 2, - если удалялось - проверяем есть ли родитель(текущий индекс/2) в списке удаленных индексов, если есть то +1 и проверяем еще раз(рекурсия в помощь) - добавляем элемент - присваиваем новый индекс(текущий +1) после добавления текущий индекс++, новый++, размер++ 2. Удаление: - находим жертву - запоминаем размер списка с удаленными индексами - проходим по всему родовому дереву жертвы удаляя от самого последнего отпрыска занося индекс каждого в списочек, - считаем насколько увеличился список удаленных индексов - на эту разницу уменьшаем наш общий размер списка. ps: не забываем про проверки на null - и не забываем, что стереть значит стереть все ссылки на элемент и не забываем добавить медот типа "перезагрузки" чтоб если при добавлении некуда добавить (все дети удаленны) очищало список удаленных индексов и ставило текущий индекс = текущий размер - а следующий размер +1

Kidchai

Уровень 35

1 сентября 2022, 22:44

в котором задании уже молюсь на рекурсию, как здорово, что она есть

An N

Уровень 34

23 августа 2022, 06:39

Кто-нибудь считал количество строк в правильном решении, если убрать все комментарии? У меня 173 строки, из которых 10 строк комментариев и пустые строки между методами.

An N

Уровень 34

23 августа 2022, 08:14

В правильном решении 23.08.2022 содержится 205 закомментированных строк 70 пустых незакомментированных строк 518 непустых строк с кодом Всего 793

Вадим

Уровень 40

31 августа 2022, 19:28

Справедливости ради стоит отметить, что они переопределили все методы из коллекций, так, что класс стал полноценно рабочим. А у нас только пару штук. Правда, не совсем понятно, где его можно применить :)

RomanGV

Уровень 26

13 августа 2022, 11:50

Javarush и многие пользователи в комментах: вот у нас коллекция для хранения элементов дерева ArrayList<Entry<String>>... Я сохранил всё в private Entry<String> root; без коллекций: А чё, так мооожно было что-ли? 😀😀😀 Задачу решал долго, примерно 6-7 часов суммарно за два дня. Зато хорошо прокачал скилл по алгоритмам обхода дерева. Задаче плюс! 👍 В моём решении используется горизонтальный обход дерева с помощью очереди (поиск и добавление), и вертикальный концевой обход с помощью стека (чтобы концевым элементам восстановить возможность иметь потомков) Очень помогли две статьи с хабра, ну и гугло-яндекс конечно. Обход бинарных деревьев: рекурсия, итерации и указатель на родителя Структуры данных: бинарные деревья. Часть 1 Кстати, в первой статье есть ошибка в алгоритме горизонтального обхода: последний элемент в нём не будет обработан. Внимание спойлер! Это мой вариант решения, который проходит валидатор. Открывать только если решили сами, или в полном тупике. Если админы удалят - ну окей. Правила... Warning! Spoiler! Ready solution. тут PS Не совсем понятен практический смысл именно такого дерева. Поиск долгий. Добавление тоже не самое быстрое...