Структуры данных. 3
17
СОДЕРЖАНИЕ
Стр.
Введение
1.Понятие двоичного дерева поиска
2.Основные операции двоичного дерева поиска
3.Основная проблема использования двоичного дерева поиска 10
Заключение
Список используемых источников
ВВЕДЕНИЕ
Дерево — это совокупность элементов, называемых узлами (при этом один из них определен как корень), и отношений (родительский–дочерний), образующих иерархическую структуру узлов. Узлы могут являться величинами любого простого или структурированного типа, за исключением файлового. Узлы, которые не имеют ни одного последующего узла, называются листьями.
В двоичном (бинарном) дереве каждый узел может быть связан не более чем двумя другими узлами. Рекурсивно двоичное дерево определяется так: двоичное дерево бывает либо пустым (не содержит ни одного узла), либо содержит узел, называемый корнем, а также два независимых поддерева — левое поддерево и правое поддерево.
Двоичное дерево поиска может быть либо пустым, либо оно обладает таким свойством, что корневой элемент имеет большее значение узла, чем любой элемент в левом поддереве, и меньшее или равное, чем элементы в правом поддереве. Указанное свойство называется характеристическим свойством двоичного дерева поиска и выполняется для любого узла такого дерева, включая корень. Далее будем рассматривать только двоичные деревья поиска. Такое название двоичные деревья поиска получили по той причине, что скорость поиска в них примерно такая же, что и в отсортированных массивах: O(n) = C • log2n (в худшем случае O(n) = n).
Объектом работы является двоичное дерево поиска, а предметом – особенности двоичного дерева поиска.
Цель работы – исследование особенности двоичного дерева поиска.
Поставленная цель определяет задачи исследования:
- рассмотреть понятие двоичного дерева поиска;
- исследовать основные операции двоичного дерева поиска;
- охарактеризовать основную проблему использования двоичного дерева поиска.
Работа состоит из введения, трех глав, заключения, списка используемых источников.
1.Понятие двоичного дерева поиска
Двоичным деревом поиска (ДДП) называют дерево, все вершины которого упорядочены, каждая вершина имеет не более двух потомков (назовём их левым и правым), и все вершины, кроме корня, имеют родителя. Вершины, не имеющие потомков, называются листами. Подразумевается, что каждой вершине соответствует элемент или несколько элементов, имеющие некие ключевые значения, в дальнейшем именуемые просто ключами. Обычно одной вершине соответствует один элемент, поэтому данные термины можно без потери смысла считать синонимами, хотя и надо помнить, что в некоторых реализациях это не так.[1]
В приведённых алгоритмах считается, что одной вершине соответствует только один элемент. Поэтому мы будем использовать понятия ключа вершины и данных вершины, подразумевая ключ и данные соответствующего вершине элемента. Мы так же будем понимать под вставкой вершины добавление вершины с указанным значением элемента и присвоение указателям на родителя и потомков корректных значений. Именно ключ используется во всех операциях сравнения элементов. Элемент может также содержать ассоциированные с ключом данные. На практике в качестве ключа может использоваться часть данных элемента. Ключ также может храниться как отдельное значение.
2.Основные операции двоичного дерева поиска
ДДП позволяет выполнять следующие основные операции:
Поиск вершины по ключу.
Определение вершин с минимальным и максимальным значением ключа.
Переход к предыдущей или последующей вершине, в порядке, определяемом ключами.
Вставка вершины.
Удаление вершины.[2]
Двоичное дерево может быть логически разбито на уровни. Корень дерева является нулевым уровнем, потомки корня – первым уровнем, их потомки – вторым, и т.д. Глубина дерева это его максимальный уровень. Понятие глубины также может быть описано в терминах пути, то есть глубина дерева есть длина самого длинного пути от корня до листа, если следовать от родительской вершины до потомка. Каждую вершину дерева можно рассматривать как корень поддерева, которое определяется данной вершиной и всеми потомками этой вершины, как прямыми, так и косвенными. Поэтому о дереве можно говорить как о рекурсивной структуре. Эффективность поиска по дереву напрямую связана с его сбалансированностью, то есть с максимальной разницей между глубиной левого и правого поддерева среди всех вершин. Имеется два крайних случая – сбалансированное бинарное дерево (где каждый уровень имеет полный набор вершин) и вырожденное дерево, где на каждый уровень приходится по одной вершине. Вырожденное дерево эквивалентно связанному списку. Время выполнения всех основных операций пропорционально глубине дерева. Таким образом, скоростные характеристики поиска в ДДП могут варьироваться от O(log2N) в случае законченного дерева до O(N) – в случае вырожденного.
ДДП может быть использовано для реализации таких абстракций, как сортированный список, словарь (набор соответствий "ключ-значение"), очередь с приоритетами и так далее.
При реализации дерева помимо значения ключа (key) и данных также хранятся три указателя: на родителя (net), левого (left) и правого (right) потомков. Если родителя или потомка нет, то указатель хранит нулевое (NULL, NIL) значение.[3]
Свойство упорядоченности двоичного дерева поиска
Если x – это произвольная вершина в ДДП, а вершина y находится в левом поддереве вершины x, то y.key <= x.key. Если x – это произвольная вершина ДДП, а вершина y находится в правом поддереве вершины x, то y.key >= x.key. Из свойства следует, что если y.key == x.key, то вершина y может находиться как в левом, так и в правом поддереве относительно вершины x.
Необходимо помнить, что при наличии нескольких вершин с одинаковыми значениями ключа некоторые алгоритмы не будут работать правильно. Например, алгоритм поиска будет всегда возвращать указатель только на одну вершину. Эту проблему можно решить, храня элементы с одинаковыми ключами в одной и той же вершине в виде списка. В таком случае мы будем хранить в одной вершине несколько элементов, но данный случай в статье не рассматривается.
Это двоичное дерево поиска:
Рисунок 1. Двоичное дерево поиска
А это нет:
Рисунок 2.
Способы обхода ДДП
Есть три способа обхода: Прямой (preorder), Поперечный (inorder), Обратный (postorder).
Прямой обход: сначала обходится данная вершина, левое поддерево данной вершины, затем правое поддерево данной вершины.
Поперечный обход: сначала обходится левое поддерево данной вершины, затем данная вершина, затем правое поддерево данной вершины. Вершины при этом будут следовать в неубывающем (по ключам key) порядке.
Обратный обход: сначала обходится левое поддерево данной вершины, затем правое, затем данная вершина.
На рисунке 3 порядок обхода вершин указан номерами, при этом предполагается, что сами вершины расположены так, что образуют ДДП.
Рисунок 3. Способы обхода ДДП
Наиболее часто употребляется поперечный обход, так как во всех других способах обхода следующие друг за другом вершины не связаны никакими условиями отношения.
Поиск вершины в ДДП
Идея поиска проста. Алгоритм поиска в ДДП по своей природе рекурсивен. При его описании проще всего использовать понятие поддерева. Поиск начинается с корня дерева, который принимается за корень текущего поддерева, и его ключ сравнивается с искомым. Если они равны, то, очевидно, поиск закончен. Если ключ, который мы ищем, оказался больше текущего, то, очевидно, что нужная вершина находится в правом поддереве, иначе – в левом.[4]
Проблемы возникают и при удалении. Нам необходимо сохранить свойство упорядоченности ДДП. При удалении возможны три случая: у удаляемой вершины нет потомков, у удаляемой вершины есть один потомок и у удаляемой вершины два потомка. Если потомков нет, то вершину можно просто удалить. Если потомок один, то удаляемую вершину можно “вырезать”, указав её родителю в качестве потомка единственного имеющегося потомка удаляемой вершины. Если же потомков два, требуются дополнительные действия. Нужно найти следующую за удаляемой (по порядку ключей) вершину, скопировать её содержимое (ключ и данные) в удаляемую вершину (она теперь никуда не удаляется физически, хотя логически исчезает) и удалить найденную вершину (у неё не будет левого потомка). Сначала функция TreeDelete ищет вершину, которую надо удалить, затем переменной nodeTemp присваивается указатель на существующего потомка удаляемой вершины (или NIL, если потомков нет). Далее вершина удаляется из дерева, при этом отдельно рассматриваются случаи: когда потомков нет и когда удаляемая вершина – это корень дерева.
3. Основная проблема использования двоичного дерева поиска
Основной проблемой использования ДДП является то, что методы вставки и удаления вершин, гарантируя сохранение свойства упорядоченности, совершенно не способствуют оптимизации основных операций над ДДП. Например, если вставить в ДДП последовательность возрастающих или убывающих чисел, оно превратится, по сути, в двусвязный список, а основные операции будут занимать время, пропорциональное количеству вершин, а не его логарифму.
Таким образом, для получения производительности порядка O(log2N) нужно, чтобы дерево имело как можно более высокую сбалансированность (то есть имело возможно меньшую высоту). Обычно выделяются несколько типов сбалансированности. Полная сбалансированность, это когда для каждой вершины дерева количества вершин в левом и правом поддеревьях различаются не более чем на 1. К сожалению, такой сбалансированности трудно добиться на практике. Поэтому на практике используются менее жесткие виды сбалансированности. Например, русскими математиками Г. М. Адельсон-Вельским и Е.М.Ландисом были разработаны принципы АВЛ деревьев. В АВЛ деревьях для каждой вершины дерева глубины обоих поддеревьев различаются не более чем на 1. Еще одним “продвинутым” видом деревьев является так называемые красно-чёрные деревья. АВЛ деревья обеспечивают более высокую сбалансированность дерева, но затраты на их поддержание выше. Поскольку на практике разница в сбалансированности между этими двумя видами деревьев не высока, чаще используются красно-чёрные деревья.[5]
Итак, одним из способов решения основной проблемы использования ДДП являются красно-чёрные деревья. Красно-чёрные (название исторически связано с игральными картами, поскольку из них легко делать простые модели) деревья (КЧД) – это ДДП, каждая вершина которых хранит ещё одно дополнительное логическое поле (color), обозначающее цвет: красный или чёрный. Фактически, в КЧД гарантируется, что уровни любых двух листьев отличаются не более, чем в два раза. Этого условия оказывается достаточно, чтобы обеспечить скоростные характеристики поиска, близкие к O(log2N). При вставке/замене производятся дополнительные действия по балансировке дерева, которые не могут не замедлить работу с деревом. При описании алгоритмов мы будем считать, что NIL – это указатель на фиктивную вершину, и операции (NIL).left, (NIL).right, (NIL).color имеют смысл. Мы также будем полагать, что каждая вершина имеет двух потомков, и лишь NIL не имеет потомков. Таким образом, каждая вершина становится внутренней (имеющей потомков, пусть и фиктивных), а листьями будут лишь фиктивные вершины NIL.
Каждая вершина может быть либо красной, либо чёрной. Бесцветных вершин, или вершин другого цвета быть не может.
Каждый лист (NIL) имеет чёрный цвет.
Если вершина красная, то оба её потомка – чёрные.
Все пути от корня к листьям содержат одинаковое число чёрных вершин.
Пример КЧД с учётом наших положений приведен на рисунке 4. Учтите, что вершина 9 могла быть и красной, но в дальнейшем мы будем рассматривать только те деревья, у которых корень чёрный. Мы это сделаем для того, чтобы потомки корня могли иметь любой цвет.
Рисунок 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.
