30502

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

Доклад

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

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

Русский

2013-08-24

65.5 KB

61 чел.

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


 

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

81158. Максим Максимович Ковалевский 36.16 KB
  Продолжая линию Конта в этом вопросе Ковалевский формулирует основной социологический закон закон роста солидарности а также основной вопрос социологии вопрос об общественном историческом прогрессе. Солидарность объединяет подчеркивает Ковалевский единое политическое целое государство под влиянием факторов мировой религии и международного торгового обмена солидарность объединяет ряд государств а в перспективе ведет к всемирному единству народов. Ковалевский критикует однофакторные точки зрения получившие широкое распространение на...
81159. Христианский гуманизм 41.05 KB
  По мнению Соловьева от начала истории три основные силы управляли человеческим развитием коренящиеся в совместном существовании трех исторических миров грех культур резко между собой различающиеся: Мусульманский Восток Западная цивилизация и Славянский мир. Мусульманский Восток находится под преобладающим влиянием так называемой первой силы которая стремится подчинить человечество во всех сферах на всех уровнях его жизни одному верховному началу подавить его самостоятельность и свободу личной жизни. Один господин и аморфная масса рабов...
81160. Анархизм как социально-политическое течение 39.24 KB
  Анархизм (от греч. anarchia - безначалие, безвластье) — это социально-политическое течение, отрицающее необходимость государственной и всякой иной власти, проповедующее неограниченную свободу личности, непризнание общего для всех порядка в отношении между людьми. Само течение сложилось в середине XIX в. Основные его теоретические положения были выдвинуты немецким философом Максом Штирнером и французским философом
81161. Второй этап развития теории социологии в России 38.63 KB
  Во главе социологического отделения созданного при факультете общественных наук Петроградского университета стал Питирим Александрович Сорокин 18891968 крупнейший ученый и общественный деятель внесший существенный вклад в развитие отечественной и мировой социологии. Сорокин один из лидеров правого крыла партии эсеров после Февральской революции 1917 г. в числе большой группы российской интеллигенции Центральным Комитетом ВКП б Сорокин был выслан из России за границу. Сорокин один из родоначальников теории социальной...
81163. Эмпирическая социология в России 39.49 KB
  Возникновение и развитие эмпирической социологии в России связывают обычно с серединой XIX столетия. Накопление эмпирического опыта по строительству новой жизни необходимость перехода от агитационнопропагандистских форм к научноисследовательским подготовили почву к возникновению зачатков отраслевой социологии на практическом материале труда быта и культуры социальной структуры и др. Кузмичева духовная жизнь и десятков других революционнопрогрессивных представителей социологии. Интерес к конкретным социологическим исследованиям вел к...
81164. Школа научного управления: Ф. Тейлор, А. Файоль, Г. Форд, Г. Эмерсон 38.83 KB
  Его система научной организации труда включала в себя ряд основных положений: научные основания производства научный подбор кадров обучение и тренировка организация взаимодействия между управляющими и рабочими. В социологии труда он изучал вопросы рестрикционизма группового взаимодействия и групповой динамики а также отношение к труду стимулирование мотивацию и организацию труда. Система Тейлора заложила основы научной организации труда через создание многочисленных правил законов и формул которые заменяют личное суждение работника и...
81165. Школа «человеческих отношений»: М. Фоллет, Э. Мэйо, Л. Урвик, К. Левин 40.51 KB
  Основные направления деятельности школы: применение наук об управлении человеческим поведением; разработка систем мотивации труда. Основное содержание доктрины человеческих отношений можно выразить следующими тезисами: человек социальное животное Мейо ввел понятие социальный человек; жесткая иерархия подчиненность формализация организационных процессов несовместимы с его природой; производительность труда зависит не только и не столько от методов организации производства сколько от того как управляющие относятся к...
81166. Бюрократическая модель управления (М. Вебер) 42.07 KB
  Вебер. Максимилиан Карл Эмиль Вебер Mximilin Crl Emil Weber родился 21го апреля 1864го в Эрфурте в Тюрингии Erfurt Thuringi. Старший из семи детей Макса Веберастаршего богатого и известного политика из Националлиберальной партии Германии и Хелен Фалленштайн Helene Fllenstein протестантки и кальвинистки. В доме Веберов собирались видные ученые и политики и молодой Вебер как и его брат Альфред lfred также ставший социологом и экономистом процветал в такой интеллектуальной атмосфере.