Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Топ:
Теоретическая значимость работы: Описание теоретической значимости (ценности) результатов исследования должно присутствовать во введении...
История развития методов оптимизации: теорема Куна-Таккера, метод Лагранжа, роль выпуклости в оптимизации...
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Интересное:
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Дисциплины:
2019-11-19 | 359 |
5.00
из
|
Заказать работу |
|
|
Два крайних случая АВЛ-деревьев это:
(а) совершенное дерево – все узлы имеют показатель баланса 0;
(б) дерево Фибоначчи – все узлы, кроме листовых, имеют показатель баланса +1, либо все узлы, кроме листовых, имеют показатель баланса –1.
Не для каждого набора ключей можно построить совершенное дерево, равно как и не для каждого набора ключей можно построить дерево Фибоначчи. Но эти деревья позволяют оценить диапазон возможных высот АВЛ-деревьев. Совершенное дерево является частным случаем идеально сбалансированного дерева, поэтому оно имеет минимально возможную высоту для данного количества узлов. Дерево Фибоначчи, напротив, имеет максимально возможную высоту для данного количества узлов, при условии, что сохраняются свойства АВЛ-дерева. В совершенном дереве у каждого узла, кроме листовых, ровно два сына. Тогда количество узлов m равно 1 + 2 + 22 + … Количество таких слагаемых равно количеству уровней в дереве, т.е. на единицу больше высоты этого дерева. Если количество слагаемых равно h + 1, то степень двойки в последнем слагаемом будет равна h:
Поэтому высота совершенного дерева вычисляется как h = log2(m + 1) – 1
Дерево Фибоначчи имеет минимально возможную высоту для заданного количества узлов среди всех АВЛ-деревьев. Если переформулировать свойство дерева Фибоначчи, то получится, что при заданной высоте оно имеет минимальное количество узлов из всех возможных АВЛ-деревьев.
Из определения дерева Фибоначчи следует, что для любого узла, кроме листовых, разность высот левого и правого поддеревьев равна 1 либо –1. Не ограничивая общности рассуждений, будем считать, что эта разность равна 1. Таким образом, если высота дерева равна h, то высоты левого и правого поддеревьев равны h – 2 и h – 1 соответственно. Это свойство выполняется для любого поддерева дерева Фибоначчи.
|
*ДАЛЬШЕ МНОГО ВЫЧИСЛЕНИЙ ВСЯКИХ, ШЛИ БЫ ОНИ НАФИГ*
Высота h АВЛ-дерева из m узлов находится в диапазоне
Это соотношение задает оценку количества сравнений при поиске узла в АВЛ-дереве на пути от корня к этому узлу. Если, например, в АВЛ-дереве 106 вершин, то его высота, а, следовательно, и сложность поиска узла в нем, не превысит 29.
Особенностью АВЛ-дерева является то, что оно является сбалансированным в следующем смысле: для любого узла дерева высота его правого поддерева отличается от высоты левого поддерева не более чем на единицу. Доказано, что этого свойства достаточно для того, чтобы высота дерева логарифмически зависела от числа его узлов: высота h АВЛ-дерева с n ключами лежит в диапазоне от log2(n + 1) до 1.44 log2(n + 2) − 0.328. А так как основные операции над двоичными деревьями поиска (поиск, вставка и удаление узлов) линейно зависят от его высоты, то получаем гарантированную логарифмическую зависимость времени работы этих алгоритмов от числа ключей, хранимых в дереве.
|
|
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!