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

  • 28
  • Недоступна
Добавлять в дерево элементы мы можем, теперь займись удалением: необходимо реализовать метод remove(Object o), который будет удалять элемент дерева имя которого было полученного в качестве параметра.
Вы не можете решать эту задачу, т.к. не залогинены.
Комментарии (239)
  • популярные
  • новые
  • старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
Fermi Arch
Уровень 23
26 ноября, 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
Юрий Митрясов
Уровень 36
9 ноября, 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 октября, 03:16
Вирішив за 3 години (мені повезло). В лоб, створив список List<Entry<String>> в якому зберігав посилання на всі елементи (в порядку додавання), написав свій метод видалення з цього списку (рідний не працює, ми самі його "відключили", і я просто створював копію без цілевого елементу), при видаленні елементу з основного списку, в його батька(мати🙃) повертаю здатність мати дитину з "правильної" сторони, через рекурсію викликаю видалення всіх його дітей. Читаючи коментарі були думки що, надовго застряв, але очі бояться руки роблять. Р.S з моїм кодом говорити про оптимізацію не можна, але мені лінь після схвальної відповіді Валі, городити велосипед.
Zakhar Kuropiatnyk
Уровень 37
3 октября, 23:25
Заставили попотеть(когда увидел готовое решение - вспотел еще больше) в предыдущей задаче решил добавлением индекса к Энтри (индекс нового родителя всегда равен size/2) и думал, что на все окей, но эта часть с удалением.... игра в кошки мышки - наворотил такого показать страшно, но оказалось что ничего есть решения пострашнее - короткий план решения может поможет: в нашем дереве создал две переменные int - текущий индекс, и новый индекс, и простой List<Integer> - удаленные индексы 1 - добавление: - если лист заполняется новыми данными и ничего не удалялось - размер будет равен текущему индексу, индекс родителя = текущий индекс / 2, - если удалялось - проверяем есть ли родитель(текущий индекс/2) в списке удаленных индексов, если есть то +1 и проверяем еще раз(рекурсия в помощь) - добавляем элемент - присваиваем новый индекс(текущий +1) после добавления текущий индекс++, новый++, размер++ 2. Удаление: - находим жертву - запоминаем размер списка с удаленными индексами - проходим по всему родовому дереву жертвы удаляя от самого последнего отпрыска занося индекс каждого в списочек, - считаем насколько увеличился список удаленных индексов - на эту разницу уменьшаем наш общий размер списка. ps: не забываем про проверки на null - и не забываем, что стереть значит стереть все ссылки на элемент и не забываем добавить медот типа "перезагрузки" чтоб если при добавлении некуда добавить (все дети удаленны) очищало список удаленных индексов и ставило текущий индекс = текущий размер - а следующий размер +1
Kidchai
Уровень 35
1 сентября, 22:44
в котором задании уже молюсь на рекурсию, как здорово, что она есть
An N
Уровень 34
23 августа, 06:39
Кто-нибудь считал количество строк в правильном решении, если убрать все комментарии? У меня 173 строки, из которых 10 строк комментариев и пустые строки между методами.
An N
Уровень 34
23 августа, 08:14
В правильном решении 23.08.2022 содержится 205 закомментированных строк 70 пустых незакомментированных строк 518 непустых строк с кодом Всего 793
Вадим
Уровень 40
31 августа, 19:28
Справедливости ради стоит отметить, что они переопределили все методы из коллекций, так, что класс стал полноценно рабочим. А у нас только пару штук. Правда, не совсем понятно, где его можно применить :)
RomanGV
Уровень 26
13 августа, 11:50
Javarush и многие пользователи в комментах: вот у нас коллекция для хранения элементов дерева ArrayList<Entry<String>>... Я сохранил всё в private Entry<String> root; без коллекций: А чё, так мооожно было что-ли? 😀😀😀 Задачу решал долго, примерно 6-7 часов суммарно за два дня. Зато хорошо прокачал скилл по алгоритмам обхода дерева. Задаче плюс! 👍 В моём решении используется горизонтальный обход дерева с помощью очереди (поиск и добавление), и вертикальный концевой обход с помощью стека (чтобы концевым элементам восстановить возможность иметь потомков) Очень помогли две статьи с хабра, ну и гугло-яндекс конечно. Обход бинарных деревьев: рекурсия, итерации и указатель на родителя Структуры данных: бинарные деревья. Часть 1 Кстати, в первой статье есть ошибка в алгоритме горизонтального обхода: последний элемент в нём не будет обработан. Внимание спойлер! Это мой вариант решения, который проходит валидатор. Открывать только если решили сами, или в полном тупике. Если админы удалят - ну окей. Правила... Warning! Spoiler! Ready solution. тут PS Не совсем понятен практический смысл именно такого дерева. Поиск долгий. Добавление тоже не самое быстрое...
Олег
Уровень 35
7 августа, 09:57
В таком случае элементы "1" и "2" должны восстановить возможность иметь потомков (возможно придется внести изменения в метод add()). А потом на картинке видим, как новый элемент добавляется 9. Да, из комментариев становится понятно, что хочет джавараш, и становится понятно, для чего определять левый крайцний элемент и вводить счетчик уровней. Только теперь мне вобще все переделывать. А силушки уже нет. Моя прога работает в соответствии с условием. Я себе засчитываю.
Ян
Уровень 24
30 июля, 08:07
Решил за 1.5 часа примерно, но всё не безоблачно. Вначале вообще парализован был морально, не понимал как подступиться и как это сделать. Решил подглядывая в комментарии. Где-то сам допёр, но вот структуру общую в виде рекурсивной функции я всё же подглядел. Несколько плаваю как вот всё это работает в плане обхода при рекурсии.
Khaweez
Уровень 39
29 июля, 08:03
Объясните пожалуйста, я, кажется, не догоняю принципа бинарного дерева. Почему 16 добавляется не левым потомком к 1 на освободившееся место, а к 9? А к "старым" ветвям дерева новые потомки присоединяются только если не остается эл-тов isAvailableToAddChildren? Для чего такая логика добавления?
Evgeny Siganov QA Automation Engineer в Айтеко
29 ноября, 20:31
здесь то что мы написали это не то бирарное дерево, классическое) то которое мы написали я сам не понимаю как его применять, просто дерево в вакууме.