Alvin Seville
335 / 267 / 132
Регистрация: 25.07.2014
Сообщений: 4,537
Записей в блоге: 9
1

Удаление узла из AVL-дерева

31.08.2018, 12:04. Показов 3114. Ответов 5
Метки нет (Все метки)

Почему можно так (стр 28) сделать
Остановить просмотр можно на том узле, в котором показатель баланса не поменялся.
?

Добавлено через 2 минуты
Как вообще может найтись такой предок, где баланс не изменится, если мы идем по пути поиска удаляемого узла вверх?
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
31.08.2018, 12:04
Ответы с готовыми решениями:

Физическое удаление из AVL-дерева
Можно ли при удалении сначала провести балансировку и пересчитать балансы, а потом произвести...

AVL-деревья - вычисление баланса узла
Баланс узла обычно вычисляется как разность высот левого и правого дерева или наоборот? ...

Удаление из AVL-дерева
Узел дерева: namespace AVL_Tree { /// <summary> /// Узел дерева. /// </summary> ...

Удаление узла дерева
Добрый вечер. У меня маленькая проблема - написал шаблон для работы с бинарным деревом поиска....

5
Модератор
2933 / 2077 / 445
Регистрация: 26.03.2015
Сообщений: 8,108
31.08.2018, 13:23 2
Цитата Сообщение от Соколиный глаз Посмотреть сообщение
Как вообще может найтись такой предок, где баланс не изменится, если мы идем по пути поиска удаляемого узла вверх?
Удаление узла в поддереве может не изменить высоту поддерева. Тогда показатель баланса в корне поддерева тоже не изменится.
(А вот наоборот бывает - высота поддерева не изменилась, а показатель баланса в корне поддерева изменился).
1
Alvin Seville
335 / 267 / 132
Регистрация: 25.07.2014
Сообщений: 4,537
Записей в блоге: 9
02.09.2018, 11:04  [ТС] 3
1) Как определить изменит ли высоту дерева удаление узла или нет, если есть только балансы в узлах дерева?
2)
А вот наоборот бывает - высота поддерева не изменилась, а показатель баланса в корне поддерева изменился.
Можно пример? Я не совсем понимаю когда это может произойти.
0
Модератор
2933 / 2077 / 445
Регистрация: 26.03.2015
Сообщений: 8,108
03.09.2018, 09:11 4
Если левое и правое поддерево узла А одинаковой высоты, то удаление элемента не изменит высоту дерева, а баланс станет -1 или +1.

Цитата Сообщение от Соколиный глаз Посмотреть сообщение
Как определить изменит ли высоту дерева удаление узла или нет, если есть только балансы в узлах дерева?
Удалить и посмотреть. Зависит от балансов дочерних узлов.
1
Alvin Seville
335 / 267 / 132
Регистрация: 25.07.2014
Сообщений: 4,537
Записей в блоге: 9
03.09.2018, 15:22  [ТС] 5
Shamil1, правильно ли понимаю, что просто удаляю сначала узел, потом по такому же принципу как при добавлении провожу перебалансировку и если надо поворот?
0
Модератор
2933 / 2077 / 445
Регистрация: 26.03.2015
Сообщений: 8,108
03.09.2018, 17:01 6
Лучший ответ Сообщение было отмечено Соколиный глаз как решение

Решение

Да.
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
03.09.2018, 17:01
Помогаю со студенческими работами здесь

Удаление узла дерева
Разбираюсь с удалением в дереве, начал с удаления листа и сразу же столкнулся с проблемой :wall:...

Удаление узла из дерева
Создаю дерево(картинку прикрепил): program BinTree; uses Tree; var TheRoot, P: PNode; ...

Удаление узла из дерева
сделав функции добавления,поиска,пару обходов и вывод ввиде дерева в консоли(жаль что нельзя размер...

Удаление узла бинарного дерева
Бьюсь над задачей битый час, в функцию передаю указатель на узел, который и хотим удалить. И в...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru