сортировка бинарным деревом

1. Типы и структуры данных
1.1. Понятие типа данных
1.2. Встроенные типы данных
1.3. Уточняемые типы данных
1.4. Перечисляемые типы данных
1.5. Конструируемые типы данных
1.5.1. Массивы
1.5.2. Записи
1.5.3. Записи с вариантами
1.5.4. Множества
1.6. Указатели
1.7. Динамическое распределение памяти и списки
1.8. Абстрактные (определяемые пользователями) типы данных
1.8.1. Представление типа
1.8.2. Реализация типа
1.8.3. Инкапсуляция
1.8.4. Наследование типов
1.8.5. Разновидности полиморфизма
1.9. Типы и структуры данных, применяемые в реляционных базах данных
1.10. Типы и структуры данных, применяемые в объектно-реляционных базах данных
1.10.1. Строчные типы данных
1.10.2. Наследование таблиц и семантика включения
1.10.3. Типы коллекций
1.10.4. Объектные типы данных
2. Методы внутренней сортировки
2.1. Сортировка включением
2.2. Обменная сортировка
2.3. Сортировка выбором
2.4. Сортировка разделением (Quicksort)
2.5. Сортировка с помощью дерева (Heapsort)
2.6. Сортировка со слиянием
2.7. Сравнение методов внутренней сортировки
3. Методы внешней сортировки
3.1. Прямое слияние
3.2. Естественное слияние
3.3. Сбалансированное многопутевое слияние
3.4. Многофазная сортировка
3.5. Улучшение эффективности внешней сортировки за счет использования основной памяти
4. Методы поиска в основной памяти
4.1. Методы поиска в основной памяти на основе деревьев
4.1.1. Двоичные деревья
4.1.2. Сбалансированные двоичные деревья
4.1.3. Деревья оптимального поиска
4.1.4. Деревья цифрового поиска
4.2. Методы хэширования для поиска в основной памяти
4.2.1. Совершенное хэширование
4.2.2. Коллизии при хэшировании и способы их разрешения
4.2.3. Линейное зондирование
4.2.4. Двойное хэширование
4.2.5. Использование цепочек переполнения
5. Методы поиска во внешней памяти
5.1. Методы поиска во внешней памяти на основе деревьев
5.1.1. Классические B-деревья
5.1.2. B+-деревья
5.1.3. Разновидности B+-деревьев для организации индексов в базах данных
5.1.4. R-деревья и их использование для организации индексов в пространственных базах данных
5.2. Методы хэширования для поиска во внешней памяти
5.2.1. Расширяемое хэширование
5.2.2. Линейное хэширование
5.2.3. Использование хэширования для организации индексов в базах данных
5.3. Дополнительные способы поддержки поиска в базах данных
5.3.1. Индексы соединения
5.3.2. Индексы на основе использования битовых шкал

4. Методы поиска в основной памяти
В этой части книги будут обсуждаться структуры данных в основной памяти и методы их использования, предназначенные для поиска данных в соответствии со значениями их ключей. Эта задача является не менее распространенной в программировании, чем внутренняя сортировка данных.
Главным образом, распространены два подхода - поиск в динамических древовидных структурах и поиск в таблицах на основе хэширования. Рассмотрению разновидностей этих подходов и посвящены следующие два раздела.
Заметим, что мы намеренно выделили в отдельную часть структуры данных и методы поиска данных во внешней памяти. Несмотря на использование того же набора терминов (деревья и хэширование) поиск во внешней памяти и критерии оценки эффективности алгоритмов существенно отличаются от тех, которые применимы в случае расположения данных в основной памяти.
4.1. Методы поиска в основной памяти на основе деревьев
Понятия, связанные с деревьями, широко известны и интуитивно понятны. Тем не менее, для однозначного понимания содержимого этого раздела (и соответствующего раздела следующей части курса) мы приведем несколько не слишком формальных определений и примеров.
Существует несколько возможных определений дерева. Например, с точки зрения теории графов деревом часто называют неориентированный граф с выделенной вершиной (корнем), который не содержит циклов. Нас будут интересовать не произвольные графы, а только ориентированные деревья, причем с точки зрения программистов. Поэтому мы используем следующее рекурсивное определение: дерево R с базовым типом T - это либо (a) пустое дерево (не содержащее ни одной вершины), либо (b) некоторая вершина типа T (корень дерева) с конечным (возможно, нулевым) числом связанных с ней деревьев с базовым типом T (эти деревья называются поддеревьями дерева R). Из этого определения, в частности, следует, что однонаправленный список (рисунок 4.1) является деревом.
Рис. 4.1.
Деревья можно представлять по-разному (это всего лишь однородная иерархическая структура). Например, на рисунках 4.1 и 4.2 показаны два разных способа представления одного и того же дерева, у которого базовый тип содержит множество букв латинского алфавита. Сразу заметим, что графовое представление на рисунке 4.2 больше соответствует специфике программирования.
Рис.4.2.
Придерживаясь естественной для графового представления терминологии, мы будем называть связи между поддеревьями ветвями, а корень каждого поддерева - вершиной. Упорядоченным деревом называется такое, у которого ветви, исходящие из каждой вершины, упорядочены. Например, два упорядоченных дерева на рисунке 4.3 различаются.

