Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[83]

больше числа сравнений, выполненных при добавлении этого элемента. Почему?

13.3-3 Набор из га чисел можно отсортировать, сначала добавив их один за другим в двоичное дерево поиска (с помощью процедуры Tree-Insert), а потом обойти дерево с помощью процедуры Inorder-Tree-Walk. Найдите время работы такого алгоритма в худшем и в лучшем случае.

13.3-4 Покажите, что, если вершина двоичного дерева поиска имеет двоих детей, то следующая за ней вершина не имеет левого ребёнка, а предшествующая ей вершина - правого.

13.3-5 Предположим, что указатель на вершину у хранится в какой-то внешней структуре данных и что предшествующая у вершина дерева удаляется с помощью процедуры Tree-Delete. Какие при этом могут возникнуть проблемы? Как можно изменить Tree-Delete, чтобы этих проблем избежать?

13.3-6 Коммутируют ли операции удаления двух вершин? Другими словами, получим ли мы одинаковые деревья, если в одном случае удалим сначала ж, а потом у, а в другом - наоборот? Объясните свой ответ.

13.3-7 Если у z двое детей, мы можем использовать в Tree-Delete не следующий за z элемент, а предыдущий. Можно надеяться, что справедливый подход, который в половине случаев выбирает предыдущий, а в половине - следующий элемент, будет приводить к лучше сбалансированному дереву. Как изменить текст процедуры, чтобы реализовать такой подход?

★ 13.4 Случайные двоичные деревья поиска

Как мы видели, основные операции с двоичными деревьями поиска требуют времени 0(h), где h - высота дерева. Поэтому важно понять, какова высота «типичного» дерева. Для этого необходимо принять какие-то статистические предположения о распределении ключей и последовательности выполняемых операций.

К сожалению, в общем случае ситуация трудна для анализа, и мы будем рассматривать лишь деревья, полученные добавлением вершин (без удалений). Определим случайное двоичное дерево (randomly built search tree) из га различных ключей как дерево, получающееся из пустого дерева добавлением этих ключей в случайном порядке (все га! перестановок считаем равновероятными). (Как


видно из упр. 13.4-2, это не означает, что все двоичные деревья равновероятны, поскольку разные порядки добавления могут приводить к одному и тому же дереву.) В этом разделе мы докажем, что математическое ожидание высоты случайного дерева из п ключей есть 0(lg п).

Посмотрим, как связана структура дерева с порядком добавления ключей.

Лемма 13.3. Пусть Т - дерево, получающееся после добавления п различных ключей к\, к2, , кп (в указанном порядке) к изначально пустому дереву. Тогда к{ является предком kj в Т тогда и только тогда, когда г < j, и при этом

ki = min{ki : 1 / г и k\ > kj}

(ключ ki больше kj и их не разделяет ни один ключ среди к\,..., ki) или

ki = max{ki : 1 / г и к\ < kj}

(ключ ki меньше kj и их не разделяет ни один ключ среди к\,... , ki)

Доказательство. =>: Предположим, что ki является предком kj. Очевидно, i < j (потомок появляется в дереве позже предка). Рассмотрим дерево Ti, которое получается после добавления ключей k\,k2, , ki. Путь в Ti от корня до ki тот же, что и путь в Г от корня до ki. Таким образом, если бы ключ kj был добавлен в Гг-, он стал бы правым или левым ребёнком ki. Следовательно (см. упр. 13.2-6), ki является либо наименьшим среди тех ключей из k\,k2, , ki, которые больше kj, либо наибольшим среди ключей из того же набора, меньших kj.

-ч=: Предположим, что ki является наименьшим среди тех ключей k\,ki, ,ki, которые больше kj. (Другой случай симметричен.) Что будет происходить при помещении ключа kj в дерево? Сравнение kj с ключами на пути от корня к ki даст те же результаты, что и для ki. Следовательно, мы пройдём путь от корня до ki, так что kj станет потомком ki.

Лемма доказана.□

Теперь можно понять, как зависит глубина каждого ключа от перестановки на входе.

Следствие 13.4. Пусть Г - дерево, полученное из пустого добавлением п различных ключей k\,ki, ,kn (в указанном порядке). Для каждого ключа kj (при всех 1 j1 п) рассмотрим множества

Gj = {ki : 1 . i < j н ki > ki > kj при всех / < г, для которых k\> к

и

Lj = {ki : 1 . i < j н ki < ki < kj при всех / < г, для которых к\ < kj


Тогда ключи на пути из корня в kj - в точности Gj U Lj, а глубина kj в дереве Г равна

На рисунке 13.5 изображены множества Gj и Lj. Их построение можно объяснить так. Считая для наглядности ключи числами, будем отмечать их на числовой оси: сначала к\, потом к2 и так далее вплоть до kj. В каждый момент на оси отмечено несколько точек ki,...,kt (где 1 t j - 1). Посмотрим, какая из этих точек будет ближайшей справа к будущему положению ключа kj. Множество всех таких ближайших точек (для всех моментов времени t = 1,2,... ,j - 1) и есть Gj. Ближайшие слева точки образуют множество Lj.

Наша цель - оценить сверху количество элементов в Gj и Lj, поскольку сумма этих количеств равна глубине ключа kj. Фиксируем некоторое j. Число элементов в Gj будет случайной величиной, зависящей от порядка ключей на входе (имеет значение лишь порядок на ключах к\,..., kj). Мы хотим оценить это число сверху (доказать, что вероятность события «это число велико» мала).

Следующий факт из теории вероятностей играет центральную роль при этой оценке.

Лемма 13.5. Пусть ki,k2,...,kn есть случайная перестановка п различных чисел. Для каждого г от 1 до п рассмотрим минимальный элемент в множестве {к\, к2, , к{\. Множество всех таких элементов назовём S:

Тогда P{\S\ (/3 + 1)Нп} 1/га2, где Нп - п-я частичная сумма гармонического ряда, а (3 рй 4,32 - корень уравнения (In (3 - 1)(3 = 2.

Доказательство. Будем следить за тем, как меняется множество {ki,..., ki} с ростом г. На г-м шаге к нему добавляется элемент к{, причём он с равными вероятностями может оказаться первым, вторым,..., г-м по величине (каждой из этих возможностей соответствует равная доля входных перестановок). Таким образом, вероятность увеличения множества S на г-м шаге равна 1/г при любом порядке среди ключей ki,..., k{ i, так что для разных г эти события независимы.

Мы приходим к ситуации, описанной в теореме 6.6: имеется последовательность независимых испытаний, вероятность успеха в г-м испытании равна 1/г. Нам надо оценить число успехов.

Математическое ожидание этого числа равно 1 + 1/2 + .. .+ 1/г = Hi = In г+ 0(1), см. формулу (3.5) и задачу 6-2. Нам надо оценить вероятность того, что число успехов больше своего математического ожидания в /3 + 1 раз.

•,Г) = 0, +

S = {ki : 1 г га и к\ > ki для всех I < г}.



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]