Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Сбалансированные деревья поиска

Преобразование скобочных выражений в обратную польскую запись | Нелинейные структуры. Деревья | Обходы дерева | Бинарное дерево. Построение бинарного дерева | Помеченные деревья и деревья выражения | Реализация деревьев | Представление списков в виде БД | Прошитые БД | Применение деревьев. Представление сообщений кодами Хаффмана | Идеально сбалансированные бинарные деревья |


Читайте также:
  1. VIII. В ПОИСКАХ УЛИК
  2. АКТУАЛЬНЫЕ ПАТЕНТНЫЕ САЙТЫ, ПРОВЕДЕНИЕ ПОИСКА
  3. Бинарные деревья поиска
  4. Блок поиска дальности
  5. В отчаянных поисках эргономики
  6. В ПОИСКАХ АЛЬТЕРНАТИВ
  7. В поисках высшей истины

 

Время поиска в БД поиска определяется высотой самого дерева. Для заданного числа элементов n высота дерева зависит от порядка поступления элементов при построении дерева и может колебаться от в случае идеальной сбалансированности дерева до n -1 в случае вырождения дерева в линейный список. Следовательно, затраты на поиск и включение будут порядка от до n.

Доказано, что при случайном порядке включения элементов в дерево средние затраты на поиск элемента будут 1.386* . Увеличение затрат на 39% объясняется простыми средствами поддержания обычного дерева поиска по сравнению с идеально сбалансированным деревом поиска. Однако при работе с большими деревьями свойство случайности распределения поступающих данных редко соблюдается – это, скорее, исключение, чем правило. Обычно выходные последовательности являются частично упорядоченными. Для таких последовательностей наиболее подходящими оказываются сбалансированные деревья поиска. Рассмотрим один из видов таких деревьев: АВЛ – деревья, предложенные в 1962 г. Адельсоном-Вельским и Ландисом.

Требования к сбалансированности в АВЛ-деревьях менее жесткие, чем в идеально сбалансированных деревьях.

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

Максимальная высота АВЛ-дерева с n вершинами не превосходит 1.44* т.е. затраты на поиск не превосходят 1.45* .

Отличие АВЛ-дерева от обычного дерева поиска заключается в том, что при включении и удалении элементов необходимо поддерживать сбалансированность дерева в целом. Для этого в каждый узел дерева добавляется одно вспомогательное поле, содержащее информацию о равновесности поддеревьев (показатель сбалансированности узла). Его значениями могут быть: 0 – высоты правого и левого поддеревьев равны; 1 – высота правого поддерева больше; -1 – высота левого поддерева больше.

При попытке добавить или удалить элемент в поддереве с показателем сбалансированности, отличным от 0, дерево может стать несбалансированным, и потребуется операция балансировки.

 


Дата добавления: 2015-07-16; просмотров: 79 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Бинарные деревья поиска| Операции над деревьями

mybiblioteka.su - 2015-2024 год. (0.005 сек.)