30502

Алгоритмы поиска. Использование деревьев в задачах поиска: бинарные, сбалансированные, красно-черные деревья поиска

Доклад

Математика и математический анализ

Сравнение ключа поиска с эталоном необходимо провести для всех элементов дерева. Уменьшить число сравнений ключей с эталоном возможно если выполнить организацию дерева особым образом то есть расположить его элементы по определенным правилам. Поиск на таких структурах не дает выигрыша по выполнению по сравнению с линейными структурами того же размера так как необходимо в худшем случае выполнить обход всего дерева. Двоичные упорядоченные деревья Двоичное дерево упорядоченно если для любой его вершины x справедливы такие свойства: все...

Русский

2013-08-24

65.5 KB

64 чел.

  1.  Алгоритмы поиска. Использование деревьев в задачах поиска: бинарные, сбалансированные, красно-черные деревья поиска.

Поиск данных, являясь одним из приоритетных направлений работы с данными, предполагает использование соответствующих алгоритмов в зависимости от ряда факторов: способ представления данных, упорядоченность множества поиска, объем данных, расположение их во внешней или во внутренней памяти. Поиск – процесс нахождения конкретной информации в ранее созданном множестве данных. Как правило, данные представляют собой структуры, каждая из которых имеет хотя бы один ключ – значение определенного поля конкретной структуры. Ключ поиска – это поле, по значению которого происходит поиск.

Рассмотрим организацию поиска данных, имеющих древовидную структуру. Анализируя дерево только с точки зрения представления данных в виде иерархической структуры, заметим, что выигрыша при организации поиска не получится. Сравнение ключа поиска с эталоном необходимо провести для всех элементов дерева.

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

Двоичные (бинарные) деревья

Двоичные деревья представляют собой иерархическую структуру, в которой каждый узел имеет не более двух потомков. То есть двоичное дерево либо является пустым, либо состоит из данных и двух поддеревьев (каждое из которых может быть пустым). При этом каждое поддерево в свою очередь тоже является деревом. Поиск на таких структурах не дает выигрыша по выполнению по сравнению с линейными структурами того же размера, так как необходимо в худшем случае выполнить обход всего дерева. Поэтому интерес представляют двоичные упорядоченные деревья.

Двоичные упорядоченные деревья

Двоичное дерево упорядоченно, если для любой его вершины x справедливы такие свойства:

  1.  все элементы в левом поддереве меньше элемента, хранимого в x,
  2.  все элементы в правом поддереве больше элемента, хранимого в x,
  3.  все элементы дерева различны.

Если в дереве выполняются первые два свойства, но встречаются одинаковые элементы, то такое дерево является частично упорядоченным.

Основными операциями, производимыми с упорядоченным деревом, являются:

  1.  поиск вершины;
  2.  добавление вершины;
  3.  удаление вершины;
  4.  вывод (печать) дерева;
  5.  очистка дерева.

Алгоритм удаления элемента более трудоемкий, так как надо соблюдать упорядоченность дерева. При удалении может случиться, что удаляемый элемент находится не в листе, то есть вершина имеет ссылки на реально существующие поддеревья. Эти поддеревья терять нельзя, а присоединить два поддерева на одно освободившееся после удаления место невозможно. Поэтому необходимо поместить на освободившееся место либо самый правый элемент из левого поддерева, либо самый левый из правого поддерева. Упорядоченность дерева при этом не нарушится. Удобно придерживаться одной стратегии, например, заменять самый левый элемент из правого поддерева. Нельзя забывать, что при замене вершина, на которую производится замена, может иметь правое поддерево. Это поддерево необходимо поставить вместо перемещаемой вершины.

Временная сложность этих алгоритмов (она одинакова для этих алгоритмов, так как в их основе лежит поиск) оценим для наилучшего и наихудшего случая. В лучшем случае, то есть случае полного двоичного дерева, получаем сложность Omin(log n). В худшем случае дерево может выродиться в список. Такое может произойти, например, при добавлении элементов в порядке возрастания. При работе со списком в среднем придется просмотреть половину списка. Это даст сложность Omax(n).

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

