Двоичное дерево поиска

Рисунок 4. Пример КЧД

Вращения

Операции вставки и удаления вершин в КЧД могут нарушать свойства КЧД. Чтобы восстановить эти свойства, надо будет перекрашивать некоторые вершины и менять структуру дерева. Для изменения структуры используются операции, называемые вращением. Возвращая КЧД его свойства, вращения так же восстанавливают сбалансированность дерева. Вращения бывают левые и правые, их суть показана на рисунке 5.

Рисунок 5. Вращения левые и правые

Как видно, вращения, перемещая вершины, не нарушают свойства упорядоченности.[6]

В процедуре RBTLeftRotate предполагается, что node.right != NIL. В процедуре RBTRightRotate предполагается, что node.left != NIL.

Функция RBTInsert не так сложна, как кажется на первый взгляд. Рассмотрим её подробнее. После строк 3-4 выполняются все свойства КЧД, кроме, возможно, одного: у новой красной вершины может быть красный родитель. Такая ситуация (красная вершина имеет красного родителя) может сохраниться после любого числа итераций цикла. Внутри цикла рассматриваются 6 различных случаев, но три из них (строки 8-28) симметричны трём другим (строки 30-50), различие лишь в том, является ли родитель вершины node правым или левым потомком своего родителя (случаи разделяются в строке 7). Поэтому мы рассмотрим подробно только первые три случая (строки 8-28). Предположим, что во всех рассматриваемых КЧД корень чёрный, и будем поддерживать это свойство (строка 52). Поэтому в строке 5 node.nodeParent (красного цвета) не может быть корнем, и node.nodeParent.nodeParent != NIL. Операции внутри цикла начинаются с нахождения nodeTemp, “дяди” node, то есть вершины, имеющей того же родителя, что и node.nodeParent. Если nodeTemp – красная вершина, то имеет место случай 1, если черная, то 2 или 3. Во всех случаях вершина node.nodeParent.nodeParent – чёрная, так как пара node, node.nodeParent была единственным нарушением свойств КЧД.[7]

Случай 1 (строки 12-15 и 34-37) показан на рисунке 6. Является ли вершина node правым или левым потомком своего родителя, значения не имеет.

Рисунок 6. Случай 1

Обе вершины (node и nodeTemp) – красные, а вершина node.nodeParent.nodeParent – чёрная. Перекрасим node.nodeParent и nodeTemp в чёрный цвет, а node.nodeParent.nodeParent – в красный. При этом число чёрных вершин на любом пути от корня к листьям остаётся прежним. Нарушение свойств КЧД возможно лишь в одном месте: вершина node.nodeParent.nodeParent может иметь красного родителя, поэтому надо продолжить выполнение цикла, присвоив node значение node.nodeParent.nodeParent.

В случаях 2 и 3 вершина nodeTemp – чёрная. Различаются случаи, когда вершина node является правым или левым потомком своего родителя. Если правым, то это случай 2 (строки 20-23 и 41-45). В этом случае производится левое вращение, которое сводит случай 2 к случаю 3, когда node является левым потомком своего родителя. Так как node и node.nodeParent – красные, после вращения количество чёрных вершин на путях от корня к листьям остается прежним.[8]

Рисунок 7. Случай 2

Осталось рассмотреть случай 3: красная вершина node является левым потомком красной вершины node.nodeParent, которая, в свою очередь, является левым потомком node.nodeParent.nodeParent, правым потомком которой является nodeTemp. В этом случае достаточно произвести правое вращение и перекрасить две вершины. Цикл окончится, так как вершина node.nodeParent будет после этого чёрной.

ЗАКЛЮЧЕНИЕ

Двоичное дерево поиска (англ. binary search tree, BST) — это двоичное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):

 Оба поддерева — левое и правое, являются двоичными деревьями поиска.

 У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных узла X.

 У всех узлов правого поддерева произвольного узла X значения ключей данных не меньше, нежели значение ключа данных узла X.

Очевидно, данные в каждом узле должны обладать ключами, на которых определена операция сравнения меньше.

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

