 |
|
|
 
|
|
Балансировка бинарных деревьев 
| 0lmer |
|
|||
|
Шустрый  Профиль Группа: Участник Сообщений: 115 Регистрация: 3.12.2006 Репутация: нет Всего: -1 |
Подскажите пожалуйста алгоритмы для балансировки и подсчета глубины бинарного дерева.
Большая просьба в гугль не посылать т. к. уже неделю ниче найти не могу. Заранее спасибо. |
|||
|
||||
Загрузка ...
| JackYF |
|
|||
 полуавантюрист Профиль Группа: Участник Сообщений: 5814 Регистрация: 28.8.2004 Где: страна тысячи озё р Репутация: нет Всего: 162 |
балансировка чистого бинарного дерева - перестроение его с нуля. Если тебе нужна динамическая и менее затратная балансировка, то тебе подойдёт "красно-чёрное дерево". Которое автоматически балансируется по мере добавления/удаления элементов. За алгоритмом - гуглить на "красное-чёрное дерово" и т.д. + алгоритм точно описан в Кормен и другие "Алгоритмы: построение и анализ". Эту книгу тоже кто-то находил в электронном виде. |
|||
|
||||
| archimed7592 |
|
|||
 Архимед Профиль Группа: Завсегдатай Сообщений: 2531 Регистрация: 12.6.2004 Где: Moscow Репутация: нет Всего: 93 |
algolist.manual.ru
-------------------- If you have an apple and I have an apple and we exchange apples then you and I will still each have one apple. But if you have an idea and I have an idea and we exchange these ideas, then each of us will have two ideas. © George Bernard Shaw |
|||
|
||||
| 0lmer |
|
|||
|
Шустрый Профиль Группа: Участник Сообщений: 115 Регистрация: 3.12.2006 Репутация: нет Всего: -1 |
еще один вопрос:
как удалить элемент из АВЛ дерева, не нарушив его сбалансированности? Узел выглядит так:
balans - разность между высотами правого и левого поддерева узла. |
|||
|
||||
| archimed7592 |
|
|||
|
Архимед Профиль Группа: Завсегдатай Сообщений: 2531 Регистрация: 12.6.2004 Где: Moscow Репутация: нет Всего: 93 |
1. Если это лист - удалить его и отбалансировать "в другую сторону".
2. Если у него есть дети, то найти минимальный элемент в правом поддереве(постоянно спускаться влево) и поменять местами этот минимальный с удаляемым. Потом удалить этот элемент, но уже так, будто он находится на том месте, где был минимальный(он уже будет листом - см. п. 1). -------------------- If you have an apple and I have an apple and we exchange apples then you and I will still each have one apple. But if you have an idea and I have an idea and we exchange these ideas, then each of us will have two ideas. © George Bernard Shaw |
|||
|
||||
| sentry |
|
|||
|
Code Monkey Профиль Группа: Участник Сообщений: 133 Регистрация: 29.1.2007 Где: Москва Репутация: нет Всего: 10 |
Да на русском вообще мало чего есть. Можешь посмотреть ТУТ. |
|||
|
||||
| bilbobagginz |
|
|||
 Naughtius Maximus Профиль Группа: Экс. модератор Сообщений: 8813 Регистрация: 2.3.2004 Где: Israel Репутация: нет Всего: 317 |
значит нужно осознать и серьезно заняться иностранным языком. напр. японским или английским. -------------------- Я ещё не демон. Я только учусь. |
|||
|
||||
| Kuvaldis |
|
|||
 механик-вредитель Профиль Группа: Участник Клуба Сообщений: 1189 Регистрация: 16.6.2006 Где: Минск Репутация: 1 Всего: 61 |
Про AVL деревья достаточно неплохо написано в классической книге Вирта "Алгоритмы и структуры данных"
-------------------- Помни - когда ты спишь, враг не дремлет Спи чаще и дольше, изматывай врага бессоницей |
|||
|
||||
| 0lmer |
|
|||
|
Шустрый Профиль Группа: Участник Сообщений: 115 Регистрация: 3.12.2006 Репутация: нет Всего: -1 |
archimed7592, а подробнее можно?
Не обязательно, у него может быть правый потомок. |
|||
|
||||
| archimed7592 |
|
|||
|
Архимед Профиль Группа: Завсегдатай Сообщений: 2531 Регистрация: 12.6.2004 Где: Moscow Репутация: нет Всего: 93 |
Ах, ну да, в таком случае: 3. Если у узла есть "поддерево"(в кавычках, потому что длинее одно узла оно быть не может), то этот элемент удаляется, а потомок подвешивается на его место. Тогда, в случае п.2, вариантов дальнейших действий будет два - либо п.1, либо п.3. Добавлено через 5 минут и 56 секунд Если бы ты прошёл по ссылке, которую я дал в 3-м посте, то увидел бы там полное руководство с иллюстрациями: http://algolist.manual.ru/ds/btree.php Всё что было сказано мной потом - это рассказ по памяти из того же источника, но т.к. читал я это очень давно, то ессно передал с неточностями. Советую прочитать этот материал, а не ждать пока всё разжуют и в рот положат. -------------------- If you have an apple and I have an apple and we exchange apples then you and I will still each have one apple. But if you have an idea and I have an idea and we exchange these ideas, then each of us will have two ideas. © George Bernard Shaw |
|||
|
||||
|
|
| Правила форума "Алгоритмы" | |
|
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Алгоритмы | Следующая тема » |
[ Время генерации скрипта: 0.0737 ] [ Использовано запросов: 21 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |