30502

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

Доклад

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

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

Русский

2013-08-24

65.5 KB

63 чел.

  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 — удаление указанного элемента.


 

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

11056. Основы проектирования интегрированных мехатронных модулей и систем 734 KB
  Основы проектирования интегрированных мехатронных модулей и систем Основой метода мехатроники является интеграция составляющих частей которая закладывается на этапе проектирования и затем реализуется в технологических процессах производства и эксплуатации мехат...
11057. Методы интеграции при проектировании мехатронных агрегатов 182.5 KB
  Методы интеграции при проектировании мехатронных агрегатов Для проектирования интегрированных мехатронных агрегатов разработаны три метода интеграции. Каждый из методов может применяться как самостоятельно так и в комбинации с другими методами поскольку они реа
11058. Создание базы данных каналов промышленного контроллера в SCADA системе TRACE MODE 561.5 KB
  Создание базы данных каналов промышленного контроллера в SCADA системе TRACE MODE: методические указания по выполнению практической работы и варианты заданий / Воронеж. гос. технол. акад.; сост. И.А. Хаустов А.А Хвостов Р.А. Романов. Воронеж: ВГТА 2011. 32 с. Указания разработаны
11059. Создание базы каналов автоматизированного рабочего места диспетчерского контроля и управления с настройкой сетевого обмена 447 KB
  Создание базы каналов автоматизированного рабочего места диспетчерского контроля и управления с настройкой сетевого обмена: методические указания по выполнению практической работы / Воронеж. гос. технол. акад.; сост. И.А. Хаустов А.А Хвостов Р.А. Романов. Воронеж: ВГТА 20...
11060. Создание пользовательских функциональных блоков программированием на СИ++ 900 KB
  Создание пользовательских функциональных блоков программированием на СИ: Методические указания для выполнения лабораторной работы по дисциплине Интегрированные системы проектирования и управления / Воронеж. гос. технол. акад.; Сост. И.А. Хаустов А.А. Хвостов. Воронеж...
11061. Создание и отладка программ на языке инструкций 270 KB
  Создание и отладка программ на языке инструкций: Методические указания для выполнения практической работы по дисциплине Интегрированные системы проектирования и управления / Воронеж. гос. технол. акад.; Сост. И.А. Хаустов. Воронеж 2011. 13 с. Указания разработаны в соотве...
11062. Создание графического интерфейса оператора технолога 1.25 MB
  Создание графического интерфейса оператора технолога: Методические указания для выполнения лабораторной работы по дисциплине Интегрированные системы проектирования и управления / Воронеж. гос. технол. акад.; Сост. И.А. Хаустов. Воронеж 2011. 54 с. Указания разработаны в ...
11063. Создание и настройка отчета тревог 475.5 KB
  Создание и настройка отчета тревог: Методические указания для выполнения лабораторной работы по дисциплине Интегрированные системы проектирования и управления / Воронеж. гос. технол. акад.; Сост. И.А. Хаустов. Воронеж 2011. 12с. Указания разработаны в соответствии с тре
11064. Введение в управленческое документоведение 838.5 KB
  Глава 1. Управленческие документы и их общая характеристика Управление и управленческая информация. Представление информации в практике управления. Управление и управленческая информация Управление и информация два тесно связанных между собо