AOP_Tom3 (1021738), страница 128
Текст из файла (страница 128)
А10. [Последний штрих.] (Балансирующее преобразование (1) в (2) завершено; Р указывает на корень нового поддерева, а Т вЂ” иа родитечьский по отношению к корню старого поддерева узел Я.) Если Б = Нь1ИК(Т), следует установить НЕ1ИК(Т) е- Р; в противном случае следует установить ЕЕ1ИК(Т) е- Р. 1 Программа А (Поиск со вставкой но сбалансированному дереву). Эта программа, реализующая алгоритм А, использует узлы дерева в следующем формате: (4) гА:— К, г11 = Р, г12 ев Ц, г13 ив в Н, г14 г— в Я, г15 = Т. Код шагов А7-Л9 дублируется, так что значение а используется в программе в неявном виде.
01 В ЕЦО О ! 00 1Е1ИК ЕЦ0 2:3 Этот алгоритм достаточно длинный, однако разделяется на три простые части: на шагах А1 — А4 осуществляется поиск, на шагах А5-А7 — вставка нового узла и на шагах А8 — Л10 при необходимости ребалансируется дерево. Тот же алгоритм может использоваться и для ирошитых деревьев (см. упр. 6.2.2 — 2). 14звестно, что для этого алгоритма требуется около С!о8 Х единиц времени, где С вЂ” некоторая константа.
Однако следует оценить ее величину, чтобы знать, при каких Х использование сбалансированных деревьев становится эффективнее других алгоритмов. Приведенная ниже И1Х-реализация алгоритма позволяет приступить к решению этого вопроса. 4Н 1Н 7Н (11 С1+ 31 32Р РОМЕ 32Е 7Р А75 50 51 ОЯ 04 Об Об 07 ОВ 09 19 11 12 13 Ц 15 15 17 1В 19 20 21 22 23 24 25 2б 27 2В 29 ЯО 31 32 33 34 35 37 ЯВ Я9 40 41 42 43 й 45 бб 47 43 19 К11ИК БТАКТ 4Н 1Н 2Н 5Н 1Н ОН ЕЦУ 4:5 1РА К ЕИТ5 НЕАР РР2 0,5(Н11ИК) ЯИР 2Р 1.02 0,1(К11ИК) 322 5Р 1РХ 0,2(В) ЭХЕ е+3 ЕМТЯ 0,1 ЕМТ4 0,2 ЕМТ1 0,2 СИРА 1,1 36 4В ЮЕ БОССЕБЯ РР2 0,1(ШИК) 32ИЕ 1В 102 АЧАП.
32Е ОУЕВР10Ы 1РХ 0,2(Н11МК) ЯТХ АУА11 ЯТА 1,2 ЯТЕ 0,2 1Р ЯТ2 0,1(НР1ИК) ЯИР и+2 ЯТ2 0,1(111ИК) СИРА 1,4 и+3 ЫЗ 0,4(Н11МК) ЛИР и+2 РРЗ 0,4К11МК) ЕМТ1 О,З ЕИТХ -1 ЭНР 1Р ЮЕ 7Р БТХ 0,1(1:1) Ы1 0,1(ВНИК) СИРА 1,1 ЛОЕ 4В БТХ 0,1(В) 1.01 0,1(1ПИК) ЗНР 1В 1.02 0,4(В) БТЕ 0,4(В) СИРА 1,4 ЭО А7В 1 1 1 1 С2 С2 С вЂ” 1 С вЂ” 1 () — 1 1) С С С С1 С1 — Я С1 — Я 1 — 5 1 — Я 1 — Я 1 — Я 1 — Я 1 — Я 1 — Я А А 1 — Я вЂ” А 1 — 5 1 — Я Е Е 1 — Я вЂ” Е 1 — Я 1 — Я 1 — 5 Р'2+ 1 — Я Р2 2'2 Р'+ 1 — 5 Г+1 — Я Р'1 А'1 Г1 1 — Я 1 — Я 1 — 5 1 — Я ЕА,Н Т <- НЕАР.
Ц +- В11ИК(НЕАР). Переход к А2 с Б < — Р е — Ц. А4. Пе еме ение еп аво. Ц < — В11ИК(Р). Переход к шагу АБ при Ц = А. гХ <- В(Ц). Переход, если В(Ц) = О. Т е — Р. Б — Ц. Р е- Ц. ис-. Переход к шагу А4, если К > КЕТ(Р) . Выход при К = КЕТ(Р). АЗ. Пе еме ение влево. Ц < — ШИК(Р) Переход при Ц ф Л. А5. Всгаека, Ц ~ АТА11.. КЕТ(Ц) е — К ШИК(Ц) +- В11ИК(Ц) +- А.
К < КЕТ(Р1' ВЫИК(Р) < — Ц 1.1.1ИК(Р) <- Ц. Аб. Ко екги евка акга а ~б Переход при К ( КЕТ(Б). В с- В11ИК(Б). В +- Ы.ХИК(Б). Р е- В, гХ < — — 1. Переход к циклу сравнении. Переход к шагу А7, если К = КЕТ(Р). В(Р) +-+1 (было +О), Р < — В11ИК(Р). Переход при К > КЕТ(Р).
В(Р) <- — 1. Р н П.1ИК(Р). Переход к циклу сравнения. АЕ и ~ ц~~ 11 и). В(Б) с — О. Переход к подпрограмме а = +1 при К > КЕТ(Б) . Выход при г12 = -а. Переход, если В(Б) было равно О. С1 С1 С1 Н1 Н1 Н1 Н1 Н1 Н1 Н1 Н1 Н1 С1 С1 С1 С1 У2 С2+ 32 С2 С2 С2 Н2 Н2 Н2 Н2 Н2 Н2 Н2 Н2 Н2 С2 С2 С2 С С С СЗ СЗ С4 С4 Таблица для (3). 32 3 У 3 У 1 — Я 52 53 51 55 АОЕ 56 57 53 59 60 61 62 63 61 А8Е 66 67 66 А7К 69 70 71 72 73 А9К 'Ц 75 76 77 76 79 Во 31 62 АЯК 63 34 65 ЗН Вб АТО 67 бб 69 90 91 92 93 Т1 94' Т2 95 96 бн 97 7Н 93 99 100 101 НОМЕ ЕИТ1 0,3 102 0,3(В) 32М А8Е 101 0,3(КЫИК) ЕОХ 0,1(ШИК) ЯТХ 0,3(К11МК) ЯТЗ 0,1(ШИК) 102 0,1(В) ЕОХ Т1,2 БТХ 0,4(В) ЫХ Т2,2 БТХ 0.3(В) ЫХ 0,1(КЕ1ИК) БТХ 0,4(ШИК) БТ4 0,1(КЕ1МК) ЗНР ВР 32И ООИЕ 322 бр ЕИТ1 0,3 П)2 0,3(В) 32Р А8К Ы1 0,3(Ы.ТМК) ЕОХ 0,1(КПИК) ЯТХ 0,3(ШИК) БТЗ 0,1(К11ИК) 1.02 0,1(В) ЕОХ Т2,2 БТХ 0,4(В) ЕОХ Т1,2 ЯТХ 0,3(В) ЬОХ 0,1(Е11ИК) ЯТХ 0,4(К11МК) БТ4 0,1(ШМК) БТ2 0,1(В) СНР4 Огб(КАМЕ) ЗИЕ к+3 БТ1 0,8(КПИК) ЗМР ООИЕ ЯТ1 О,б(?Л.1МК) ЭМР ООИЕ СОИ +1 СОМ 0 СОИ О СОМ -1 ЕИТХ +1 БТХ 0,4(В) 1ОХ НЕАО(ШИК) 1МСХ 1 ЯТХ НЕАО(ШМК) ЕЦО Р к- К г12 г- В(В).
Переход к шагу ЛВ при г12 = а. А9. век атный ново от. Е1МК(а,Р < — 11МК(-а,В)) -+ Е1МК( — а,В). Е1МК(а,Р) к в К. г12 < — В(Р). — а, О илий -+ В(Б). О,Оилиа -+ В(К). Аб. О нок атный поко ох 11МК(а,Б) +-Е1МК( — а,Р). ПМК(-а,р) г- Б. Объединение с другой ветвью, Выход при г12 = -а. Переход, если В(Б) было равно О. Р к в В. г12 < — В(В). Переход к шагу А8 прн г12 = а. А9. ~ в к атный ново от.
11МК(а.р < — 1.1МК( — а,В) ) -г Е1МК (-а, К) . Е1МК(а,р) г- В. г12 к — В(Р). -а, 0 или 0 -+ В(Б). О, 0 нли а -+ В(К). Аб. О нок атный пово от 11МК(а,Б) < — ЫМК( — а,р). 1.1МК( — а,Р) +- Б. В(Р) + — О. А10. После ннй шт их. Переход прн К1.1МК (Т) Р. Б. М.1МК(Т) +- Р Выхг д. 21.1МК(Т) 1 — Р. Выход. гХ г — +1. В(Б) +- а. ШМК(НКАО) +1 -+ [Л.1МК(ВЕАО). Вставка завершена. ! Анализ вставки в сбалансированное дерево. (Те, кому математика кажется скучной и недостойной внимания, могут пропустить материал до (10).] Для выяснения времени работы алгоритма А необходимо ответить на следующие вопросы.
° Сколько сравнений будет выполнено во время поиска". ° Как далеко друг от друга будут находиться узлы Б н 07 Иными словами, сколько корректировок будет проведено на шаге А67 о Как часто будут выполняться однократные и двукратные повороты? Несложно найти верхнюю границу времени работы программы, воспользовавшись теоремой А, однако с практической точки зрения нас, еотественно, интересует среднее время работы. До сих пор нет теоретического вывода поведения алгоритма в среднем в связи с его сложностью, однако были получены некоторые интересные частные теоретические и эмпирические результаты, В первую очередь, нас лэожет заинтересовать количество В„л сбалансированных бинарных деревьев с и внутренними узлами и высотой 1~,.
Для небольших А из соотношений Во(г) = 1, В~(г) = г, Влео(г) = гВл(г)(Вл(г) + 2Вл,(г)) (5) нетрудно вычислить производящую функцию Вл(г) = 2 о>о В„лг" (см. упр. 6). Таким образом, Вг(г) 2гг + гэ Вз(г) = 4г4 + бгл + 4го + гт Вл(г) = 16гт + 32го + 44го + + 8гы + гго и вообще, Вл(г) при Ь > 3 имеет вид Ь Л 2л"" лгк" ' ~ -л2~"" гол ~г~"" + сложные члены+ 2л лгг г+ г- ~, (6) где бл —— Ел.,~ + .Е~ м (Эта формула обобщает теорему А.) Общее количество сбалансированных деревьев высотой й равно Вл — — Вл(1) и удовлетворяет рекуррентному соотношению Во — — В~ —— 1, Вл~.~ = Вгл + 2ВлВл (7) так что Во =3, Вз =3.5, В4 =Зт 5.7, Вл =Зэ.5~.7.23; вобщем случае В = АклА " '...
А~' А'о л= о о . -л.-э л (8) где Ао = 1 А~ = 3, .4г = 5, Аэ = 7, Ал = 23, Ао = 347, ..., Ал = Ал — ~Вл — г + 2. Последовательности Вл и Ал растут очень быстро —. как экспонента экснонснгвлк в упр. 7 показано, что существует действительное число д — 1.43687, такое, что ~рг'~ ~6г"-'~ ~6т"-'~ + 1)л айт'~ Если положить, что все Вл деревьев равновероятны, то, как показано в упр.
8, среднее число узлов в дереве высотой й равно В,',(1)/Вл(1) в (0.70118) 2л — 1. (10) Это означает, что высота сбалансированного дерева с А? узлами обычно гораздо ближе к 1обг Ю, чем к 1ояо Х. К сожалению, этн результаты в действительности не имеют отношения к алгоритму А, поскольку механизм построения деревьев делает одни из них существенно более вероятными, чем друтие. Например, рассмотрим случай. когда Ж = 7, при котором имеется 17 сбалансированных деревьев.
Существует 7! = 5 040 возможных способов вставки ключей в дерево, При этом идеально сбалансированное 'совершенное" дерево получается 2160 раз. Дерево же Фибоначчи (12) образуется только в 144 случаях, а похожее на него дерево (13) будет получено 216 раз. Заменив левые полдеревья в (12) и (13) произвольными сбалансированнымн деревьями с четырьмя узлами и использовав зеркальное отображение относительно вертикальной оси, получим 16 различных деревьев.
Восемь из них, полученные из (12), встречаются по 144 раза, а полученные из (13) — по 216 раз. Как зто ни странно, деревья (13) встречаются чаще, чем (12). Тот факт, что идеально сбалансированные деревья образуются с такой высокой вероятиями:тью, и формула (10), соответствующая случаю равных вероятностей, делают весьма правдоподобным заключение о том, что для среднего времени поиска по сбалансированному дереву необходимо требовать около 1к Л + с сравнений, где с малб. Р.
В. Флойд (В. %. Г!оус1) обнаружил, что коэффициент при 1кХ не ранен в точности 1, поскольку тогда корень дерева должен быгь очень близок к медиане, а корни поддеревьев — около четвертых частей. Однако однократные и двукратные повороты не могут просто оставить корень дерева в медиане. Эмпирические исследования показали, что реальное среднее количество сравнений, необходимых для вставки Аг-го элемента, примерно равно 1.01 1к Ай + 0.1 при не очень малых Х. Для изучения поведения фаз вставки и балансировки алгоритма А можно классифиинровагь внешние узлы сбалансированного дерева, как показано на рис.
23. Путь, ведущий вверх яз внешнего узла, определяется последовательностью плюсов и минусов ("+" для правой ссылки н "-" для левой ссылки). Сначала записываем последовательность до тех пор, пока не будет достигнут первый узел с ненулевым Рис. 23. Классификация, определяющая поведение алгоритма А после вставки. фактором сбалансированности или (если такого узла нет) пока не будет достигнут корень. Затем добавляем А нли В в соответствии с тем, будет ли новое дерево после вставки в данное место внутреннего узла сбалансированным. Так, путь вверх от ~Я записывается как ++-В, что означает "правая ссылка, правая ссылка, левая ссылка, несбалансировано".
Запись, оканчивающаяся на А, означает, что балансировка после вставки нового узла не требуется, для записи, завершающейся на ++В или --В, необходим однократный поворот, а для записи, завершающейся на +-В нли -+В, двукратный поворот. Если в пути встречается 1г звеньев, на шаге Аб корректируется ровно к — 1 факторов сбалансированности. Таким образом, описанные последовательности предоставляют необходимую информацию о времени работы шагов Аб — А10. Таблица 1 ПРИБЛИЖЕННЫЕ ВЕРОЯТНОСТИ ПРИ ВСТАВКЕ Х-ГО ЭЛЕМЕНТА Однократный Двукратный поворот поворот Нет корректировки Длина пути Й Всего .534 В среднем 2.78 Эмпирические тесты со случайными числами в количестве 100 < Х < 2000 дали приближенные вероятности для путей различных типов (табл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