Для целей реализации двоичное дерево поиска можно определить так:

 Двоичное дерево состоит из узлов (вершин) — записей вида (data, left, right), где data — некоторые данные привязанные к узлу, left и right — ссылки на узлы, являющиеся детьми данного узла - левый и правый сыновья соответственно. Для оптимизации алгоритмов конкретные реализации предполагают также определения поля parent в каждом узле (кроме корневого) - ссылки на родительский элемент.

 Данные (data) обладают ключом (key), на котором определена операция сравнения "меньше". В конкретных реализациях это может быть пара (key, value) - (ключ и значение), или ссылка на такую пару, или простое определение операции сравнения на необходимой структуре данных или ссылке на неё.

 Для любого узла X выполняются свойства дерева поиска: key[left[X]] < key[X] ≤ key[right[X]], т. е. ключи данных родительского узла больше ключей данных левого сына и нестрого меньше ключей данных правого.

Двоичное дерево поиска не следует путать с двоичной кучей, построенной по другим правилам.

Основным преимуществом двоичного дерева поиска перед другими структурами данных является возможная высокая эффективность реализации основанных на нём алгоритмов поиска и сортировки.

Двоичное дерево поиска применяется для построения более абстрактных структур, таких как множества, мультимножества, ассоциативные массивы.

СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

1.      Муравьев, И.В. Структура данных в предметной области / И.В. Муравьев.- М.: Экономист, 2009.- 467с.

2.      Негашев, Е.В. Структура данных: Учебное пособие/ Е.В. Негашев. - М.: Высшая школа, 2009. – 259 с.

3.      Носов, А.Ю. Структура данных / А.Ю. Носов.- М.: Инфра-М, 2009.- 789с.

4.      Павлова, Л.Н. Программирование на языке высокого уровня: Учебник для вузов/Л.Н. Павлова. – М.: Финансы, ЮНИТИ, 2009. – 261 с.

5.      Папирян, Г.А. Структурное программирование / Г.А. Папирян. -М.: Экономика, 2009. - 207 с.

6.      Савицкая, Г.В. Основные концепции структур данных и реализация / Г.В. Савицкая.- М.: Экономистъ, 2009. – 356с.

7.      Савицкая, Г.В. Алгоритмы и структуры данных: Учебное пособие/ Г.В. Савицкая. – Москва: Инфра-М , 2009. – 468 с.

8.      Соболева е.а. Структуры данных и другие объекты: Учебно-методическое пособие/ Е.А. Соболева.- М.: Финансы и статистика, 2009. - 128 с.

9.      Тишкова, И.Е. Алгоритмы и структуры данных / И.Е.Тишкова. – Мн.: Выш.шк., 2010. - 542с.

10. Тренев, Н.Н. Структура данных / Н.Н. Тренев.- М.: Финансы и статистика, 2009. – 623с.

[1] Муравьев, И.В. Структура данных в предметной области / И.В. Муравьев.- М.: Экономист, 2009.- С. 89.

[2] Негашев, Е.В. Структура данных: Учебное пособие/ Е.В. Негашев. - М.: Высшая школа, 2009. – С. 39.

[3] Носов, А.Ю. Структура данных / А.Ю. Носов.- М.: Инфра-М, 2009.- С. 99.

[4] Павлова, Л.Н. Программирование на языке высокого уровня: Учебник для вузов/Л.Н. Павлова. – М.: Финансы, ЮНИТИ, 2009. – С. 12.

[5] Папирян, Г.А. Структурное программирование / Г.А. Папирян. -М.: Экономика, 2009. – С. 11.

[6] Савицкая, Г.В. Основные концепции структур данных и реализация / Г.В. Савицкая.- М.: Экономистъ, 2009. – С. 93.

[7] Савицкая, Г.В. Алгоритмы и структуры данных: Учебное пособие/ Г.В. Савицкая. – Москва: Инфра-М , 2009. – С. 89.

[8] Тренев, Н.Н. Структура данных / Н.Н. Тренев.- М.: Финансы и статистика, 2009. – С. 23.