1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 28
Текст из файла (страница 28)
Например, допустим, что последовательность элементов, которые надлежит добавить, оказалась упорядоченной (в порядке возрастания). Тогда дерево поиска будет просто цепью правых сыновей. Но если вставляется и случайных элементов, то, как показывает следующая теорема, вставка потребует время 0(и !Од и). Теорема 4.4, Среднее число сравнений, необходимых для вставки и случайных элементов в дерево двоичного поиска, пустое вначале, равно 0(и !Ой и) для и Р1. ГЛ, А СТРУКТУРЫ ДАННЫХ ДЛЯ ЗАДАЧ С МНОЖЕСТВАМИ Т(п)=-„~~' (и — 1+Т(! — 1)+Т(п — !)), (4.1) У=! или, с учетом простых алгебраических преобразований, Т()= -1+ЖТ()) 4 О (4.2) Способом, описанным в равд.
3.5, можно показать, что Т(п) =Ьг!оял, где й=!п 4=1,39. Таким образом, в среднем на вставку и элементов в дерево двоичного поиска тратится 0(п 1ои а) сравнений. (З Итак, методами этого раздела можно выполнить случайную последовательность из п операций ВСТАВИТЬ, УДАЛИТЬ, ПРИНАДЛЕЖАТЪ и М1Ы за среднее время 0(д !ои а). Выполнение в худшем случае занимает квадратичное время. Однако даже это худшее время можно улучшить до 0(д 1оя п) с помощью одной из схем сбалансированных деревьев (2-3-деревьев, АВЛ-деревьев или деревьев с ограниченной балансировкой), которые обсуждаются в равд. 4.9 и упр.
4.30 — 4.37, Д о к а з а тел ь с т в о. Пусть Т(п) — число сравнений, производимых между элементами последовательности ан а„..., ДА при построении дерева двоичного поиска, Т(0)=0. Пусть Ь„Ь„... ..., ܄— та же последовательность в порядке возрастания. Если а„а„..., а„— случайная последовательность элементов, то а, с равной вероятностью совпадает с Ьт для любого!, 1:Я =а. Элемент а, становится корнем дерева двоичного поиска, и в окончательном дереве ! — 1 элементов Ь„ Ь„ ..., Ь , будут находиться в левом поддереве корня и и — 1 элементов Ьг+„ Ьу+„ ..., ܄— в правом поддереве.
Подсчитаем среднее число сравнений, необходимых для вставки элементов Ь„ Ь„ ..., Ь4 4 в дерево. Каждый из этих элементов когда-нибудь сравнивается с корнем, и это дает ! — 1 сравнений с корнем. Затем по индукции получаем, что еще потребуется Т(! — !) сравнений, чтобы вставить Ь„, Ь„..., Ьг, в левое поддерево. Итак, необходимо ) — 1+ТЦ вЂ” 1) сравнений, чтобы вставить Ь„Ь„... ..., ЬЕ, в дерево двоичного поиска. Аналогично п — 1+ Т (и — !) сравнений потребуется, чтобы вставить в дерево элементы Ьу н Ь|+„..., Ь„. Поскольку ! с равной вероятностью принимает любое значение от!дон, то св. оптимлльиыа дававья двоичного поиски 4.в. ОПТИМАЛЬНЫЕ ДЕРЕВЬЯ ДВОИЧНОГО ПОИСНА В равд. 4.3 по данному множеству 3=(а„аь..., а„), являющемуся подмножеством некоторого большого универсального множества У, строилась структура данных, позволяющая эффективно выполнить последовательность о, составленную только из операций ПРИНАДЛЕЖАТЬ.
Рассмотрим снова эту задачу, но теперь предположим, что кроме множества 5 задается для каждого а Е У вероятность появления в о операции ПРИНАДЛЕЖАТЬ(а, 5). Теперь нам хотелось бы построить дерево двоичного поиска для 5 так, чтобы последовательность о операций ПРИНАДЛЕЖАТЬ можно было выполнить в префиксном режиме с наименьшим средним числом сравнений. Пусть а„ а„ ..., а„ вЂ” элементы множества 5 в порядке возра стаиия н р; — вероятность появления в аоперации ПРИНАДЛЕЖАТЬ(ап о). Пусть де — вероятность появления в а операции ПРИНАДЛЕЖАТЬ(а, 5) для некоторого а(а„а д, — вероятность появления в о операции ПРИНАДЛЕЖАТЬ(а, 5) для некоторого а, а,(а ав+т. Наконец, пусть д„— вероятность появления в а операции ПРИНАДЛЕЖАТЬ (а, 5) для некоторого а) а„.
Для определения стоимости дерева двоичного поиска удобно добавить к нему и+1 фиктивных листьев, чтобы отразить элементы из У вЂ” 5. й(ы будем обозначать эти листья числами О, 1, ..., и. На рис. 4.7 показано дерево двоичного поиска, изображенное на рис, 4.4, с добавленными фиктивными листьями. Например, лист с меткой 3 представляет те элементы а, для которых епе((а( (И. Рис. 4.7. Дерево двоичного поиска с добавленными листьями.
44$ гл. ь стяяктягы длниых для злдлч с множяствлми Нам надо определить стоимость дерева двоичного поиска. Если элемент а равен метке ((о) некоторого узла о, то число узлов, посещенных во время выполнения операции ПРИНАДЛЕЖАТЬ(а, 3), на единицу больше глубины узла о. Если а (Я и а,(а<а1+„то число узлов, посещенных при выполнении операции ПРИНАДЛЕЖАТЬ (а, Я), равно глубине фиктивного листа Ь Поэтому стоимость дерева двоичного поиска можно определить как Л а ~ р~ (ГЛУБИНА (а;) + !) -(- ~ д~ ГЛУБИНА (!). у ! ~ о Теперь, если у нас есть дерево двоичного поиска Т, обладакхцее наименьшей стоимостью, мы можем выполнить последовательность операций ПРИНАДЛЕЖАТЬ с наименьшим средним числом посещений узлов, просто применив для выполнения каждой операции ПРИНАДЛЕЖАТЬ алгоритм 4.! на Т.
Если даны числа р~ и дь то как найти дерево наименьшей стоимости? Подход "разделяй н властвуй" предлагает определить элемент ам который надо поставить в корень. Это разбило бы данную задачу на две подзадачи: построение левого и правого поддеревьев. Однако, похоже, нет легкого пути определения корня без решения всей задачи. Поэтому придется решать йл подзадач; по две для каждого возможного корня. Это естественно приводит к решению с помощью динамического программирования. Для 0(!()(п обозначим через Тц дерево наименьшей стоимости для подмножества (а~+о а; „..., а ).
Пусть сы — стоимость дерева Тнь а г г — его корень. Вес вм дерева Тм определяется как Чг+ (р~~г+Ч+1)+ .+ (Рт+ЧЭ Дерево Т,> состоит из корня аь, левого поддерева Т, ь, (т. е. дерева наименьшей стоимости для (а~+о а~+в..., а„,)) и правого поддерева Т„т (т. е. дерева наименьшей стоимости для (ах+ ь а„~„... ..., а )); см. рис. 4.8. Если (=й — (, то нет левого поддерева, а при й=!' нет правого поддерева.
Для удобства мы будем трактовать Тп как пустое дерево. Вес шм дерева Тм равен дь а его стоимость см равна О. Рис. 4.8, поадерево тп, 142 ев. оптимальные днннвья двоичного поискл В Тпь 1~!', глубина каждого узла в левом и правом поддеревьях на единйцу больше глубины того же узла в Т, „, или Т»р Поэтому стоимость сп дерева Тм можно выразить так: с; =ш, „, +р»+ш»!+се», +с»~ —— вы+с, »„,+с»р Следует брать здесь то значение й, которое минимизирует сумму с~ »,+с д Поэтому для нахождения оптимального дерева Ты вычисляют для каждого й, !(Й(1, стоимость дерева с корнем а», левым поддеревом Т; „, и правым поддеревом Т»;, а затем выбирают дерево наименьшей стоимости.
Приведем соответствующий алгоритм. Алгоритм 4.2. Построение оптимального дерева двоичного поиска Вход, Множество В вида (а„а„..., а„), где а,~а»(... (а„. Известны также вероятности д„чь .. „д„и ры р»,, р, где )К г ~ э е ь 1я=!(и,— вероятность выполнения операции ПРИНАДЛЕАТЬ(а, В) для а;(а(а1еы д,— вероятность выполнения операции ПРИНАДЛЕЖАТЬ(а, В) для аСаы д„— вероятность выполнения операции ПРИНАДЛЕЖАТЬ (а, В) для а а„, а рь 1<!<и,— вероятность выполнения операции ПРИНАДЛЕЖАТЬ(а„Я). Выход.
Дерево двоичного поиска для 3, обладающее наименьшей стоимостью. ЬеК!п 1. 1ог ! — 0 нп1П и е!о Ьея!п 2. Ф 4' 3. си -0 еп»1; 4. 1ог ! -1 ип1П и до 5. 1ог ! — 0 нп1П и — ! до ЬеК)п 6. ! -!+1; 7. сны ш',у-»+Ру+Ч!! о. пустыи — значение й, ! ( Й н 1, для которого сумма с, »,+с»~ минимальна; 9. 10. г! -а, епс! епд Рнс. 4хи Алторнтм для нахождения корней оптимальных поддеревьев. 443 гл. с стрнктяры данных для задач с миожяствдми ргосее)цге ПОСТРДЕРЕВА(1, 1): Ьеп(п образовать корень оп дерева ТО41 пометить оп меткой г01 пусть «1 †инде числа ггу (т.
е. г1 * а ); И 1' < пт — 1 (Ьеп сделать ПОСТРДЕРЕВА (1, еп — 1) левым поддеревом узла о01 11 ел</ (Ьеп сделать ПОСТРДЕРЕВА(пе, 1) правым подде- ревом узла оп епе) Рис. 4.10. Пропедура ддя построения оптииадьиого дерева двоичного поиска.
Метод. 1. Для 0(1(~(п вычисляются г» и с11 в порядке возрастания разности ) — 1 с помощью алгоритма динамического программирования, приведенного на рис. 4.9. 2. После вычисления всех гм вызывается процедура ПОСТРДЕРЕВА(0, и) для рекурсивного построения оптимального дерева для Те„. Процедура ПОСТРДЕРЕВА приведена на рис. 4.10. П О 2 3 4 С=/- 1' О Рнс. 4.11, Значения в;у, с1у н ггу. 144 Еб. ОПТИМАЛЬНЫЕ ДЕРЕВЬЯ ДВОИЧНОГО ПОИСКА Рис.
АЛ2, Дерево ивимееьшей стоимости. Пример 4.6. Рассмотрим четыре элемента а,(а,<а,<а, с д,= =1/8 дт=З/1б Г/т=т/п=р4=1/16 и рт=1/4, рв=Н8, рт=рв=106, На Рис. 4.11 даны значениЯ вц, Г» и соь вычисленные алгоРитмом, приведенным на рис. 4.9. Для удобства записи значения шм и с,~ в этой таблице были умножены на 16. НапРимеР, чтобы вычислить Г„, надо сРавнить значениЯ с„+см, с„+с„и с„+сиь равные (после умножения на 16) соответственно 8, 9 и 11. Таким образом, в строке 8 рис.
4.9 Й=2 дает минимум, так что Г„=а,. Вычислив таблицу рнс, 4.11, строим дерево Т,о вызывая ПОСТРДЕРЕВА (0, 4). На рис. 4.12 изображено полученное в результате дерево двоичного поиска. Его стоимость равна ЗЗД6. () Теорема 4.2. Алгоритм 4.2 строит оптимальное дерево двоичного поиска за время 0(п'). Д о к а з а тел ь от в о. Вычислив таблицу значений Гы, мы строим по ней оптимальное дерево за время 0 (и), вызывая процедуру ПОСТРДЕРЕВА. Эта процедура вызывается только и раз, и каждый вызов занимает постоянное время. Наиболее дорого стоит алгоритм динамического программирования (рис. 4.9).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