В худшем случае, когда дерево вырождено в линейный список, хранение данных в упорядоченном бинарном дереве никакого выигрыша в сложности операций по сравнению с массивом или линейным списком не дает. В лучшем случае, когда дерево сбалансировано, для всех операций получается логарифмическая сложность, что гораздо лучше. Идеально сбалансированным называется дерево, у которого для каждой вершины выполняется требование: число вершин в левом и правом поддеревьях различается не более чем на 1.

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

При операциях добавления и удаления может произойти нарушение сбалансированности дерева. В этом случае потребуются некоторые преобразования, не нарушающие упорядоченности дерева и способствующие лучшей сбалансированности.

Рассмотрим такие преобразования. Пусть вершина a имеет правый потомок b. Обозначим через P левое поддерево вершины a, через Q и R – левое и правое поддеревья вершины b соответственно. Упорядоченность дерева требует, чтобы P<a<Q<b<R. Точно того же требует упорядоченность дерева с корнем b, его левым потомком a, в котором P и Q – левое и правое поддеревья вершины aR – правое поддерево вершины b. Поэтому первое дерево можно преобразовать во второе, не нарушая упорядоченности. Такое преобразование называется малым правым вращением. Аналогично определяется симметричное ему малое левое вращение.

Пусть b – правый потомок вершины ac – левый потомок вершины bP – левое поддерево вершины aQ и R – соответственно левое и правое поддеревья вершины c,S – правое поддерево b. Тогда P<a<Q<c<R<b<S. Такой же порядок соответствует дереву с корнем c, имеющим левый потомок a и правый потомок b, для которых P иQ – поддеревья вершины a, а R и S – поддеревья вершины b. Соответствующее преобразование будем называть большим правым вращением. Аналогично определяется симметричное ему большое левое вращение.

Схематично алгоритм добавления нового элемента в сбалансированное по АВЛ дерево будет состоять из следующих трех основных шагов.

Шаг 1. Поиск по дереву.

Шаг 2. Вставка элемента в место, где закончился поиск, если элемент отсутствует.

Шаг 3. Восстановление сбалансированности.

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

Алгоритм удаления элемента из сбалансированного дерева будет выглядеть так:

Шаг 1. Поиск по дереву.

Шаг 2. Удаление элемента из дерева.

Шаг 3. Восстановление сбалансированности дерева (обратный проход).

Первый шаг необходим, чтобы найти в дереве вершину, которая должна быть удалена. Третий шаг представляет собой обратный проход от места, из которого взят элемент для замены удаляемого, или от места, из которого удален элемент, если в замене не было необходимости. Операция удаления может потребовать перебалансировки всех вершин вдоль обратного пути к корню дерева, т.е. порядка log n вершин. Таким образом, алгоритмы поиска, добавления и удаления элементов в сбалансированном по АВЛ дереве имеют сложность, пропорциональную O(log n).

Красно-черные деревья

Для удобства поисковые деревья будем расширять, вводя дополнительный фиктивный узел (  -узел) и считая его потомком каждого узла исходного дерева, у которого нет правого, левого или обоих потомков, его же считаем родителем корня.

Красно-черное дерево — это расширенное двоичное дерево поиска, вершины которого разделены на красные (red) и черные (black) так, что:

  1.  Каждый узел либо красный, либо черный.
  2.  Каждый лист (  -узел) — черный.
  3.  Если узел красный, то оба его ребенка черные.
  4.  Все пути, идущие вниз от корня к листьям, содержат одинаковое количество черных узлов.

Свойства 1-4 называют RB-свойствами. Узлы красно-черного дерева будем представлять записями вида

Для справки:

  1.  Search — поиск элемента с заданным ключом.
  2.  Minimum — поиск элемента с минимальным ключом.
  3.  Maximum — поиск элемента с максимальным ключом.
  4.  Predecessor — поиск элемента с предыдущим ключом.
  5.  Successor — поиск элемента со следующим ключом.
  6.  Insert — вставка элемента со своим ключом.
  7.  Delete — удаление указанного элемента.


 

А также другие работы, которые могут Вас заинтересовать

79933. Торговые договоры 73.5 KB
  Торговые договоры. Договор поручения По договору поручения поверенный обязуется совершать от имени и за счет доверителя определенные юридические действия ст. Помимо юридических действий поверенный совершает и фактические действия но они носят сопутствующий не основной характер поэтому не изменяют квалификацию договора. Права и обязанности поверенного определяются договором а также доверенностью которую доверитель обязан выдать поверенному ст.
