Аналогия с B-деревом с параметром 2
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
«КАБАРДИНО-БАЛКАРСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ им. Х. М. БЕРБЕКОВА»
Институт информатики, электроники и компьютерных технологий
Кафедра информатики и технологий программирования
Дисциплина: Алгоритмы и структуры данных
КУРСОВАЯ РАБОТА
На тему
«Алгоритмы сортировки. Внутренняя сортировка»
Выполнил:
студент 2 курса,
ИВТ (ПОСВТиАС)
Аюбов Т.А.
Проверил:
преподаватель кафедры ИТП
Арванова М.М.
Нальчик 2017
СОДЕРЖАНИЕ
1. Введение
1,1Анализ предметной области
1,2Терминология
1.3Свойства
1.4Аналогия с B-деревом с параметром 2
1.5Работа с красно-чёрными деревьями
1.5.1Операции
1.5.2Вставка
1.5.3Удаление
1.6Доказательство асимптотических границ
2.Язык c++
3. Реализация красно-черного дерева наязыке c++
4.Заключение
5.Список использованных источников
Введение
Красно-чёрное дерево — это одно из самобалансирующихся двоичных деревьев поиска, гарантирующих логарифмический рост высоты дерева от числа узлов и быстро выполняющее основные операции дерева поиска: добавление, удаление и поиск узла. Сбалансированность достигается за счёт введения дополнительного атрибута узла дерева — «цвета». Этот атрибут может принимать одно из двух возможных значений — «чёрный» или «красный».
Изобретателем красно-чёрного дерева считают немца Рудольфа Байера. Название «красно-чёрное дерево» структура данных получила в статье Л. Гимпаса и Р. Седжвика (1978). В журнале были доступны две краски (красная и чёрная)[1] и дополнительный бит, «прикреплявшийся» к каждому из узлов, обозначался цветом.
|
|
|
Терминология
Красно-чёрное дерево является особым видом двоичного дерева, используемым в информатике для организации сравнимых данных, таких как фрагменты текста или числа. Листовые узлы красно-чёрных деревьев не содержат данных. Такие листья не нуждаются в явном выделении памяти — нулевой указатель на потомка может фактически означать, что этот потомок — листовой узел, но в некоторых случаях работы с красно-чёрными деревьями использование явных листовых узлов может послужить упрощением алгоритма.
Свойства
Пример красно-чёрного дерева
Красно-чёрное дерево — двоичное дерево поиска, в котором каждый узел имеет атрибут цвет, принимающий значения красный или чёрный. В дополнение к обычным требованиям, налагаемым на двоичные деревья поиска, к красно-чёрным деревьям применяются следующие требования:
Узел либо красный, либо чёрный.
Корень — чёрный. (В других определениях это правило иногда опускается.Это правило слабо влияет на анализ, так как корень всегда может быть изменен с красного на чёрный, но не обязательно наоборот).
|
|
|
Все листья (NIL) — чёрные.
Оба потомка каждого красного узла — чёрные.
Всякий простой путь от данного узла до любого листового узла, являющегося его потомком, содержит одинаковое число чёрных узлов.
Эти ограничения реализуют критическое свойство красно-чёрных деревьев: путь от корня до самого дальнего листа не более чем в два раза длиннее пути от корня до ближайшего листа (если дальний лист расположен на 3-м уровне). Результатом является то, что дерево примерно сбалансировано. Так как такие операции как вставка, удаление и поиск значений требуют в худшем случае времени, пропорционального длине дерева, эта теоретическая верхняя граница высоты позволяет красно-чёрным деревьям быть более эффективными в худшем случае, чем обычные двоичные деревья поиска.
Чтобы понять, почему это гарантируется, достаточно рассмотреть эффект свойств 4 и 5 вместе. Пусть для красно-чёрного дерева T число чёрных узлов в свойстве 5 равно B. Тогда кратчайший возможный путь от корня дерева T до любого листового узла содержит B чёрных узлов. Более длинный возможный путь может быть построен путём включения красных узлов. Однако, свойство 4 не позволяет вставить несколько красных узлов подряд. Поэтому самый длинный возможный путь состоит из 2B узлов, попеременно красных и чёрных. Любой максимальный путь имеет одинаковое число чёрных узлов (по свойству 5), следовательно, не существует пути, более чем вдвое длинного, чем любой другой путь.
|
|
|
Во многих реализациях структуры дерева возможно, чтобы узел имел только одного потомка и листовой узел содержал данные. В этих предположениях реализовать красно-чёрное дерево возможно, но изменятся несколько свойств и алгоритм усложнится. По этой причине данная статья использует «фиктивные листовые узлы», которые не содержат данных и просто служат для указания, где дерево заканчивается. Эти узлы часто опускаются при графическом изображении, в результате дерево выглядит противоречиво с вышеизложенными принципами, но на самом деле противоречия нет. Следствием этого является то, что все внутренние (не являющиеся листовыми) узлы имеют два потомка, хотя один из них может быть нулевым листом. Свойство 5 гарантирует, что красный узел обязан иметь в качестве потомков либо два чёрных нулевых листа, либо два чёрных внутренних узла. Для чёрного узла с одним потомком нулевым листовым узлом и другим потомком, не являющимся таковым, свойства 3, 4 и 5 гарантируют, что последний должен быть красным узлом с двумя чёрными нулевыми листьями в качестве потомков.
|
|
|
Иногда красно-чёрное дерево трактуют как бинарное дерево поиска, у которого вместо узлов в красный и чёрный цвета раскрашены ребра, но это не имеет какого-либо значения. Цвет узла в терминах данной статьи соответствует цвету ребра, соединяющего узел со своим предком, за исключением того, что корневой узел всегда чёрный (свойство 2), в то время как соответствующее ребро не существует.
Аналогия с B-деревом с параметром 2
То же самое красно-чёрное дерево, что и в примере выше, представленное как B-дерево.
Красно-чёрное дерево схоже по структуре с B-деревом с параметром 2, в котором каждый узел может содержать от 1 до 3 значений и, соответственно, от 2 до 4 указателей на потомков. В таком В-дереве каждый узел будет содержать только одно значение, соответствующее значению чёрного узла красно-чёрного дерева с необязательным значениями до и/или после него в том же узле, оба из которых соответствуют эквивалентным красным узлам красно-чёрного дерева.
Один из способов увидеть эту эквивалентность — «поднять» красные узлы в графическом представлении красно-чёрного дерева так, чтобы они оказались на одном уровне по горизонтали со своими предками чёрными узлами, образуя страницу. В В-дереве, или в модифицированном графическом представлении красно-чёрного дерева, у всех листовых узлов глубина одинаковая.
Этот тип В-дерева является более общим, чем красно-чёрное дерево, хотя, как видно, из одного такого В-дерева с параметром 2 могут быть получены несколько красно-чёрных деревьев. Если страница В-дерева содержит только одно значение, данный узел чёрный и имеет двух потомков. Если страница содержит три значения, то центральный узел является чёрным, а каждый его сосед — красным. Однако, если страница содержит два значения, любой узел может стать чёрным в красно-чёрном дереве (и тогда второй будет красным).
Дата добавления: 2018-02-15; просмотров: 664; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!