Произвольность деревьев поиска

Время выполнения алгоритмов обработки BST-деревьев находится в зависимости от форм деревьев. В наилучшем случае дерево может быть вполне равновесным и содержать прибли­зительно lgN узлов меж корнем и каждым из наружных узлов, но в худшем случае в любой из путей поиска может содержать N узлов[3].

Можно также возлагать Произвольность деревьев поиска, что в среднем время поиска также будет связано с коли­чеством узлов логарифмической зависимостью, так как 1-ый вставляемый элемент становится корнем дерева. Если N ключей должны быть вставлены в случайном по­рядке, то этот элемент разделял бы ключи напополам (в среднем), что отдало бы логарифми­ческую зависимость времени поиска (при использовании Произвольность деревьев поиска подобных рассуждений применительно к поддеревьям). Вправду, вероятен случай, когда BST-дерево приводит в точности к этим же сопоставлениям, что и бинарный поиск. Этот случай был бы лучшим для данного метода, гарантируя логарифми­ческую зависимость времени выполнения для всех видов поиска. В вправду про­извольной ситуации корнем может быть хоть какой Произвольность деревьев поиска ключ, и потому вполне сбаланси­рованные деревья встречаются только изредка, соответственно, без особенных усилий не получится сохранять дерево стопроцентно равновесным после каждой встав­ки. Но стопроцентно несбалансированные деревья также встречаются изредка при про­извольных ключах, потому-то в среднем деревья довольно отлично сбалансирова­ны. В этом Произвольность деревьев поиска разделе мы детализируем это наблюдение.

А именно, длина пути и высота бинарных деревьев, конкретно связаны с затратами на поиск в BST-деревьях. Высота определяет сто­имость поиска в худшем случае, длина внутреннего пути конкретно связана со ценой попаданий при поиске, а длина наружного пути конкретно связана со ценой промахов при поиске Произвольность деревьев поиска.

Лемма 18:Для обнаружения попадания при поиске в дереве бинарного поиска, образо­ванном N случайными ключами, в среднем требуется около 2 lgN ~ 1.39 lgN сравнений.

Cчитаем поочередные операции == и < одной операцией сопоставления. Количество сравнений, использованных для обнару­жения попадания при поиске, завершающемся в данном узле, равно 1 плюс рас­стояние от этого узла до Произвольность деревьев поиска корня. Таким макаром, интересующая величина равна 1 плюс средняя длина внутреннего пути BST-дерева, которую можно проанализи­ровать с внедрением уже знакомых рассуждений: если — средняя длина внутреннего пути BST-дерева, состоящего из N узлов, мы имеем последующее ре­куррентное соотношение:

при . Член N-1 учитывает, что корень наращивает длину Произвольность деревьев поиска пути для каждо­го из других N-1 узлов на 1; остальная часть выражения вытекает из того, что ключ в корне (вставленный первым) с равной вероятностью может быть к-м по ве­личине ключом, разбивая дерево на произвольные поддеревья размерами &-1 и N - k.

Лемма 19: Для выполнения вставок и обнаружения промахов при поиске в Произвольность деревьев поиска дереве бинар­ного поиска, образованном N случайными ключами, в среднем требуется около 2 lg N ~ 1.39 lgN сравнений.

Поиск случайного ключа в дереве, содержащем N узлов, с равной вероятнос­тью может закончиться в любом из N - 1 наружных узлов обнаружением промаха при поиске. Эта лемма в купе с тем, что разница Произвольность деревьев поиска длин наружного и внутреннего пути в любом дереве равна просто 2 N), обусловливает обсужденный итог. В любом BST- дереве среднее количество сравнений, нужных для выполнения вставки либо обнаружения промаха, приблизи­тельно на 1 больше среднего количества сравнений, необ­ходимых для выявления попадания при поиске.

Набросок 34. Пример дерева бинарного поиска

В этом BST Произвольность деревьев поиска-дepeвe, которое было выстроено за счет вставки около 200 случайных ключей в сначало пустое дерево, ни один поиск не употребляет более 12 сравнений. Средняя цена обнаружения попадания при поиске примерно равна 10.

В согласовании с леммой 18 следует ждать, что затра­ты на поиск для BST-деревьев должна быть примерно на Произвольность деревьев поиска 39% выше издержек для бинарного поиска случайных ключей. Но в согласовании с леммой 19 дополнительные издержки полностью окупаются, так как новый ключ может быть вставлен практически при тех же издержек — схожая упругость при использовании бинарного поиска не доступна.

На рисунке 34 показано BST-дерево, приобретенное в итоге длинноватой цепи случайных перестановок. Хотя оно Произвольность деревьев поиска содержит не­сколько длинноватых и несколько маленьких путей, его можно считать отлично равновесным: для выполнения хоть какого поиска требуется наименее 12 сравнений, а среднее количество сравнений, нужных для обнаружения случайного попадания при поиске равно 7.00, что сопоставимо с 5.74 для варианта бинарного поиска.

Набросок.35. Худший случай дерева бинарного поиска

Если ключи в BST-дереве вставляются Произвольность деревьев поиска в порядке возрастания, дерево вырождается в форму, эквивалентную односвязному списку, приводя к квадратичной зависимости времени сотворения дерева и к линейной зависимости времени поиска.

Леммы 18 и 19 определяют производительность для среднего варианта при условии, что порядок ключей произво­лен. Если это не так, производительность метода имеет тенденцию к понижению Произвольность деревьев поиска.

Лемма 20:В худшем случае для поиска в дереве бинарного по­иска с N ключами может требоваться N сравнений.

На рис. 35 показаны два примера наихудших слу­чаев BST-деревьев. Для этих деревьев поиск с использова­нием бинарного дерева ничем не лучше последовательно­го поиска с внедрением односвязных списков.

Таким макаром Произвольность деревьев поиска, высочайшая производительность базисной ре­ализации таблиц знаков с внедрением BST-дерева тре­бует, чтоб ключи в достаточной степени были подобны про­извольным ключам, а дерево не содержало длинноватых путей.

Более того, наихудший случай не настолько уж изредка встречает­ся на практике — он появляется при вставке ключей в перво­начально Произвольность деревьев поиска пустое дерево по порядку либо в оборотном порядке с применением стандартного метода — последователь­ность операций, которую мы определено можем предпри­нять, не получив никакого очевидного предупреждения не делать этого. Ни одна из других рассмотренных реализаций таблиц знаков не может употребляться для выполнения задачки вставки в таблицу очень огромного количества Произвольность деревьев поиска произволь­ных ключей, а потом поиска каждого из их — время вы­полнения каждого из способов определяется квадратичной зависимостью. Более того, из анализа следует, что среднее расстояние до узла в бинар­ном дереве пропорционально логарифму количества узлов в дереве, что позволяет отлично делать смешанные наборы операций поиска, вставки и других операций с Произвольность деревьев поиска АТД таблицы знаков, что и будет скоро показано.

Набросок 36. Ещё один худший случай дерева бинарного поиска.

Огромное количество других схожих вариантов порядка вставки ключей приводят к вырождению BST-дерева. Все же, дерево бинарного поиска, образованное произвольно упорядоченными ключами, вероятнее всего, окажется отлично равновесным.


prokatka-referat.html
prokimen-voskresnij-glasa-ili-prazdnika.html
prokladka-trassi-podklyucheniya-duta.html