79934. Внешнеторговая деятельность. Регулирование внешнеторговых отношений 60 KB
  Под ней понимается предпринимательская деятельность в области международного обмена товарами работами услугами информацией результатами интеллектуальной деятельности. Существенные условия контракта: наименование товара его обозначение; количество товара или порядок его определения...
79935. Договор подряда. Общие положения о подряде 239 KB
  В структуре главы Подряд выделяются общие положения бытовой подряд строительный подряд подряд на выполнение проектных и изыскательских работ подрядные работы для государственных нужд. Статья 702 ГК признает подрядом договор по которому одна сторона подрядчик обязуется выполнить по заданию другой стороны заказчика определенную работу и сдать ее результат заказчику а заказчик обязуется принять результат работы и оплатить его. Приведенное определение позволяет квалифицировать подряд как договор возмездный...
79936. Договор. Сущность договора. Заключение договоров в сети Интернет 101 KB
  Сущность договора Торговый оборот деятельность по продвижению товарной массы от изготовителей к потребителям регулируется не только законодательством но и договорами заключаемыми хозяйствующими субъектами. Законом закреплено общее правило согласно которому условия договора определяются соглашением сторон. Таким образом определение содержания договора происходит не на основе избрания сторонами приемлемых норм права а в результате самостоятельной выработки конкретных правил взаимосвязанной деятельности и придания им значения взаимных прав...
79937. Страхование. Понятие и значение страхования 312.5 KB
  Понятие и значение страхования 1. В отличие от самострахования при страховании в собственном смысле страховой фонд обслуживает не одно а целый ряд лиц и или организаций и здесь действует принцип централизации страхового фонда. Страхование в собственном смысле этого термина может осуществляться либо в форме взаимного страхования определенным образованием организованной группы лиц своими взносами образующих страховой фонд из которого они участники фонда получают возмещение возникшего вреда либо в форме так называемого коммерческого...
79938. Договоры купли-продажи, мены, дарения 222 KB
  Передача товара покупателю представляет собой исполнение заключенного и вступившего в силу договора куплипродажи со стороны продавца. Если момент вступления договора в силу совпадает с фактической передачей товара то он исполняется в момент заключения. Он является договором синаллагматическим поскольку исполнение обязательств покупателем по оплате товара обусловлено исполнением продавцом своих обязательств по передаче товара покупателю п. Иными словами покупатель не должен исполнять свои обязанности по оплате товара до исполнения...
79939. Договор аренды, лизинга, ссуды. 197.5 KB
  Понятие договора аренды Договор имущественного найма зародился в римском праве как договор найма вещей loctioconductio rerum. Дореволюционное российское гражданское законодательство использовало понятие договора имущественного найма не придавая какоголибо специального юридического значения одновременному применению понятия аренда имущества. Поэтому предметом договора аренды объявляется только плодоносящая вещь. В действующем законодательстве дается следующее легальное определение договора аренды.
79940. Транспортные договоры. Транспортное законодательство 242 KB
  Морские порты выполняют широкий круг транспортных операций: погрузку разгрузку и обслуживание заходящих в порт судов транспортноэкспедиторские и складские операции с грузами перевалку грузов между разными видами транспорта обслуживание пассажиров морских судов а также местные перевозки грузов и пассажиров на судах порта. Договор перевозки груза его особенности и виды Гражданский кодекс воспроизводит традиционное правило транспортного права согласно которому перевозка грузов осуществляется на основании договора перевозки и дает этому...
79941. Ответственность. Понятие и признаки гражданско-правовой ответственности 105 KB
  Такие меры понуждения к реальному исполнению обязательств нельзя считать ответственностью поскольку обязанность реального исполнения вытекает непосредственно из самого обязательства а ответственность должна выражаться в какомто дополнительном бремени. Долгое время в нашем законодательстве использовался принцип реального исполнения обязательств когда уплата неустойки и возмещение убытков не освобождали должника от исполнения обязательства в натуре. Если уплата неустойки и возмещение убытков вызваны ненадлежащим исполнением обязательства...