Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 28
Текст из файла (страница 28)
Значит, вероятность того, что на шаге Аб число ненулевых факторов и — 1 равно к — 1, равна р~ '(1 — р), так что среднее значение и равно 1/(1 — р). Вероятность того, что потребуется повернуть часть дерева, равна д -'. Вставка нового узла должна увеличить количество сбалансированных узлов в среднем на р; это число увеличивается на 1 на шаге А5, иа -р/(1 — р) на шаге Аб, иа д иа шаге А7 и на 2о на шаге А8 или А9, так что должно получиться показывают, что можно принять В ж 1С, С1 1(С + Я), С + э ж 1.0118Ю+ 0.1, так что среднее время поиска примерно равно 11.3 1К Ю + З.З вЂ” 13.7Я единиц.
(Если поиск осуществляется значительно чаще вставки, кояечно же, можно использовать отдельную, более быструю программу поиска, поскольку не нужно следить за факторами сбалансированности. В этом случае среднее время работы при успешном поиске составило бы около (6.6)8 Ф вЂ” 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. (Инициализация,) Установить М +- А, Р +- ВЫМК(НЕАй). В2. (Сравнение.) Ешш Р = Л, алгоритм заканчивается неудачно (это может произойти, только если А было больше, чем количество узлов в дереве, или А < О).
В противном случае, если М < ВАМК(Р), перейти к шагу ВЗ; если М > ВАМК(Р) „перейти к шагу В4; если М = ВАМК(Р), алгоритм успешно завершается (Р указывает на А-й узел). ВЗ. (Перемещение влево,) Присвоить Р +- ьЫМК(Р) и вернуться к шагу В2. В4. (Перемещение вправо.) Присвоить М < — М вЂ” ВАМК(Р) и Р ВЫМЕ(Р) и вернуться к шагу В2. $ В э и алгоритме определенный интерес представляет только операция над М на шаге В4. Аналогично можно модифицировать процедуру вставки элемента, хотя в этом случае имеются определенные тонкости.
Алгоритм С (Всгаавка в сбалаисироваююе дерево по положению). Дан линейный список, представленный в виде сбалансированного бинарного дерева. Алгоритм вставляет новый узел непосредсгвенно перед й-м элементом списка по заданным Й и указателем Ц на новый узел. Если Й = Х + 1, новый узел вставляется за последним элементом списка. Винарное дерево, как и в случае использования алгоритма Л, предполагается непустым, имеющим головной узел; также предполагается, что узлы имеют поля 1 ЫМК, ВЕ1МК и В, а также поле ВАМК, описанное выше. Этот алгоритм очень похож на алгоритм А, отличие заключается в использовании и обновлении полей ВАМК вместо КЕУ.
С1. (Инициализация.) Установить Т +- НЕАй, Е +- Р +- ВЫМК(НКАО), О +- М +- А. С2. (Сравнение.) Если М < ВАМК(Р), перейтн к шагу СЗ, в противном случае перейти к шагу С4. СЗ. (Перемещение влево.) Установить ВАМК(Р) +- ВАМК(Р) + 1 (будем вставлять новый узел слева от Р). Установить В < — (ЫМК(Р). Если В = Л, присвоить ЕЫМК(Р) ~ — Ц н перейтн к шагу Сб. В противном случае, если В(В) ф О, присвоить Т <- Р, 3 «- й н 0 «- И. И, наконец, присвоить Р +- В и вернуться к шагу С2, С4. [Перемещение вправо.] Установить И +- М вЂ” ВАМК(Р) и й +- ВЫМЕ(Р). Если й = Л, присвоить ВЫМК(Р) +- Ц и перейти к шагу С5. В противном случае, если В(й) Р. О, присвоить Т +- Р, 3 +- й и 9 +- И.
И, наконец, присвоить Р «- В и вернуться к шагу С2. С5,(Вставка.] Установить ВАМК(9) <- 1,Ы.ХМК(9) +- В11МК(9) +- Л, В(Ц) «- О. СВ.(Корректировка факторов сбалансированности,] Установить М з- О. (Это действие позволяет восстановить предыдущее значение И,когда Р было равно Я; все поля йАМК установлены соответствующим образом,) Если И < ВАМК(3), присвоить В +- Р з- (ЫМК(3) и а «- — 1; в противном случае присвоить В +- Р з- В1.1МК(Я), а «- +1 и М +- И вЂ” ВАМК(3). Затем повторять глелующке действия, пока Р не станет равным Ц: если И < ВАМК(Р), установить В(Р) +- -1 и Р +- Ы.ХМК(Р); если М > ВАМК(Р), установить В(Р) +- +1, Н з- Н вЂ” ВАМК(Р) н Р <- ВЫМЕ(Р). (Если Н = ВАМК(Р), то Р = Ц и можно переходить к следующему шагу.) СТ. (Балансировка.] Здесь возможны несколько случаев.
!) Если В(Я) = О, установить В(3) < — а, Ы.|МК(НЕАО) «- ЕЫМК(НЕАО) + 1 н прекратить выполнение алгоритма. й) Если В(Б) = — а, установить В(Б) ° 0 и прекратить выполнение алгоритма. й1) Если В(Я) = а, то перейти к шагу С8 в случае, если В(й) = а, и к шагу С9, если В(й) = — а.
СВ, (Однократный поваров] Установить Р = В, ЫМК(а,Б) з- 51МК( — а,й), ЫМК( — а, В) «- Я, В(Я) з — В(й) +- О. Если а = +1, установить ВАМК(й) +- ВАМК(й) + ВАМК(3); если а = -1, установить ВАМК(3) <- ВАМК(Я) — ВАМК(й). Перейти к шагу С10. С9. (Двукратный поворот.] Выполнить шаг А9 (алгоритм А). Затем, если а = +1, установить ВАМК(й) +- ВАМК(В) — ВАМК(Р), ВАМК(Р) +- ВАМК(Р) +ВАМК(3); если а = -1, присвоитьВАМК(Р) +- ВАМК(Р)+ВАМК(й), азатем ВАМК(3) +- ВАМК(3)— ВАМК(Р). С10. (Последний штрих.] Если Я = ВЫМЕ(Т), присвоить 31.1МК(Т) +- Р, в противном случае — 111МК(Т) з- Р. ! «Удаление, конкатенация и другие операции.
Существует множество других операций над сбаланскрованными деревьями, которые поддерживают их сбалансированность, однако их алгоритмы слишком длинны для детального рассмотрения в этой книге. Здесь обсуждаются только общие ндеи, и заинтересованному читателю предоставляется возможность самостоятельно восстановить опущенные дешли (что не так трудно, как кажется на первый взгляд). Удаление при корректной постановке выполняется за 0(1оК Ю) шагов ]С.
С. Гозсег, "А Ягоду о( АУ1, Тгеев", Соодуеаг Аегсерасе Согр. герогг СЕВ-12158 (Арп1, 1965)]. Прежде всего, удаление произвольного узла сводится к простому удалению узла Р, поля Ы.ХМК(Р) или й(1МК(Р) которого равны Л, как в алгоритме 6.2.2П. Алгоритм к тому же должен быть изменен таким образом, чтобы он строил список указателей, определяющих путь к узлу Р: (16) (Рв,ао), (Рыаг), ..., (Рывин), где Ро -- НЕАО, ао = +1; ЫМК(а;,Р,) = Р+ы 0 < 1 < 1; Р~ = Р и Е1МК(ам Р~) = Л. Этот список при поиске вниз по дереву может быть помещен во вспомогательный стек. В процессеудаления узла Р устанавливается 1.1МК(а~ юР~,) ~- 1.1МК(-амР~) и следует откорректировать фактор сбалансированности узла Р~ ы Предположим, что мы должны откорректировать фактор сбалансированности узла Ры потому что уменьшилась высота поддерева аэ данного узла.
Для этого используется следующая процедура: если й = О, установить Ь(,1МК(НКАО) +- Ы,|МК(НКАО) — 1 и прекратить выполнение алгоритма, поскольку уменьшилась высота всего дерева. В противном случае рассмотрим фактор сбалансированности В(Рь). Возможны три варианта, приведенных ниже. 1) В(РА) = аю Установить В(РА) +- О, уменьшить й на 1 и повторить процедуру корректировки для нового значения А. Н) В(Рь) = О. Установить В(Рь) +- -аь и прекратить выполнение алгоритма.
Н1) В(Рь) = -аы Требуется балансировка! Ситуации, в которых требуется ребвлаисировка дерева, практически те же, что в алгоритме вставки; вернитесь к (1), где в роли А выступает узел Ры а в роли  — узел 1.1МК(-аь,Рь), принадлежащий ветви, проглпеополоокчюй той, в которой производится удаление. Отличие заключается в том„что узел В может быть сбалансированным. Это приводит к возникновению нового случая 3, который подобен случаю 1, но высота Д равна Ь + 1. В случаях 1 и 2 ребалансировка, как и в (2), означает, что мы уменьшаем высоту, устанавливая 1.1МК(аь юРь ь) в качестве корня (2), уменьшаем А на 1 и перезапускаем процедуру корректировки для нового значения А. В случае 3 выполняется однократный поворот, который оставляет факторы сбалансированности А и В ненулевыми без изменения общей высоты.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
