AOP_Tom3 (1021738), страница 120
Текст из файла (страница 120)
Интересно отметить тесную взаимосвязь между анализом сортировки путем вставки в дерево и анализом "быстрой сортировки", хотя, на первый взгляд, эти методы совершенно различны. При успешной вставке ьУ ключей в изначально пустое дерево мы выполняем то же среднее число сравнений ключей, что и в алгоритме 5.2.2() (за небольшими исключениями). Например, .в случае вставки в дерево каждый ключ сравнивается с Кь, затем каждый ключ, меньший, чем Кь, сравнивается с первым ключом, меньшим, чем Кь, и т. д.; в случае быстрой сортировки каждый ключ сравнивается с первым разделяющим элементом К, затем каждый ключ, меньший, чем К, сравнивается с некоторым элементомь меньшим, чем К, и т.
д. Среднее количество сравнений, необходимое в обоих случаях, равно ЛгС~. — Ль (впрочем, в алгоритме 5.2.2() на самом деле выполняется несколько дополнительных сравнений для ускорения внутреннего цикла). Удаление. Иногда приходится заставлять компьютер забыть одну из записей таблицы. ь(ы можем легко удалить узел, палс ШМК или Ы.1МК которого равно Л; однако, если оба поддерева не пусты, мы должны проделать некоторые специальные действия, так как ссылка не мажет указывать на два места одновременно.
Рассмотрим еще раз рис. 10. Как удалить из дерева корневой узел, САРН1СОНМ? Одно нз решений состоит в удалении следующего по алфавиту узда, ссылка 111МК которого пуста, и его вставке на место узла, который надо удалить. Например, на рис. 10 мы можем удалить СЕМ1М1, а затем заменить САРН1СОНМ значением СЕМ1М1. Это позволит сохранить порядок элементов таблицы. В приведенном далее алгоритме содержится детальное описание такого процесса. Алгоритм 1) (Удалеььие иг дерева (Тле деьегьап)]. Пусть Ц вЂ” переменная, указывающая на узел дерева поиска, представленного, как в алгоритме Т.
Алгоритм предназначен для удаления этого узла, причем дерево останется бинарным деревом поиска. (На практике имеем либо Ц = НООТ,либо Ц = ЕЕТМК(Р),либо Ц = НЕ1МК(Р) для некоторого узла дерева. Алгоритм изменяет значение Ц с учетом проведенного удаления.) Ш.[Пуста ли ссылка НЕ1МК?] Установить Т ь — Ц. Если Н1.1МК(Т) = Л, установить Ц + — ЕЕ1МК(Т) и перейти к шагу 1)4, (Например, если Ц = НЕ1МК(Р) для некоторого Р,мы можем присвоить НЕ1МК(Р) е- Е11МК(Т).) Х)2.[Поиск преемника.] Установить Н ь — НЕ1МК(Т). Если 1Л.1МК(Н) = Л, присвоить ЕЕ1МК(Н) +- ЕЕ1МК(Т), Ц +- Н и перейти к шагу ))4.
1)З. [Поиск пустой ссылки1.11МК,] Устанавить 3 ь- Ы.1МК(Н). Затем, если ШМК(3) ф Л, присвоить Н ь — 3 и повторять этот шаг до тех пор, пока не будет получено ~Л.1МК(3) = Л. (Теперь 3 будет равно Цэ, следующему за Ц элементу при симметричном обходе.) И, наконец, установить 1.1.1МК(Б) +- ~Л.1МК(Т), ШМК(Н) < — Ы.1МК(Я), НЕ1МК(3) ь — Н11МК(Т), Ц +- 3. 1)4.
[Освобождение узла.] Выполнить АгАП, ~ Т, т. е. вернуть удаленный узел в пул свободной памяти. ! Читатель может проверить работоспособность данного алгоритма, удаляя узлы АЦОАН103ь САМСЕН и САРН1СОНМ на рис. 10; каждый из этих случаев имеет свои особенности. Особо придирчивый читатель, конечно, обратит внимание на то, что случай НЕ1МК (Т) ф Л, ЕЕ1МК (Т) = Л отдельно не выделен. Мы отложили обсуждение этого специального случая "на потом", поскольку в приведенном виде алгоритм обладает некоторыми интересными свойствами.
Алгоритм В представляется весьма несимметричным, и создаетсн впечатление, что длинная цепь удалений разбалансирует дерево (и все оценки эффективности работы при этом потеряют силу). Однако "все не так, как на самом деле", и вырождения не будет. Теорема Н (Т.
Н. Хнббард (Т. 1э. Н1ЬЬагб), 1962.) После удаления элемента нз случайного дерева по алгоритму Р дерево остается случайным. (Читателям, которым математика не доставляет никакого удовольствия, настоятельно рекомендуется пропустить все до формулы (10).) Эта формулировка, естественно, несколько туманна.
Сформулируем теорему более строго. Пусть Т представляет собой дерево из и элементов и пусть Р(Т) — вероятность появления Т, если его ключи вставляются в случайном порндке согласно алгоритму Т. Одни деревья более вероятны, чем другие. Пусть Я(Т) — вероятность того, что после вставки случайным образом с помощью алгоритма Т и+ 1 элементов и удаления любого из них (выбранного наудачу) по алгоритму Р получится дерево Т. При вычислении Р(Т) предполагается, что все и! перестановок ключей равновероятны; при вычислении Я(Т) предполагается равновероятность (и+ 1)! (и+ 1) перестановок ключей и выбора удаляемого ключа. Теорема гласит, что для всех Т Р(Т) = э;>(Т).
Доказапэельспэео. По условию теоремы равновероятны не деревья, а перестановки, поэтому доказывать теорему мы будем, рассматривая в качестве случайных объектов переспэаноеки. Сначала определим удаление из перестановки, а затем докажем, что случайный элемент, удаленный из случайной перестановки, оставляет перестановку случайной. Пусть оэ аэ, .. а„э.э — перестановка множества (1, 2,, и+1); мы хотим определить операцию удаления аь которая даст в результате перестановку Ьэ Ьт... Ь„ множества (1, 2,..., и).
Эта операция должна соответствовать алгоритмам Т и В, так что, если мы начнем с дерева, сконструированного последовательностью вставок аэ,аэ,...,а„э.э, и удалим ао перенумеровав затем ключи от 1 до и, получится дерево, которое может быть построено последовательностькэ вставок Ьэ Ьэ... Ь„. Такую операцию удаления можно легко определить.
Возможны два случая. Случай 1. а, = и+ 1 или а;+ 1 = а для некоторого у ( 1. (Это соответствует условию иь1Щ(а;) = Л.) Удаляем а; из последовательности и вычитаем единицу из каждого .элемента, большего, чем а,. Случай й. а; + 1 = а для некоторого у > (. Заменим а; элементом ау, удалим ау из его первоначального положения и вычтем единицу из каждого элемента, большего, чем а,. Рассмотрим, например, перестановку 4 6 1 3 5 2.
Если пометить элемент, который должен быть удален, кружком, получим 0461352 45132 4610352 35142 4О61352 41352 4613®2 45132 4 6®3 5 2 = 3 5 1 2 4 4 6 1 3 ба= 3 5 1 2 4 Поскольку имеется (и + 1)! (и + 1) возможных операций удаления, теорема будет доказана, если мы сможем показать, что каждая перестановка (1, 2,..., п) является результатом в точности (и+ 1) удалений. ПУсть Ь~ Ьэ... ܄— пеРестановка множества (1, 2,..., и), Мы опРеделим (и+1)з удалений, по одному для каждой пары ю', ~' (1 < 1, у < и + 1).
Удаление для 1 < 1 таково: Ь',... Ь',, ® Ь,'~ь, ... Ь', (Ь,+1) Ь', ... Ь'„. (7) Здесь и далее Ь' означает либо Ьы либо Ьь + 1, в зависимости от того, является ли Ьь меньше, чем помеченный элемент, Такое удаление соответствует случаю 2. Удаление для ю' > / таково: Ь,... Ь',,ОЬ, Ь',....Ь'„; (8) оно соответствует случаю 1. И наконец, если 1 = 1, мы имеем другой случай 1, а именно Ь',... Ь',,~+)Ь',...Ь'„.
В качестве примера примем и = 4 и рассмотрим 25 удалений, приводящих к перестановке 3 1 4 2. 1'=1 (5)3 1 4 2 4®1 5 2 4 1О35 2 4 1 5О32 4 1 5 2(3) у =2 Д34 1 5 2 ЗО51 4 2 4 2(О5 3 4 2 5®3 4 2 5 ЗО1 у =3 О31 4 5 2 4О12 5 3 3 1Д54 2 3 1 5О42 3 1 5 2Д4 1=4 О31 542 4О1523 31(4)52 314®2 4153Д2 1=5 ОЗ152«®532 31О42 5 415О23 3142О5 Помеченный элемент всегда находится в 1-й позиции; для фиксированного 1 мы строили и + 1 различных удалений, по одному для каждого /ь Таким образом, для каждой перестановки Ь| Ьэ...
Ь„построено (и + 1) различных удалений. Так как возможны только (и+ 1)~п! удалений, мы должны найти их все. 3 Доказательство теоремы Н не только описывает результат удалений, но также помогает проанализировать среднее время удаления. В упр. 12 показано, что при удалении случайного элемента из случайной таблицы шаг П2 будет выполняться меньше чем в половине случаев. Теперь рассмотрим, как часто выполняется цикл на шаге ПЗ.
Предположим, что мы удаляем узел на уровне 1 и внешний узел, при симметричном обходе следующий непосредственно за ним, находится на уровне Ь. Например, при удалении узла САРКХСОКИ на рис. 10 1 = 0 и /с = 3, так как узел Д4 находится на уровне 3. Если Ь = 1+ 1, то на шаге 01 81.1ИК(Т) = Л; если и > 1+ 1, то на шаге ПЗ мы выполним присвоение Я е- 1.1.1ИК(й) ровно Ь вЂ” 1 — 2 раэ.
Среднее значение 1 равно (длина внутреннего пути)/Х; среднее значение я (ллнна внешнего пути — расстояние до крайнего слева внешнего узла)/Ж. Расстояние до крайнего слева внешнего узла равно числу лево-правых минимумов вставляемой последовательности, так что среднее значение этой величины согласно анализу в разделе 1.2.10 составляет Нгг. Поскольку длина внешнего пути превышает длину внутреннего пути на 2Х, среднее значение /с — 1 — 2 равно — Нч/Х.
Добавляя к этому среднему значению число случаев, когда й — ! — 2 равно — 1, мы получим, что при случайном удалении в среднем операция Я+- ((ТИК(й) на шаге РЗ выполняется только (10) раз. Это успокаивает, так как в наихудшем случае> как показано в упр. 11, удаления выполняются весьма медленно. Хотя теорема Н вполне строга и точна, в указанном виде ее нельзя применить к последовательности удалений, следующих за вставками.
После удалений форма дерева остается случайной, однако относительное распределение значений в данной форме дерева может оказаться измененным, и это может привести к тому, что первая же вставка после удаления уничгпвжиш свойство случайности формы. Этот поразительный факт, впервые обнаруженный Гарри Кноттом (Сагу Кпсс() в 1972 году, вам придется принять на веру (см. упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
