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


 

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

80147. ПОНЯТИЕ И ВИДЫ ФИНАНСОВО-ПРАВОВЫХ НОРМ 53.5 KB
  Как и любая другая норма права финансовоправовая норма представляет собой установленное и охраняемое государством правило поведения участников общественных отношений выраженное в их юридических правах и обязанностях. Особенности финансовоправовой нормы обусловлены тем что она в отличие от норм других отраслей права регулирует отношения возникающие в процессе планового образования распределения и использования государством и органами местного самоуправления финансовых ресурсов необходимых им для осуществления своих задач. Это...
80148. ВИДЫ ФИНАНСОВОГО КОНТРОЛЯ 53.5 KB
  Одним из важнейших принципов контроля в государстве является финансовый контроль. Финансовый контроль в России особенно актуален в период перехода от командноадминистративных к рыночным формам управления экономикой. По мере развития рыночной экономики тем более с усилением ее социальной ориентации контрольнофинансовые функции государства все более усложняются все большее число функций по защите финансовых прав и интересов граждан ложится на плечи государства.
80149. ПРАВОВОЙ РЕЖИМ ГОСУДАРСТВЕННЫХ ВНЕБЮДЖЕТНЫХ ФОНДОВ 99.5 KB
  Бюджеты государственных внебюджетных фондов Российской Федерации рассматриваются и утверждаются Федеральным Собранием в форме федеральных законов одновременно с принятием федерального закона о федеральном бюджете на очередной финансовый год. Проекты бюджетов территориальных государственных внебюджетных фондов представляются органами исполнительной власти субъектов Российской Федерации одновременно с представлением проектов законов субъектов Российской Федерации о бюджете на очередной финансовый год и утверждаются одновременно с принятием...
80150. СУЩНОСТЬ И ЗНАЧЕНИЕ ГОСУДАРСТВЕННОГО КРЕДИТА 131 KB
  Функционирование системы государственного кредита ведет к образованию государственного долга. Под управлением государственным кредитом в узком смысле понимается совокупность действий связанных с подготовкой к выпуску и размещению долговых обязательств государства регулированию рынка государственных ценных бумаг обслуживанию и погашению государственного долга представлению кредитов и гарантий. Рефинансирование государственного долга погашение старой государственной задолженности путем выпуска новых займов; 3. Аннулирование...
80154. СТАДИЯ ИСПОЛНЕНИЯ БЮДЖЕТА 33 KB
  Исполнение бюджета обеспечивает в установленном порядке Министерство финансов РФ вся система органов управления финансами РФ. В процессе исполнения бюджета органы исполнительной и представительной власти осуществляют корректировку бюджетных назначений с учетом динамики цен и поступлений доходов в федеральный бюджет осуществляют контроль за исполнением федерального бюджета и целевым использованием средств выделяемых из федерального бюджета предприятиям учреждениям и организациям. Главный распорядитель средств федерального бюджета орган...
80155. ИСТОЧНИКИ ФИНАНСОВОГО ПРАВА. ФИНАНСОВОЕ ЗАКОНОДАТЕЛЬСТВО 47 KB
  Нормы финансового права Российской Федерации содержатся в большом числе разнообразных правовых нормативных актов или источниках. В дореволюционном российском праве под источниками права понимались формы выражения положительного права которые имеют значение обязательных средств ознакомления с действующим правом. В современной российской юридической науке под источником права обычно понимают форму выражения правила сообщающую ему качество правовой нормы; тот единственный резервуар в котором пребывают...