Бинарное дерево поиска

отличная работа с высоким уровнем уникальности ...

СОДЕРЖАНИЕ
Введение
Глава 1. Б-деревья
1.1 Основные определения
1.2 Определение, пример
1.3 Основные операции над Б-деревьями
1.3.1 Поиск
1.3.2 Добавление нового ключа
1.3.3 Удаление ключа
1.4 Варианты Б-деревьев
Глава 2.Двоичные Б-деревья
2.1 Определение
2.2 Включение ключей
2.3 Симметричное двоичное Б-дерево
Заключение
Библиографический список

С увеличением объемов хранимой и обрабатываемой информации все важней становится вопрос о выборе структур данных, поскольку именно от них зависит производительность программ и систем где они используются.
Одними из самых эффективных и в то же время сложных структур являются Б-дерево и двоичное Б-дерево, поэтому темой данной работы являются Б-деревья, двоичные Б-деревья, которые будут рассмотрены отдельно.............

Рис. 4. Результат удаления ключа 38 из Б-дерева Может оказаться, что ни одна из соседних страниц непригодна для переливания, поскольку содержат по n ключей. Тогда выполняется процедура слияния соседних листовых страниц. К 2*n-1 ключам соседних листовых страниц добавляется средний ключ из страницы-предка (из страницы-предка он изымается), и все эти ключи формируют новое содержимое исходной листовой страницы. Поскольку в странице-предке число ключей уменьшилось на единицу, может оказаться, что число элементов в ней стало меньше n, и тогда на этом уровне выполняется процедура переливания, а возможно, и слияния. Так может продолжаться до внутренних страниц, находящихся непосредственно под корнем Б-дерева. Если таких страниц всего две, и они сливаются, то единственная общая страница образует новый корень. Высота дерева уменьшается на единицу, но по-прежнему длина пути до любого листа одна и та же. Пример удаления ключа со слиянием листовых страниц показан на рисунке 5. a) Начальный вид Б-дерева (b) Б-дерево после удаления ключа 6Рис. 5. Пример удаления ключа из Б-дерева со слиянием листовых страниц: 1.4 Варианты Б-деревьевСуществует несколько видов Б-деревьев, которые практикуют в современном программировании: Б-деревья, Б*-деревья, Б+-деревья, Б++-деревья, R-деревья, RB-деревья (красно-черные деревья).В стандартных Б-деревьях ключи и данные хранятся как во внутренних узлах, так и в листьях (концевых узлах). Если при спуске по дереву во время вставки встречен заполненный узел, его содержимое перераспределяется между братьями. Если братья тоже полны, создается новый узел и половина ключей потомка пересылается в него. Во время удаления наполовину заполненные потомки являются первыми кандидатами на добавление ключей из прилежащих узлов. Если сами прилежащие узлы полны, лишь наполовину, они объединяются так, чтобы получился полный узел. Б*-деревья устроены аналогично, единственное отличие - узлы заполняются на 2/3. Это приводит к лучшему использованию места, занимаемого деревом, и чуть лучшей производительности. На рис. 6 представлено Б+-дерево. Все ключи хранятся в листьях, там же хранится и информационная часть узла. Во внутренних узлах хранятся копии ключей - они помогают искать нужный лист. У указателей смысл немножко не такой, как при работе с обычными Б-деревьями. Левый указатель ведет к ключам, которые меньше заданного значения, правый - ключам, которые больше или равны (GE). Например, к ключам, меньшим 22, ведет левый указатель, а к ключам от 23 и выше ведет правый. Обратите внимание на то, что ключ 22 повторяется в листе, где хранятся соответствующие ему данные. Во время вставки и удаления необходимо аккуратно работать с родительскими узлами. Когда модифицируются первый ключ в листе, дерево проходится от листа к корню. Последний из GE-указателей, найденный при спуске по дереву, и является тем, который потребуется модифицировать, чтобы отразить новое значение ключа. Поскольку все ключи повторяются в листьях, мы можем связать их для последовательного доступа.Рис. 6: Б+-дерево Последний метод, Б++-деревья. Оно устроено аналогично Б+-деревьям, отличается лишь стратегия расщепления/объединения.Предположим, что в каждом узле могут храниться k ключей, а в корне их может быть 3k. Перед тем, как во время вставки мы спустимся к потомку, мы проверяем, пуст ли он. Если это так, ключи, находящиеся в потомке и двух смежных к нему узлах, объединяются и перераспределяются. Если два смежных узла также заполнены, то добавляется узел. Таким образом, мы получаем уже четыре узла, каждый из которых полон на 3/4. Перед тем, как во время удаления спуститься к потомку, мы проверяем, не полон ли он на 1/2. Если это так, ключи потомка и двух смежных узлов объединяются и перераспределяются. Если два смежных узла сами полны наполовину, они сливаются в два узла, каждый из которых полон на 3/4. Мы, таким образом, оказываемся посредине между заполненностью на 1/2 и полной заполненностью, что позволяет нам ожидать равного числа вставок и удалений. Напомним, что в корневом узле хранятся 3k ключей. Если во время вставки окажется, что корень полон, мы распределяем ключи по четырем новым узлам, каждый из которых полон на 3/4. Это увеличивает высоту дерева. Во время удаления мы исследуем потомков. Если имеется только три потомка и они полны наполовину, переносим их содержимое в корень, в результате чего высота дерева уменьшается.Другой способ описать работу с деревом - сказать, что мы собираем три узла, а затем рассыпаем их. При вставке, когда нам нужен дополнительный узел, мы рассыпаем на четыре узла. При удалении, когда узел нужно удалить, мы рассыпаем на два узла. Симметрия операций позволяет использовать при реализации вставки и удаления одни и те же собирающие/рассыпающие функции. Коротко рассмотрим еще одно расширение механизма Б-деревьев, используемое главным образом для организации индексов в пространственных базах данных, - R-деревья. Подобно B+-деревьям, R-дерево представляет собой ветвистую сбалансированную древовидную структуру с разной организацией внутренних и листовых страниц. Но информация, хранящаяся в R-дереве несколько отличается от той, которая содержится в B-деревьях. В дополнение к находящимся в листовых страницах идентификаторам пространственных объектов, в R-деревьях хранится информация о границах индексируемого объекта. В случае двумерного пространства сохраняются горизонтальные и вертикальные координаты нижнего левого и верхнего правого углов наименьшего прямоугольника, содержащего индексируемый объект. Пример простого R-дерева, содержащего информацию о шести пространственных объектах, приведен на рисунке 7.Рис. 7. Простое R-дерево для представления шести пространственных объектов Ещё одной разновидностью Б-деревьев являются так называемые красно-черные деревья. Красно-черное дерево – это двоичное дерево поиска, вершины которого разделены на красные и черные. Двоичное дерево поиска называется красно-черным деревом, если оно обладает следующими свойствами: • Каждая вершина – либо черная, либо красная. • Корень дерева является черным • Каждый лист (NIL) – черный. • Если вершина красная, оба ее ребенка черные. • Все пути, идущие вниз от корня к листьям, содержат одинаковое количество черных вершин. На рис.8 представлен пример красно-черного дерева. Рис.8 Красно-черное дерево ГЛАВА 2. ДВОИЧНЫЕ Б-ДЕРЕВЬЯ 2.1 ОпределениеДвоичное (бинарное) Б-дерево (ДБ-дерево) состоит из вершин (страниц) с одним или двумя элементами. Следовательно, страница содержит две или три ссылки на потомков (отсюда ещё один термин – 2-3 дерево). По определению в Б-дереве все листовые страницы расположены на одном уровне, а все не листовые страницы (включая и корневую) имеют двух или трех потомков. Подведем итог.Бинарное Б-дерево: • состоит из узлов с одним или двумя элементами; • содержит две или три ссылки на потомков (поэтому другое название ДБ-дерева 2-3 дерево); • все листья находятся на одном уровне; • все нетерминальные страницы содержат два или три потомка.Для экономии памяти и оптимального её использования при работе с ДБ-деревьями используется динамическое, связанное размещение элементов (внутри каждого узла имеется связанный список длиной 1 или 2), поскольку в данном случае представление элементов узла в виде массива здесь не подходит. Так как каждая вершина может иметь не более трех потомков и, следовательно, должна содержать самое большее три ссылки, то мы попытаемся объединять ссылки на потомков со ссылками в списке элементов. Таким образом, вершины Б-дерева теряют свою целостность, и элементы начинают играть роль вершин в регулярном двоичном дереве. Однако остается необходимость делать различие между ссылками потомков (по вертикали) и ссылками на «братьев» в одной странице (по горизонтали). Так как по горизонтали могут быть только ссылки вправо, то для фиксации направления достаточно одного-единственного разряда. Поэтому введем булевское поле h, говорящее, что ссылка идет по горизонтали. Определение вершины дерева, соответствующее такому направлению:TYPEPtr = POINTER TO Node;TYPENode = RECORD key: INTEGER; ……………………………… Left,right:Ptr; H: Boolean; (горизонтальная правая ветвь) ENDТак же для представления ДБ-дерева можно выбрать следующую структуру: typedef struct node { int key; node *left; node *right; int h; };,где left - указатель на страницу-наследник, right - указатель либо на страницу-потомок, либо на страницу-брата; для различия используется показатель h (при одном значении фиксируется горизонтальное перемещение, а при другом - вертикальное).[pic]Обе эти организации дерева поиска гарантируют, что максимальная длина пути будет равна p=2*[log N]. 2 .2 Включение ключейРассматривая задачу включения ключей, следует различать четыре возможных ситуации, возникающих при росте левых или правых поддеревьев.(1) Самый простой случай – рост правого поддерева вершины А, причем А – единственный элемент на странице (мнимой). В этой ситуации предок В просто становится братом А, то есть «вертикальная» ссылка превращается в «горизонтальную». Если вершина А уже имеет брата, то такой простой «поворот» правой ветки невозможен. Получаем страницу с тремя вершинами, и её необходимо разделить. Средняя вершина страницы В передается на следующий вышележащий уровень Пусть теперь левое поддерево вершины В растет в высоту. Если вершина В снова одна на странице, то есть её правая ссылка указывает лишь на предка, то левое поддерево А может стать братом В. (Так как левая ссылка не может быть горизонтальной, то требуется некоторое простое «вращение» ссылок). Если же В уже имеет брата, то «подъем» А приводит к странице с тремя элементами, требующей разделения. Разделение происходит очень просто: вершина С становится потомком В, а последняя поднимается уровнем выше.