Рис.4.3.
По определению, корень дерева находится на уровне 0, а все вершины дерева, непосредственно связанные с вершиной уровня i, находятся на уровне i+1. Вершина x уровня i, непосредственно связанная с вершиной y уровня i+1, называется непосредственным предком (или родителем) вершины y. Такая вершина y соответственно называется непосредственным потомком (или сыном) вершины x. Вершина без непосредственных потомков называется листовой (или терминальной), нелистовые вершины называются внутренними. Под степенью внутренней вершины понимается число ее непосредственных потомков. Если все вершины имеют одну и ту же степень, то она полагается степенью дерева. На самом деле, всегда можно добиться того, чтобы любая вершина дерева имела одну и ту же степень путем добавления специальных вершин в тех точках, где отсутствуют поддеревья (рисунок 4.4).
Число вершин (или ветвей), которые нужно пройти от корня к вершине x, называется длиной пути к вершине x. Высотой (или глубиной) дерева будем называть максимальную длину его вершины.
Рис. 4.4. 4.1.1. Двоичные деревья
Для организации поиска в основной памяти особое значение имеют упорядоченные двоичные (бинарные) деревья (как, например, на рисунке 4.3). В каждом таком дереве естественно определяются левое и правое поддеревья. Двоичное дерево называется идеально сбалансированным, если число вершин в его левом и правом поддеревьях отличается не более, чем на 1 (легко видеть, что при соблюдении этого условия длины пути до любой листовой вершины дерева отличаются не больше, чем на 1). Примеры идеально сбалансированных деревьев показаны на рисунке 4.5.
Рис. 4.5.
Рис. 4.6.
Двоичные деревья обычно представляются как динамические структуры (см. раздел 1.7) с базовым типом записи T, в число полей которого входят два указателя на переменные типа T.
При использовании в целях поиска элементов данных по значению уникального ключа применяются двоичные деревья поиска, обладающие тем свойством, что для любой вершины дерева значение ее ключа больше значения ключа любой вершины ее левого поддерева и больше значения ключа любой вершины правого поддерева (рисунок 4.6). Для поиска заданного ключа в дереве поиска достаточно пройти по одному пути от корня до (возможно, листовой) вершины (рисунок 4.7). Высота идеально сбалансированного двоичного дерева с n вершинами составляет не более, чем log n (логарифм двоичный), поэтому при применении таких деревьев в качестве деревьев поиска (рисунок 4.8) потребуется не более log n сравнений.
Рис. 4.7. Путь поиска ключа по значению “23”
Рис. 4.8. Идеально сбалансированное двоичное дерево
Применение деревьев как объектов с динамической структурой особенно полезно, если допускать выполнение не только операции поиска по значению ключа, но и операций включения новых и исключения существующих ключей. Если не принимать во внимание потенциальное желание поддерживать идеальную балансировку дерева, то процедуры включения и исключения ключей очень просты. Для включения в дерево вершины с новым ключом x по общим правилам поиска ищется листовая вершина, в которой находился бы этот ключ, если бы он входил в дерево. Возможны две ситуации: (a) такая вершина не существует; (b) вершина существует и уже занята, т.е. содержит некоторый ключ y. В первой ситуации создается недостающая вершина, и в нее заносится значение ключа x. Во второй ситуации после включения ключа x эта вершина в любом случае становится внутренней, причем если x > y, то ключ x заносится в новую листовую вершину - правого сына y, а если x есть дерево Фибоначчи высотой h;
(d) другие деревья Фибоначчи не существуют.
Примеры деревьев Фибоначчи высотой 2, 3 и 4 показаны на рисунке 4.11.
(а) Дерево Фибоначчи высотой 2
(b) Дерево Фибоначчи высотой 3
( c ) Дерево Фибоначчи высотой 4
Рис. 4.11. Примеры деревьев Фибоначчи
Число вершин в дереве Th определяется из следующего рекуррентного соотношения:
N0 = 0; N1 = 1; Nh = N(h-1) +1 + N(h-2)
Эти числа определяют число вершин в АВЛ-дереве в худшем случае и называются "числами Леонарда". Заметим, что из этого соотношения следует, что длина пути от корня любого листа в АВЛ-дереве может отличаться не более, чем на единицу.
Рассмотрим, как можно поддерживать балансировку АВЛ-дерева при выполнении операций включения и исключения ключей. Начнем с операции включения. Пусть рассматриваемое дерево состоит из корневой вершины r и левого (L) и правого (R) поддеревьев. Будем обозначать через hl высоту L, а через hr - высоту R. Для определенности будем считать, что новый ключ включается в поддерево L. Если высота L не изменяется, то не изменяются и соотношения между высотой L и R, и свойства АВЛ-дерева сохраняются. Если же при включении в поддерево L высота этого поддерева увеличивается на 1, то возможны следующие три случая:
(a) если hl = hr, то после добавления вершины L и R станут разной высоты, но свойство сбалансированности сохранится;
(b) если hl hr, то после включения ключа критерий сбалансированности нарушится, и потребуется перестройка дерева.
Имеет смысл рассмотреть две разные ситуа

сортировка бинарным деревом си

сортировка бинарным деревом c++

Сортированные бинарные деревья и Бинарный поиск. Пузырьковая сортировка. Категория B15. ЕГЭ по информатике и ИКТ 2014.

Читать

сортировка бинарным деревом c#

Сортировка с помощью двоичного дерева (пирамидальная) АЛГОРИТМ 1. Построение сортирующего дерева Вход: массив А[1n]. Выход