AOP_Tom3 (1021738), страница 129
Текст из файла (страница 129)
1); очевидно, эти вероятности быстро сходятся к предельным значениям при Х вЂ” ~ оо. В табл. 2 приведены точные значения вероятностей, соответствующих приведенным в табл. 1 (при Л = 10), в предположении, что все 10! перестановок равновероятны. (Вероятность, показанная в табл. 1 как имеющая значение .143, в действительности равна 1 2 3 4 >5 .143 .152 .092 .060 .036 .051 .000 .143 .048 .024 .010 009 .233 .ООО .143 .048 .024 .010 .008 .232 1/7 для всех Лс > 7; см. упр. 11.) Однократный и двукратный повороты практически равновероятны при Лс < 15, однако при /О > 16 двукратные повороты встречаются немного реже.
Таблица 2 ТОЧНЫЕ БЕРОЯТНОСТН ПРН БСТАБКЕ 10 ГО ЭЛЕМЕНТА Нет Однократный Двукратный корректировки поворот поворот Длина пути й 1/7 б/35 4/21 0 53/105 0 1/7 2/35 1/21 2б/105 0 1/7 2/35 1/21 25/105 В среднем 247/105 р = 1 — р/(1 — р) + 30 = 5/2 — р/(1 — Р).
Решение зтого уравнения относительно р дает хорошее согласование с табл. 1: 9 — ьс41 р — - 0.649; 1/(1 — р) ю 2.851. 4 Время работы фазы поиска программы А (строки 01 — 19) равно (14) (15) 10С+ С1+ 211+ 2 — ЗЗ, где С, С1 и 5 те же, что и в предыдущих алгоритлсах втой главы, а Π— число несбалансированных узлов, которые проходятся при поиске. Эмпирические тесты Из табл.
1 видно, что /с < 2 с вероятностью около .143 + .152 + .143 + .143 = .581; следовательно, спаг А6 почти в 60сУсс случаев тривиален. Среднее количество изменений фактора сбалансированности с 0 на ~1 на этом шаге примерно равно 1.8. Среднее количество изменений фактора сбалансированности с *1 до 0 на шагах А7— А10 составляет примерно .э34+ 2(.233+.232) а 1.5.
Таким образом, вставив новый узел, можно добавить в среднем около 1.8 — 1.5 = 0.3 несбалансированного узла. Это согласуется с тем, что около 68% всех узлов в сбалансированных случайных деревьях, построенных по алгоритму А, оказываются сбалансированными. Приближенная модель алгоритма А была предложена К. К.
Фостером (С. С. гов1ег) (Ргос. АСМ Хай СолЕ 20 (1965), 192 — 205). Эту модель сложно назвать абсолютно точной, но она достаточно близка к истине, чтобы дать некоторое понимание происходящего. Предположим, что в большом дереве, построенном по алгоритму А, фактор сбалансированности узла соответственно ранен 0 с вероятностью р, равен — 1 с вероятностью -'(1 — р) и равен +1 с той же вероятностью. Предположим далее (без обоснования), что факторы сбалансированности различных узлов независимы.
Значит, вероятность того, что на шаге А6 число ненулевых факторов сс — 1 равно й — 1, равна р~ '(1 — р), так что среднее значение и равно 1/(1 — р). Вероятность того, что потребуется повернуть часть дерева, равна 0 = -'. Вставка нового узла должна увеличить количество сбалансированных узлов в среднем на р; зто число увеличивается на 1 на шаге А5, на — р/(1 — р) на спаге А6, на д на шаге А7 и на 20 на шаге А8 или А9, так что должно получиться показывают, что можно принять Р— -'С, С1 ж -'(С+ Я), С+ Я 1.01)КЖ+ 0.1, так что среднее время поиска примерно равно 11.3 18Ж + 3.3 — 13.75 единиц. (Если поиск осуществляется значительно чаще вставки, конечно же, можно использовать отдельную, более быструю программу поиска, поскольку не нужно следить за факторами сбалансированности.
В этом случае среднее время работы при успешном поиске составило бы около (6.6 18Ф вЂ” 3.4)и и даже в наихудшем случае было бы меньше, чем среднее время работы программы 6.2.2Т.) При неудачно завершенном поиске время работы фазы вставки программы А (строки 20-45) составляет 8А + 26+ (О, 1 или 2) единиц. Данные из табл. 1 показывают, что в среднем г' 1.8. Для фазы балансировки (строки 46-101) требуется 16.5, 8, 27.5 или 45.5 (х0.5) единиц времени в зависимости от того, что мы делаем: увеличиваем общую высоту, просто выходим (без балансировки) или выполняем однократный либо двукратный поворот. Первый случай практически не встречается; вероятности остальных составляют около .534, .233 и .232,, так что среднее время работы комбинированной "вставочно-балаисировочиой" части программы А— примерно 63и.
Эти числа показывают, что операции над сбалансированными деревьями выволняются достаточно быстро, хотя программы при этом несколько бачьше по размеру. При случайных входных данных простой алгоритм вставки в дерево, описанный в разделе 5.2.2, работает быстрее примерно на 50и на одну вставку. Однако, используя сбалансированные деревья, можно получить хорошие результаты даже при неслучайных входных данных. Один из способов сравнения программы А с программой 6.2.2Т заключается в рассмотрении наихудшего для последней программы случая.
Если попытаться выяснить, сколько времени потребуется для вставки Л' ключей в порядке возрастания в изначально пустое дерево, то окажется, что программа А работает медленнее при Х ( 26 и быстрее — при Х > 27. Представление линейных списков. Теперь вернемся к следующему сделанному в начале этого раздела замечанию: сбалансированные деревья могут использоваться для представления линейных списков таким образом, что можно будет быстро вставлять элементы в список, преодолевая трудности, которые связаны с последовательным расположением элементов, и обеспечивая при этом произвольный доступ к элементам списка, т.
е. преодолевая сложности связанного размещения элементов. Идея состоит во введении нового поля КАХК в каждом узле. Это поле указывает относительное положение узла в его поддереве, а именно -.- единица плюс количество узлов в его левом подлереве. На рис. 24 показаны значения КАМК для бинарного дерева, приведенного на рис. 23. При представлении списков поле ККУ можно полностью исключить (при желании можно оставить оба поля, чтобы иметь возможность находить элементы как по значению ключа, так и по относительному положению в списке).
Используя такое поле КАМК, можно свести поиск по положению элемента к модификации уже изученных нами алгоритмов. Алгоритм В (Поиск в дереве по положению элемента). Дан линейный список, представленный в виде бинарного дерева. Алгоритм позволяет найти А-й элемент списка (А-й узел дерева в симметричном порядке) по заданному А.
Предполагается, Рис. 24. Поля ЯАМК Лля поиска по положению элемента в списке. что, как и в алгоритме Л, имеется головной узел и что узлы дерева имеют поля ЬЬХМК и КЬ1МК, а также описанное поле ВАМК. В1.[Инициализация.] Установить М +- А, Р +- НЫМК(НЕАВ). В2.[Сравнение.] Если Р = Л, алгоритм заканчивается неудачно (это может произойти, только если А было болыпе, чем количество узлов в дереве, или А < О). В противном случае, если М < НАМК(Р), перейти к шагу ВЗ; если М > НАМК(Р), перейти к шагу В4; если М = ВАМК(Р), алгоритм успешно завершается (Р указывает на /с-й узел). ВЗ. [Перемещение влево.] Присвоить Р е- ЬЫМК(Р) и вернуться к шагу В2.
В4. [Перемещение вправо.] Присвоить М е- И вЂ” НАМК(Р) и Р е — НЬХМК(Р) и вернуться к шагу В2. 1 В этом алгоритме определенный интерес представляет только операция над И на шаге В4. Аналогично можно модифицировать процедуру вставки элемента, хотя в этом случае имеются определенные тонкости. Алгоритм С (Вставка в сбалансированное дерево по положению). Дан линейный список, представленный в виде сбалансированного бинарного дерева. Ллгоритм вставляет новый узел непосредственно перед й-м элементом списка по заданным й и указателем Ц на новый узел.
Если й = Х+ 1, новый узел вставляется за последним элементом списка. Бинарное дерево, как и в случае использования алгоритма Л, предполагается непустым, имеющим головной узел; также предполагается, что узлы имеют поля ЬЬ1МК, НЫМК и В, а также поле НАМК, описанное выше. Этот алгоритм очень похож на алгоритм А; отличие заключается в использовании и обновлении яшей ВАМК вместо КЕУ. С1. [Инициализация,! Установить Т е- НЕАВ, Я < — Р е- НЫМК(НКАО), Н ~ — М < — й.
С2. [Сравнение.] Ести И < НАМК(Р), перейти к шагу СЗ, в противном случае перейти к шагу С4. СЗ. [Перемещение влево.) Установить НАМК(Р) < — НАМК(Р) + 1 (будем вставлять новый узел слева от Р). Установить Н +- ЬЫМК(Р). Если Н = Л, присвоить ЬЫМК(Р) +- Ц и перейти к шагу С5. В противном случае, если В(Н) эв О, присвоить Т +- Р, Я +- Н и О <- И. И, наконец, присвоить Р <- Н и вернуться к шагу С2. С4. (Перемещение вправо.] Установить И < — И вЂ” НАМИ(Р) и Н +- НЫМК(Р).
Если Н = Л, присвоить НЫМК(Р) +- Ц и перейти к шагу С5, В противном случае, если В(Н) ф О, .присвоить Т +- Р, Я +- Н и 0 +- И. И, наконец, присвоить Р < — Н н вернуться к шагу С2. С5. (Вставка.] Установить НАМК(Ц) < — 1, (.ЫМК(Ц) < — 81.1МК(Ц) +- Л, В(Ц) < — О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
