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


 

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

21453. Комплексные числа. Комплексные числа являются естественным обобщением понятия вещественных чисел 392 KB
  Комплексные числа. Комплексные числа являются естественным обобщением понятия вещественных чисел. При этом числа x и y называются вещественной и мнимой частями соответственного комплексного числа z. Два комплексных числа и считаются равными между собой тогда и только тогда когда равны их вещественные и мнимые части т.
21454. Линейные однородные дифференциальные уравнения с постоянными коэффициентами 234 KB
  Линейные однородные дифференциальные уравнения с постоянными коэффициентами. Оператор L можно представить в следующем виде 1б где – корни характеристического уравнения 4 – их кратности. При n=2 имеем причем где – корни характеристического уравнения Далее Пусть теперь при некотором: где мы...
21455. Системы линейных дифференциальных уравнений 293 KB
  Системы линейных дифференциальных уравнений. Напомним что достаточными условиями существования и единственности решения системы обыкновенных дифференциальных уравнений 1 удовлетворяющего начальным условиям 2 являются: непрерывность всех функций в окрестности начальных значений; выполнение условия Липшица для всех...
21456. Системы линейных дифференциальных уравнений с постоянными коэффициентами 282 KB
  Системы линейных дифференциальных уравнений с постоянными коэффициентами. Итак общее решение однородной системы 1 имеет вид 6 причем векторы 7 частные решения системы 1 которые могут быть получены следующим образом. Итак решения линейно...
21457. Матричная экспонента 394 KB
  а – матрица j – й столбец которой есть решение системы 1а с начальными условиями т. матрица имеет вид и удовлетворяет уравнению Тогда вектор t – решение системы 1а с начальным условием может быть записан в виде т. Запишем теперь jе решение уравнения 1а удовлетворяющее начальному условию где – диагональная матрица вектор столбец коэффициентов и положим где – матрица коэффициентов . Теперь окончательно имеем...
21458. Спектральные приборы 519 KB
  различаются методами спектрометрии приёмниками излучения исследуемым рабочим диапазоном длин волн и др. Форма отверстия в равномерно освещенном экране 1 соответствует функции f описывающей исследуемый спектр распределение энергии излучения по длинам волн . группа 2 информация об исследуемом спектре получается путём одновременной регистрации без сканирования по  несколлькими приёмниками потоков излучения разных длин волн ’ ’’ ’’’ .
21459. Управление света светом 870.5 KB
  ставит очень амбициозную задачу создание устройств выполняющих функции управления характеристиками оптического излучения с помощью другого оптического излучения. Предлагается воспользоваться свойствами поляризованного электромагнитного оптического излучения а именно использовать эффект оптического гашения который описан например в [3]. 1 Если четвертьволновую пластинку P1 установить так чтобы её быстрая ось была ориентирована под углом к оси OX то для излучения прошедшего через пластинку P1 получим = 1 = . 2 Согласно [4]...
21460. Применение лазерного излучения для управления движением атомами и ионами 789.5 KB
  Этот эффект называется охлаждением атомов давлением лазерного излучения. Методы позволяющие с помощью лазерного излучения охлаждать атомы основаны на эффекте вязкой жидкости оптическая патока в которой атомы медленно перемещаются. При охлаждении вещества его энергия и энтропия понижаются поэтому процесс охлаждения возможен если энергия и энтропия излучения после взаимодействия с веществом повышаются.
21461. Лазерный пинцет 957 KB
  Сила с которой свет действует на окружающие объекты невелика но ее оказывается достаточно чтобы ловить и контролируемо перемещать частицы размером от 10 нм до 10 мкм. В дальнейшем Эшкин и его коллеги продемонстрировали возможности оптической ловушки на основе инфракрасного лазера захватывать удерживать и перемещать в пространстве различные биологические объекты такие как вирусные частицы одиночные бактериальные и дрожжевые клетки и органеллы в живых клетках водорослей. Как будет вести себя частица в поле после Пишейпера В случаях...