Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 27
Текст из файла (страница 27)
АЯ. Пс еме ение влево. О+-П.1ИК(Р). Переход при 0 )а Л. Аб. Всаавка. 0 с АУАП.. кет(0) +- к шик(В) а- 3313к(О) а- Л. К < КЕУ(Р1в В(ДИК(Р) +- 0 Ы.|ИК(Р) Ф- О. Аб. Ко кги ваа акга а 4Н 1Н 7Н (71 С1+ 91 Ю2Р ООМЕ 122 7Р 81 Я2 ЯЯ 84 86 Я8 89 19 11 42 48 88 86 46 47 88 89 ЯЕ в+3 103 0,4(НПИК) ЯИР в+2 Е03 0,4(1ПИК) ЕИТ1 0,3 ЕИТХ -1 ЯИР 1Р ЯЕ 7Р ЗТХ 0,1(1:1) 1.01 0,1(НПМК) СИРА 1,1 ЛОЕ 4В ЗТХ 0,1(В) 101 0,1((.ПИК) ЯИР 1В Ы2 0,4(В) ЗТХ 0,4(В) СИРА 1,4 Яо А7Н 1 — Я Е Е 1 — Я вЂ” Е 1 — Я 1 — Я 1 — Я Г2+ 1 — Я Г2 Г2 Г+1 — Я Г+1 — Я Г1 Г1 Г1 1 — Я 1 — Я 1 — Я 1 — Я Переход при К С КЕТ(3) .
В +- 3(ДИК(3) . К а- ЫЛИК(3). Ра-н, ГХ Ф- -1. Переход к циклу сравнения. Переход к шагу А7, если К = КЕТ(Р) . В(Р) +- +1 (было +О). Р+- ВЬУИК(Р). Переход при К > КЕУ(Р). В(Р) +- — 1. Р ы П.133(Р), Переход к циклу сравнения. АТ. В~о~, я2 ВЮ. В(3) а- О, Переход к подпрограмме о = +1 при К > КЕТ(3). Выход при г12 = -о.
Переход, если В(3) было равно О. Таблица для (3). 68 68 64 66 А9Ь 66 67 68 6У 66 61 68 68 64 Авь 65 66 67 68 АТВ 6У 76 71 79 78 А9В 74 76 76 77 78 7У 80 81 89 АВВ 88 84 86 ВН 86 А|О 87 88 89 УУ У| УБ 98 т| 94 т2 96 96 ВН 97 7Н 98 УУ 160 161 ООИЕ кит| о,з Ь02 О,З(В) |2И АЗ!. Ьо| О,З(ВЫИК) ьох о,|(ьыик) зтх о,зО|ыик) зтз о, ыы,|ик) Ь02 0,1(В) Ьох Т1,2 зтх о,4(в) ьох Т2,2 зтх о,з(в) ЬВХ О,|(ВЫИК) зтх о,4(ьыик) зт4 о,|(кыик) ЛИР ЗР 32И ООИЕ |22 ВР кит| о,з Ь02 0,3(В) 12Р АВВ ьо| о,з(ьыик) ЬОХ О.
1(ЯЫИК) зтх о,з(ьымк) зтз о,|(кыик) Ь02 О, 1(В) ЬОХ Т2,2 ЗТХ 0,4(В) ьох т|,2 зтх о,з(в) ЬВХ О, 1(ЬЫИК) ЗТХ 0,4(ВЫИК) зт4 0,1(ьыик) зтх о,|(в) СИР4 0,5(ВЛ.|МК) Лия е+3 зт| о д(выик) УИР Ооия зт| о,б(ьыик) ЛИР ООМЕ сои +| СОИ О сои о СОИ -1 яитх +1 ЗТХ 0,4(В) ЬОХ НЕВА(ЬЫИК) |ИСХ 1 зтх нейо(ьыик) ЕЦО С1 С1 С| Н1 Н1 Н1 Н1 Н1 Н! Н1 Н| Н1 С1 С1 С1 С! (72 С2+ Уг С2 С2 С2 Н2 Н2 Н2 Нг Н2 нг Н2 Нг Н2 С2 аг С2 С С С аз аз С4 С4 Р г- В. г12 В(В) . Переход к шагу АБ при г12 = а. А9.
вен атный ново от. ЫИК(а,Р ( — ЫИК(-а,В) ) -+ ЫИК(-а,В) ЫИК(а,р) е- В. Н2 е- В(Р). -а, О или о -+ В(Б) . О, О нли а -+ В(В). 8 О нок атный ново т ЫИК(а.з) +- Ь|ИК(-а,Р). Ь|ИК(-а,Р) +- Б. Объединение с другой ветвью. Выход при г12 = -а. Переход, если В(Б) было равно О. Р г — В. г!2 е- В (В).
Переход к шагу АБ прн г12 = а. А9. в атный пово от. ЫИК(а,Р +- ! |ИК(-а,В)) -+ ЫИК(-а,В). ЫИК(а,р) +- В, г!2 +- В(Р). -а,онлно -+ В(Б). О, О или а -г В(В). А8. О нок атный пово от. !.ХИК(а.з) г- !.1ИК(-а.Р) . Ь|ИК( — а,р) г — Б. В(Р) +-О. А10. После ггй шт нх. Переход при ВЬ1ИК(Т) ф Б. ВЬ1ИК(Т) +- Р. Выход. !.ЫИК(Т) +- Р, Выход. гХ < — +1. В(Б) +- а. ЬЫИК(НКАО) +1 -+ ЬЫИК(НКАО) . Вставка завершена. $ Вз(г) = г, Вь+з(г) = гВз(г)(Вв(г) + 2Вз з(г)) (5) производящую функцию Вь(г) = 2, „В„„г" (см, упр 6) Ве(г) = 1, нетрудно вычислить Таким образом, Вз(г) = 2гз + Вз(г) = В4(г) гз, 4гз+бгз+4 б+ з 16г' + 32гз + 44гв + -.
° + 8гы + г'з, и вообще, Вв(г) при Ь > 3 имеет внд 2я"»' ~г~"»' ~+2~'»' ~1з г~"»'+сложные члены+2" 'гз з+г- ' (6) где Хз = Гз+з + гь и (Эта формула обобщает теорему А.) Общее количество сбалансированных деревьев высотой Ь равно Вз = Вь(1) и удовлетворяет рекуррентному соотношению Ве = Вз = 1 Вз+з = Вз + 2Вь В -ы (7) так что Вз = 3, Вз = 3-5, В4 = 3' ° 5 7, Вз = 3з 5з ° 7.
23; в общем случае В Азз ~~» — ~ Азз Анз (8) где Ае = 1, Аз = 3, Аз = 5, Аз = 7, Аз — — 23, Аз = 347, ..., Аь = Аь-зВз-з + 2. Последовательности Вь и Аь растут очень быстро -- как экспонента экспонеппзы: в упр. 7 показано, что существует действительное число д — 1,43687, такое, что В =Фй'1-И' 1+Фйз 1-" +(-)"Фраат. (9) Если положить, что все Вз деревьев равновероятны, то, как показано в упр. 8„ среднее число узлов в дереве высотой Ь равно В„'(1)/Вь (1) (0.70118) 2" — 1. (10) Это означает, что высота сбалансированного дерева с Ю узлами обычно гораздо ближе к !ойтуз. чем к )ой,,Х.
Анализ вставки в сбалансированное дерево. (Те., кому математика кажется скучной и недостойной внимания, могут пропустить материал до (10).) Для выяснения времени работы алгоритма А необходимо ответить на следующие вопросы. ° Сколько сравнений будет выполнено во время поиска? в Квк далеко друг от друга будут находиться узлы Я и Ц? Иными словами, сколько корректировок будет проведено на шаге Аб? ° Как часто будут выполняться однократные и двукратные повороты? Несложно найти верхнюю границу времени работы программы, воспользовавшись теоремой А, однако с практической точки зрения нас, естественно, интересует среднее время работы.
До сих пор нет теоретического вывода поведения алгоритма в среднем в связи с его сложностью, однако были получены некоторые интересные частные теоретические н эмпирические результаты. В первую очередь, иас может заинтересовать количество В„ь сбалансированных бинарных деревьев с и внутренними узлами и высотой Ь.
Для небольших Ь из соотношений К сожалению, эти результаты в действительности не имеют отношения к алгоритму А, поскольку механизм построения деревьев делает одни из них существенно более вероятными, чем другие. Например, рассмотрим случай, когда М = 7, прн котором имеется 17 сбалансированных деревьев. Существуег 7! = 3 040 возможных способов вставки ключей в дерево, При этом идеально сбалансированное "совершенное" дерево получается 2160 раз.
Дерево же Фибоначчи (12) образуется только в 144 случаях, а похожее на него дерево (13) будет получено 216 раз. Заменив левые поддеревья в (12) и (13) произвольными сбалансированными деревьями с четырьмя узлами и использовав зеркальное отображение относительно вертикальной оси, получим 16 различных деревьев, Восемь из них, полученные из (12), встречаются по 144 раза, а полученные из (13) — по 216 раз. Как это ни странно, деревья (И) встречаются чаще, чем (12).
Тот факт„что идеально сбалансированные деревья образуются с такой высокой вероятностью, и формула (10), соответствующая случаю равных вероятностей, делают весьма правдоподобным заключение о том, что для среднего времени поиска по сбалансированному дереву необходимо требовать около )к 37+ с сравнений, где с мало. Р. В, Флойд (11. %. Г!оус!) обнаружил, что коэффициент прн !кй( не равен в точности 1, поскольку тогда корень дерева должен быть очень близок к медиане, а корни поддеревьев — около четвертых частей. Однако однократные и двукратные повороты не могут просто оставить корень дерева в медиане.
Эмпирические исследования показали, что реальное среднее количество сравнений, необходимых для вставки Л-го элемента, примерно равно 1.01!к%+ 0.1 при не очень малых Х. Для изучения поведения фаз вставки н балансировки алгоритма А можно классифицировать внешние узлы сбалансированного дерева, как показано на рис. 23. Путь, ведущий вверх из внешнего узла, определяется последовательностью плюсов н минутов ("+" для правой ссылки и "-*' для левой ссылки).
Сначала записываем последовательность до тех пор, пока не будет достигнут первый узел с ненулевым Рис. 23. Классификация, определяющая поведение алгоритма А после вставки. фактором сбалансированности или (если такого узла нет) пока не будет достигнут корень. Затем добавляем А или В в соответствии с тем, будет ли новое дерево после вставки в данное место внутреннего узла сбалансированным. Так, путь вверх от 1Я записывается как ++-В, что означает 'правая ссылка, правая ссылка, левая ссылка, несбалансировано". Запись, оканчивающаяся на А, означает, что балансировка после вставки нового узла не требуется, для записи, завершающейся на ++В или — В, необходим однократный поворот, а для записи, завершающейся на +-В или -+В, — двукратный поворот.
Если в пути встречается Й звеньев, на шаге Аб корректируется ровно Й вЂ” 1 факторов сбалансированности. Таким образом, описанные последовательности предоставляют необходимую информацию о времени работы шагов АО-А10. Таблица 1 ПРИБЛИЖЕННЫЕ ВЕРОЯТНОСТИ ПРИ ВСТАВКЕ Ф-ГО ЭЛЕМЕНТА Нет Однократный Двукратный корректировки поворот поворот Длина пути й В среднем 2.78 Эмпирические тесты со случайными числами в количестве 100 < М < 2000 дали приближенные вероятности двя путей различных типов ~табл. Ц; очевидно, зти вероятности быстро сходятся к предельным значениям при У -+ оо.
В табл. 2 приведены точные значения вероятностей, соответствующих приведенным в табл. 1 (при Х = 10), в предположении, что все 10! перестановок равновероятньь (Вероятность, показанная в табл. 1 как имеющая значение .143, в действительности равна 1 2 3 5 >5 . 143 .152 .092 .060 .036 .051 Всего .534 .000 .143 .048 .024 .010 .009 .233 ,ООО .143 .048 .024 .010 .008 .232 1/7для всех Х > 7; см. упр.
11.) Однократный и двукратный повороты практически равновероятны при Х < 15, однако при М > 16 двукратные повороты встречаютсн немного реже. Таблица 2 ТОЧНЫЕ ВЕРОЯТНОСТИ ПРИ ВСТАВКЕ 10-ГО ЭЛЕМЕНТА Длина пути й Нет Однократный Двукратный корректировки поворот поворот 1/7 6/35 4/21 0 53/105 0 1/7 2/35 1/21 26/105 0 1/7 2/35 1/21 26/105 В среднем 247/105 р = 1 — р/(1 — р) + За = 5/2 — р/(1 — р). Решение этого уравнения относительно р дает хорошее согласование с табл. 1: 9- э/4Т р ж 0.649; 1/(1 — р) 2.851.
4 Время работы фазы поиска программы А (строки 01-19) равно (14) (15) 10С+ С1+ 2Е1+ 2 — Зо, где С,, С1 и о' те же, что и в предыдущих алгоритмах этой главы, а Р— число несбалансированных узлов, которые проходятся при поиске. Эмпирические тесты р1з табл. 1 видно, что /г < 2 с вероятностью около .143+ .152+ .143+ .143 = .581; следовательно, щаг Аб почти в 60% случаев тривиален. Среднее количество изменений фактора сбалансированности с 0 на х1 на этом шаге примерно равно 1,8. Среднее количество изменений фактора сбалансированности с х1 до 0 на шагах А7- А10 составляет примерно .534+ 2(,233+ .232) ю 1.о. Таким образом, вставив новый узел, можно добавить в среднем около 1.8 — 1.5 = 0.3 несбалансированного узла.
Это согласуется с тем, что около 68% всех узлов в сбалансированных случайных деревьях, построенных по алгоритму А, оказываются сбалансированными. Приближенная модель алгоритма А была предложена К. К. Фостером (С. С. Роэгег) (Ргос. АСМ Хаа СовЕ 20 (1965), 192 — 205). Эту модель сложно назвать абсолютно точной, но она достаточно близка к истине, чтобы дать некоторое понимание происходящего. Предположим, что в большом дереве, построенном по алгоритму А, фактор сбалансированности узла соответственно равен 0 с вероятностью р, равен -1 с вгроитностью -'(1 — р) и равен +1 с той же вероятностью. Предположим далее (без обоснования), что факторы сбалансированности различных узлов независимы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
