Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 18
Текст из файла (страница 18)
Доказать это утверждение на удивление легко. Предположим, что каждая из Ж! возможных перестановок Х ключей с равной вероятностью используется для построения дерева путем последовательных вставок. Число сравнений, необходимых для поиска ключа, ровно на одно больше числа сравнений, необходимых для его вставки в дерево. Таким образом, если Ск — среднее количество сравнений при успешном поиске, а С~, — при неудачном, то С' + С,' + " + С' С„= 1+ (2) Однако согласно соотношению между длинами внутреннего н внешнего путей (6.2.1— (2)) с = (1+ — ',)с' -1. Объединяя (3) и (2), получим (3) (л'+ цс' = гл" + со+ с', + ° +си,. Это рекуррентное соотношение легко решается: вычтя следующее равенство л'с',, =2(л' — ц+с'+с, '+ - +с' из предыдущего, мы получим (Н+ ЦСй — Л'С'т, = 2+С' Так как С', = О, то следовательно, С~д = С~и 1 + 2/(Л' + ц.
С,', = гик„- г. (5) Применив (3) и выполнив некоторые упрощения, получим требуемый результат: Сн =2(1+ -)Н,, -3. 15 л.) (6) В упр. 6-8 приводится более детальная информация — можно определить не только средние значения Сл и С~, но и их точные распределения вероятностей. Сортировка путем вставки в дерево. Алгоритм Т был разработан для поиска, однако он может применяться и в качестве основы алгоритма внутренней сортировки; его можно рассматривать как естественное обобщение вставки в список — алгоритма 5.2.11.. Если этот алгоритм будет корректно реализован, то среднее время его работы лишь незначительно превысит время работы лучших алгоритмов, обсуждавшихся в главе 5. После того как дерево построено, остается только симметрично его обойти (алгоритм 2.3.1Т): так мы получим записи в рассортированном виде.
Тем не менее следует предпринять определенные меры предосторожности— требуются некоторые отличия на шаге Т2 при К = КЕУ(Р) в связи с тем, что нашей целью является не поиск, а сортировка. Одно из возможных решений — считать, что К = КЕ1'(Р) эквивалентно К > КЕ1(Р). Сортировка, при этом будет вполне корректна (отметим, что записи с одинаковыми ключами необязательно должны находиться в смежных узлах — важно„чтобы они последовательно встречались при симметричном обходе дерева). Однако при нюзичин большого количества повторяющихся ключей этот метод может дать плохо сбалансированное дерево, и процесс сортировки окажется замедленным. Еще одним решением может служить хранение списка записей с одним я тем же ключом для каждого из узлов.
В этом случае потребуется дополнительное поле ссылок, однако при большом числе повторяющихся ключей такая сортировка окажется более быстрой. Таким образом, применение алгоритма Т только для сортировки является неплохим, хотя и не лучшим, решением. Однако этот алгоритм настоятельно рекомендуется использовать в случае комбинирования в одном приложении как поиска, так и сортировки. Интересно отметить тесную взаимосвязь между анализом сортировки путем вставки в дерево и анализом "быстрой сортировки", хотя, на первый взгляд.
эти методы совершенно различны. При успешной вставке Л ключей в изначально пустое дерево мы выполняем то же среднее число сравнений ключей, что и в алгоритме 5.2,2() (за небольшими исключениями). Например, в случае вставки в дерево каждый ключ сравнивается с Км затем каждый ключ, меньший, чем Кы сравнивается с первым ключом, меньшим, чем Км и т. дл в случае быстрой сортировки каждый ключ сравнивается с первым разделяющим элементом К, затем каждый ключ, меньший, чем К, сравнивается с некоторым элементом, меныпнм, чем К., и т, д. Среднее количество сравнений, необходимое в обоих случаях, равно ХСя — Л' (впрочем, в алгоритме 5.2.2(е на самом деле выполняется несколько дополннтельньгх сравнений для ускорения внутреннего цикла),.
Удаление. Иногда приходится заставлять компьютер забыть одну нз записей таблицы. Мы можем легко удалить узел, поле ГЫМК или ВЫМК которого равно Л; однако, если оба полдерева не пусты, мы должны проделать некоторые специальные действия, так как ссылка не может указывать на два места одновременно. Рассмотрим еще раз рис. 10. 1(ак удалить из дерева корневой узел, САРВ1СОВМТ Одно из решений состоит в удалении следующего по алфавиту узла, ссылка 1ЫМК которого пуста, н его вставке на место узла, который надо удалить.
Например, на рис, 10 мы можем удалить ОЕМ1М1, а затем заменить САРВ1СОВМ значением ОЕМХМ1. Это позволит сохранить порядок элементов таблицы. В приведенном далее алгоритме содержится детальное описание такого процесса. Алгоритм 1) (Удаление иа дерева ('7)ее де(е(юп)), Пусть Ц вЂ” переменная, указывающая на узел дерева поиска, представленного, как в алгоритме Т. Алгоритм предназначен для удаления этого узла, причем дерево останется бинарным деревом поиска.
(На практике имеем либо Ц = ВООТ, либо Ц = 1ЫМК(Р), либо Ц ьз В1.1МК(Р) для некоторого узла дерева. Алгоритм изменяет значение Ц с учетом проведенного удаления.) 1)1. [()уста ли ссылка ВЫМКТ] Установить Т +- Ц. Если ВЫМК(Т) = Л, установить Ц ( — (.ЫМК(Т) и перейтн к шагу 04. (Например, если Ц = ВЫМК(Р) для некоторого Р, мы можем присвоить ВЕ1МК(Р) +- ШМК(Т).) 1)2. [Поиск преемника.] Установить В с- В1.1МК(Т), Если 1Л 1МК(В) = Л, присвоить (.ЫМК(В) (- 1ЫМК(Т), Ц +- В и перейти к шагу П4.
1)3. [Поиск пустой ссылки ШМК ] Установить Б +- (.ЫМК(В). Затем, если 1Д 1МК(Б) ф Л, присвоить В <- Б и повторять этот шаг до тех пор, пока не будет получено ГЫМК(Б) = Л. (Теперь Б будет равно Це, следующему за Ц элементу при симметричном обходе.) И, наконец, установить ШМК(Б) +- ШМК(Т), 1.1.1МК(В) +- ВЫМК(Б), ВЫМК(Б) С- ВЫМК(Т), Ц <- Б. 1)4, [Освобождение узла.] Выполнить АРАП. ч= Т, т. е. вернуть удаленный узел в пул свободной памяти. $ Читатель может проверить работоспособность данного алгоритма, удаляя узлы АЦОАВ10Б, САМСЕВ и САРВ1СОВМ на рис.
10; каждый из этих случаев имеет свои особенности. Особо придирчивый читатель, конечно, обратит внимание на то, что случай ВЫМК(Т) ~ Л, 1Л.1МК(Х) = Л отдельно не выделен. М(ы отложили обсуждение этого специального случая "на потом", поскольку в приведенном виде алгоритм обладает некоторыми интересными свойствами. Алгоритм Р представляется весьма несимметричным, н создается впечатление, что длинная цепь удалений разбалансирует дерево (н все оценки эффективности работы при этом потеряют сиду). Однако "все не так, как на самом деле", и выро. ждения не будет.
Теорема Н (Т. Н. Хиббард (Т. Х. Н)ЬЬегд), 1962.) После удаления элемента яз случайного дерева по алгоритму Р дерево остается случайным. [Читателям, которым математика не доставляет никакого удовольствия, настоятельно рекомендуется пропустить все до формулы (10).[ Эта формулировка, естественно, несколько туманна. Сформулируем теорему более строго. Пусть Т представляет собой дерево из и элементов и пусть Р(Т) — вероятность появления Т, если его ключи вставляются в случайном порядке согласно алгоритму Т.
Одни деревья более вероятны, чем другие. Пусть сг(Т) — вероятность того, что после вставки случайным образом с помощью алгоритма Т и+ 1 элементов и удаления любого из них (выбранного наудачу) по алгоритму Р получится дерево Т. При вычислении Р(Т) предполагается, что все и! перестановок ключей равновероятны; при вычислении Я(Т) предполагается равновероятность (и+ 1)! (и+ 1) перестановок ключей и выбора удаляемого ключа. Теорема гласит, что для всех Т Р(Т) = Я(Т). Докаэагпельстпео.
По условию теоремы равновероятны не деревья, а перестановки, поэтому доказывать теорему мы будем, рассматривая в качестве случайных объектов перестпаноеки. Сначала определим удаление из перестановки, а затем докажем, что случайный элемент, удаленный яз случайной перестановки, оставляет перестановку слу чайной. Пусть а~ ат...
а„*1 — перестановка множества (1, 2,..., и+1); мы хотим определить операцюо удаления аь которая даст в результате перестановку Ь| Ьт...Ь„ множества (1, 2,..., и). Эта операция должна соответствовать алгоритмам Т и Р, так что, если мы начнем с дерева, сконструированного последовательностью вставок амат,...,а„.~м н удалим аь перенумеровав затем ключи от 1 до и, получится дерево, которое может быть построено последовательностью вставок Ь1 Ьэ... Ь„.
Такую операцию удаления можно легко определить. Возможны два случая. Случай 1. а~ = и + 1 нли а; + 1 = а для некоторого у' < 1. (Это соответствует условию 31,1ИК(а,) = Л.) Ъдаляем а; из последовательности и вычитаем единицу из каждого элемента, большего, чем аь Случай й. а; + 1 = а для некоторого у > 1. Заменим а; элементом а, удалим а из его первоначального положения и вычтем единицу из каждого элемента, большего, чем а;.
Рассмотрим, например, перестановку 4 6 1 3 5 2. Если пометить элемент, который должен быть удален, кружком, получим С4)6 1 3 5 2 = 4 5 1 3 2 4 6 1С3)5 2 = 3 5 1 4 2 4Д61 3 5 2 = 4 1 3 5 2 4 б 1 3®2 = 4 5 1 3 2. 4 6(,'()3 5 2 м 3 5 1 2 4 4 6 1 3 5С2)~ 3 5 1 2 4 Поскольку имеется (и + 1)! (и + 1) возможных операций удаления, теорема будет доказана, если мы сможем показать, что каждая перестановка (1, 2,..., и) является результатом в точности (и + 1)э удалений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
