Что такое красно черное дерево
Перейти к содержимому

Что такое красно черное дерево

  • автор:

Что такое красно черное дерево

Красно-черные деревья — один из способов балансировки деревьев. Название происходит от стандартной раскраски узлов таких деревьев в красный и черный цвета. Цвета узлов используются при балансировке дерева. Во время операций вставки и удаления поддеревья может понадобиться повернуть, чтобы достигнуть сбалансированности дерева. Оценкой как среднего время, так и наихудшего является O (log n ).

Прекрасно написанные разделы о красно-черных деревьях вы найдете у Кормена-Ривеста-Лейзертона в их талмуде об алгоритмах.

  • Каждый узел покрашен либо в черный, либо в красный цвет.
  • Листьями объявляются NIL -узлы (т.е. «виртуальные» узлы, наследники узлов, которые обычно называют листьями; на них «указывают» NULL указатели). Листья покрашены в черный цвет.
  • Если узел красный, то оба его потомка черны.
  • На всех ветвях дерева, ведущих от его корня к листьям, число черных узлов одинаково.


    Красный предок, красный «дядя» : Ситуацию красный-красный иллюстрирует рис. 1. У нового узла X предок и «дядя» оказались красными. Простое перекрашивание избавляет нас от красно-красного нарушения. После перекраски нужно проверить «дедушку» нового узла (узел B ), поскольку он может оказаться красным. Обратите внимание на распространение влияния красного узла на верхние узлы дерева. В самом конце корень мы красим в черный цвет корень дерева. Если он был красным, то при этом увеличивается черная высота дерева.


Рис. 1: Вставка — Красный предок, красный «дядя
Рис. 2: Вставка — красный предок, черный «дядя»

Функция insertNode запрашивает память под новый узел, устанавливает нужные значения его полей и вставляет в дерево. Соответственно, она вызывает insertFixup , которая следит за сохранением красно-черных свойств. Функция deleteNode удаляет узел из дерева. Она вызывает deleteFixup , которая восстанавливает красно-черные свойства. Функция findNode ищет в дереве нужный узел.

/* red-black tree */ #include #include #include #include typedef int T; /* type of item to be stored */ #define compLT(a,b) (a < b) #define compEQ(a,b) (a == b) /* Red-Black tree description */ typedef enum < BLACK, RED >nodeColor; typedef struct Node_ < struct Node_ *left; /* left child */ struct Node_ *right; /* right child */ struct Node_ *parent; /* parent */ nodeColor color; /* node color (BLACK, RED) */ T data; /* data stored in node */ > Node; #define NIL &sentinel /* all leafs are sentinels */ Node sentinel = < NIL, NIL, 0, BLACK, 0>; Node *root = NIL; /* root of Red-Black tree */ void rotateLeft(Node *x) < /************************** * rotate node x to left * **************************/ Node *y = x->right; /* establish x->right link */ x->right = y->left; if (y->left != NIL) y->left->parent = x; /* establish y->parent link */ if (y != NIL) y->parent = x->parent; if (x->parent) < if (x == x->parent->left) x->parent->left = y; else x->parent->right = y; > else < root = y; >/* link x and y */ y->left = x; if (x != NIL) x->parent = y; > void rotateRight(Node *x) < /**************************** * rotate node x to right * ****************************/ Node *y = x->left; /* establish x->left link */ x->left = y->right; if (y->right != NIL) y->right->parent = x; /* establish y->parent link */ if (y != NIL) y->parent = x->parent; if (x->parent) < if (x == x->parent->right) x->parent->right = y; else x->parent->left = y; > else < root = y; >/* link x and y */ y->right = x; if (x != NIL) x->parent = y; > void insertFixup(Node *x) < /************************************* * maintain Red-Black tree balance * * after inserting node x * *************************************/ /* check Red-Black properties */ while (x != root && x->parent->color == RED) < /* we have a violation */ if (x->parent == x->parent->parent->left) < Node *y = x->parent->parent->right; if (y->color == RED) < /* uncle is RED */ x->parent->color = BLACK; y->color = BLACK; x->parent->parent->color = RED; x = x->parent->parent; > else < /* uncle is BLACK */ if (x == x->parent->right) < /* make x a left child */ x = x->parent; rotateLeft(x); > /* recolor and rotate */ x->parent->color = BLACK; x->parent->parent->color = RED; rotateRight(x->parent->parent); > > else < /* mirror image of above code */ Node *y = x->parent->parent->left; if (y->color == RED) < /* uncle is RED */ x->parent->color = BLACK; y->color = BLACK; x->parent->parent->color = RED; x = x->parent->parent; > else < /* uncle is BLACK */ if (x == x->parent->left) < x = x->parent; rotateRight(x); > x->parent->color = BLACK; x->parent->parent->color = RED; rotateLeft(x->parent->parent); > > > root->color = BLACK; > Node *insertNode(T data) < Node *current, *parent, *x; /*********************************************** * allocate node for data and insert in tree * ***********************************************/ /* find where node belongs */ current = root; parent = 0; while (current != NIL) < if (compEQ(data, current->data)) return (current); parent = current; current = compLT(data, current->data) ? current->left : current->right; > /* setup new node */ if ((x = malloc (sizeof(*x))) == 0) < printf ("insufficient memory (insertNode)\n"); exit(1); >x->data = data; x->parent = parent; x->left = NIL; x->right = NIL; x->color = RED; /* insert node in tree */ if(parent) < if(compLT(data, parent->data)) parent->left = x; else parent->right = x; > else < root = x; >insertFixup(x); return(x); > void deleteFixup(Node *x) < /************************************* * maintain Red-Black tree balance * * after deleting node x * *************************************/ while (x != root && x->color == BLACK) < if (x == x->parent->left) < Node *w = x->parent->right; if (w->color == RED) < w->color = BLACK; x->parent->color = RED; rotateLeft (x->parent); w = x->parent->right; > if (w->left->color == BLACK && w->right->color == BLACK) < w->color = RED; x = x->parent; > else < if (w->right->color == BLACK) < w->left->color = BLACK; w->color = RED; rotateRight (w); w = x->parent->right; > w->color = x->parent->color; x->parent->color = BLACK; w->right->color = BLACK; rotateLeft (x->parent); x = root; > > else < Node *w = x->parent->left; if (w->color == RED) < w->color = BLACK; x->parent->color = RED; rotateRight (x->parent); w = x->parent->left; > if (w->right->color == BLACK && w->left->color == BLACK) < w->color = RED; x = x->parent; > else < if (w->left->color == BLACK) < w->right->color = BLACK; w->color = RED; rotateLeft (w); w = x->parent->left; > w->color = x->parent->color; x->parent->color = BLACK; w->left->color = BLACK; rotateRight (x->parent); x = root; > > > x->color = BLACK; > void deleteNode(Node *z) < Node *x, *y; /***************************** * delete node z from tree * *****************************/ if (!z || z == NIL) return; if (z->left == NIL || z->right == NIL) < /* y has a NIL node as a child */ y = z; > else < /* find tree successor with a NIL node as a child */ y = z->right; while (y->left != NIL) y = y->left; > /* x is y's only child */ if (y->left != NIL) x = y->left; else x = y->right; /* remove y from the parent chain */ x->parent = y->parent; if (y->parent) if (y == y->parent->left) y->parent->left = x; else y->parent->right = x; else root = x; if (y != z) z->data = y->data; if (y->color == BLACK) deleteFixup (x); free (y); > Node *findNode(T data) < /******************************* * find node containing data * *******************************/ Node *current = root; while(current != NIL) if(compEQ(data, current->data)) return (current); else current = compLT (data, current->data) ? current->left : current->right; return(0); > void main(int argc, char **argv) < int a, maxnum, ct; Node *t; /* command-line: * * rbt maxnum * * rbt 2000 * process 2000 records * */ maxnum = atoi(argv[1]); for (ct = maxnum; ct; ct--) < a = rand() % 9 + 1; if ((t = findNode(a)) != NULL) < deleteNode(t); >else < insertNode(a); >> >

Понимаем красно-черное дерево. Часть 1. Введение

Довольно долгое время я воевал с красно-черным деревом (далее — кчд). Вся информация, которую я находил, была в духе «листья и корень дерева всегда черные, ПОТОМУ ЧТО», «топ 5 свойств красно-черного дерева» или «3 случая при балансировке и 12 случаев при удалении ноды». Такой расклад меня не устраивал.

Мне не хотелось заучивать свойства дерева, псевдокод и варианты балансировки, я хотел знать: почему. Каким образом цвета помогают при балансировке? Почему у красной ноды не может быть красного потомка? Почему глубину дерева измеряют «черной высотой»?

Ответы на эти вопросы я получил только тогда, когда мне дали ссылку на лекцию про два-три дерево, с которого мы и начнем.

Эта статья разделена на 3 логические части. Я рекомендую прочитать их в указанном порядке. Первая часть (данная) будет направлена на введение в кчд и знакомство с ним. Во второй части мы поговорим о балансировке и вставке в кчд. В третьей, завершающей, части мы разберем процесс удаления ноды. Наберитесь терпения и приятного чтения:)

  1. В этой статье не будет информации про плюсы и минусы дерева, его применение и т.д.: информации об асимптотике дерева и работе с ним в интернете полно.
  2. Материал предназначен для тех, кто уже знаком с кчд и теперь хочет их понять, а также для тех, кто только знакомится с ними.
  3. Статья не будет содержать деталей реализации структуры.
  4. Можно считать что эта статья — перевод английского видео материала в упрощенный русский текстовый вариант. Все ссылки я оставляю в конце статьи.

Два-три дерево

Чтобы понять красно-черное дерево, нужно понять два-три дерево

Забегая вперед, скажу, что два-три дерево — это, по сути, родитель нашего кчд, поэтому важно начать именно с него. Поймем два-три дерево — поймем и кчд.

Два-три дерево — абстрактный тип данных, напоминающий по структуре дерево. В нодах два-три дерева может быть одно или два значения и два или три потомка (от чего зависит количество значений и потомков ноды, узнаем ниже). Ноду с одним значением и двумя потомками будем называть 2-нода, ноду с двумя значениями и тремя потомками — 3-нода. Объяснение я начну с создания такого дерева: это наглядно и просто. Но некоторые уточнения нужны все же вначале:

  1. Добавляя элемент, мы всегда спускаемся вниз по дереву.
  2. Дерево отсортировано классически — меньшие значения находятся слева, бОльшие — справа.
  3. Два-три дерево — отсортированное, сбалансированное дерево.

Итак, начнем с первой ноды, это число 5. Тут все просто — 5 становится корнем.

Добавим число 12. Число 12 мы так же добавляем в корень (помним, что нода может иметь два значения), но теперь нам нужно «отсортировать» нашу ноду (сортировать два элемента, ха), т.е. уложить их в порядке возрастания. В итоге получается нода 5-12.

Добавим следующее число. Пусть это будет 17. Давайте пока добавим наш элемент в единственную ноду и снова отсортируем ее. Получилась нода 5-12-17.

Внимательный читатель заметит тут подвох — выше я говорил о том, что наши ноды могут содержать не более двух элементов. Вот тут и происходит магия! Мы берем средний элемент нашей ноды и «просачиваем» его наверх. Итог виден на картинке. Корнем стало число 12, левым сыном число 5, правым — 17.

То, что мы сделали выше, можно назвать балансировкой два-три дерева. Правило в этой балансировке простое: если в ноде оказывается три значения, среднее значение мы «просачиваем» вверх. Алгоритм действий зависит от 3 условий:

  1. Нода является корнем. Тогда ничего не остается, как создать новую ноду с одним значением и сделать ее новым корнем (как в нашем случае).
  2. Родительская нода имеет одно значение. Тогда мы просто добавляем значение к родителю и завершаем балансировку (при этом у родителя появляется третий потомок).
  3. Родительская нода имеет два значения. Тогда мы снова просачиваем значение вверх, пока не придем к пункту один или два.

Второй и третий случай балансировки будут рассмотрены ниже.

Окей, идем дальше. Давайте добавим число 3. Так как теперь мы не ограничиваемся одной нодой, спускаемся вниз. Понятно, что спуститься надо влево и добавить 3 к ноде со значением 5. Не забываем расставить 3 и 5 в нужном порядке. В итоге получилась нода 3-5.

Потерпите, мы близимся к самому интересному:)

Давайте добавим число 4 которое также пойдет влево и присоединится к ноде 3-5. Получится нода 3-4-5, которую, как мы уже знаем, нужно привести к нужному виду. Что делаем? Балансируем наше дерево, т.е. «просачиваем» значение 4 наверх.

Теперь самое интересное. Помимо того, что мы добавим 4 к корню, мы так же добавим корню третьего потомка — это будет нода, которая была больше 4. В нашем случае это 5. Картина будет выглядеть так:

Почему 5 не могла остаться на месте в своей ноде? Тут мы вспоминаем правило отсортированного дерева: значения меньше — слева, значения больше — справа. И так как 5 больше 4, мы не можем оставить 5 слева, т.к. это нарушит наш инвариант. Поэтому ноде со значением 5 ничего не остается, как «переехать», и стать потомком ноды 4-12 (кстати, если бы у 5 были потомки, они так же «переехали» бы вместе с родителем).

Тут нужно сделать небольшую паузу и объяснить, как ориентироваться в нодах с тремя потомками. Все просто:

  1. Значение, что меньше левого значения в ноде, будет левым потомком.
  2. Значение, что больше левого, но меньше правого значения в ноде, будет средним потомком.
  3. Значение, что больше правого значения в ноде, будет правым потомком.

А теперь посмотрите на то, что получилось. Смело можно заявить, что это отсортированное, сбалансированное два-три дерево. Значения меньше лежат слева, значения больше — справа (тут, как и в случае со значениями 4-5-12, мы считаем, что 5 лежит справа от 4 и слева от 12). Корень имеет два значения и три потомка, что абсолютно соответствует описанию дерева выше. Сейчас вы можете сами попробовать добавить любое значение, чтобы удостовериться, что вы поняли логику (что произойдет с деревом, если добавить значение 7? А затем 9?).

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

Главный минус такой структуры в том, что она, в отличие от бинарного дерева, неудобна в реализации. Нужно следить за количеством потомков и значением, плюс за их порядком, балансировкой (и это я еще не говорил про удаление). Красно-черное дерево решает эту проблему.

Красно-черное дерево

Как мы выяснили, главный недостаток два-три дерева — его структура. Тогда давайте попробуем превратить два-три дерево в дерево бинарное. Как мы можем сделать это?

Чтобы добиться этого, нам нужно простое представление для 3-ноды. Давайте разделим 3-ноду на две 2-ноды и свяжем их ссылками. Пометим эти ссылки каким-нибудь свойством, например, цветом, (возьмём красный), чтобы отличать такие ссылки в дереве от всех остальных.

Вообще говоря, мы не можем пометить сами ссылки, поэтому мы помечаем ноды.

Итак, перед вами красно-черное дерево. Далее, мы разберем несколько свойств кчд, которые я считаю важными (но я думаю, что уже из прочитанного выше многое стало ясно).

Свойства красно-черного дерева

Фактически мы разбираем не просто кчд, а левосторонне кчд — одна из имплементаций кчд, в которой красные ноды могут находится только слева, то есть от 3-ноды мы всегда отделям значение меньше (что и было сделано выше). По сути своей левостороннее кчд ничем не отличается от обычного, за исколючением того, что это более простая и понятная имплементация. Аналогично левостороннему кчд, существует и правостороннее кчд(логику его додумайте сами).

Свойство 1.

Две красные ноды не могут идти подряд. Это свойство приобретает смысл, если мы знаем, что красная нода — это по сути часть 3-ноды в 2-3 дереве. Ну а если две красные ноды идут подряд, то получается 4-нода, которой у нас не существует:)

Свойство 2.

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

Свойство 3.

Все null-ноды (ноды, которые не имеют потомков) — черные. Почему именно так, для себя объяснений я не нашел. Но хочу сказать, что это довольно удобное правило, когда дело доходит до балансировки дерева.

Раз уж мы затронули null-ноды, то стоит сказать, что в дереве у всех нод всегда должно быть два потомка, а если ссылка на потомка нулевая, то ведет она как раз в null-ноду. На самом деле, тут встает вопрос в реализации, мне было удобнее добавлять null-ноду(меньше проблем с итераторами, балансировкой и прочим).

Свойство 4.

Высота дерева измеряется только по черным нодам и называется «черной высотой». Тут опять все в целом становится очевидным: красная нода является только дополнением к ноде черной, является ее частью, поэтому высоту принято считать по черным нодам.

На этом введение подходит к концу. В следующей части мы поговорим о том, как вставлять ноды в дерево и балансировать его.

  • бинарные деревья
  • структуры данных

Понимаем красно-чёрное дерево. Часть 1: введение

Аватарка пользователя Nikita

В серии материалов автор помогает разобраться с красно-чёрным деревом. В первой части он знакомит с КЧД и выделяет его важные свойства.

Долгое время я воевал с красно-чёрным деревом (далее — КЧД). Вся информация, которую я находил, была в духе «листья и корень дерева всегда чёрные, ПОТОМУ ЧТО», «топ-5 свойств красно-чёрного дерева» или «3 случая при балансировке и 12 случаев при удалении ноды». Такой расклад меня не устраивал.

Мне не хотелось заучивать свойства дерева, псевдокод и варианты балансировки. Я хотел знать почему. Каким образом цвета помогают при балансировке? Почему у красной ноды не может быть красного потомка? Почему глубину дерева измеряют «чёрной высотой»?

Ответы на эти вопросы я получил только тогда, когда мне дали ссылку на лекцию про 2-3-дерево, с которого мы и начнём.

Эта статья разделена на 3 логические части. Я рекомендую прочитать их в указанном порядке. Первая часть будет направлена на введение в КЧД и знакомство с ним. Во второй части мы поговорим о балансировке и вставке в КЧД. В третьей, завершающей части, мы разберём процесс удаления ноды. Наберитесь терпения и приятного чтения:)

  1. В этой статье не будет информации про плюсы и минусы дерева, его применение и т.д.. Информации об асимптотике дерева и работе с ним в интернете полно.
  2. Материал предназначен для тех, кто уже знаком с КЧД и теперь хочет их понять, а также для тех, кто только знакомится с ними.
  3. Статья не будет содержать деталей реализации структуры.
  4. Можно считать, что эта статья — перевод англоязычного видео в упрощённый русский текстовый вариант.

2-3-дерево

Чтобы понять красно-чёрное дерево, нужно понять 2-3-дерево.

Забегая вперед, скажу, что 2-3-дерево — это, по сути, родитель нашего КЧД, поэтому важно начать именно с него. Поймем 2-3-дерево — поймём и КЧД.

2-3-дерево — абстрактный тип данных, напоминающий по структуре дерево. В нодах 2-3-дерева может быть одно или два значения и два или три потомка (от чего зависит количество значений и потомков ноды, узнаем ниже). Ноду с одним значением и двумя потомками будем называть 2-нода, ноду с двумя значениями и тремя потомками — 3-нода. Объяснение я начну с создания такого дерева: это наглядно и просто. Но некоторые уточнения всё же нужны:

  1. Добавляя элемент, мы всегда спускаемся вниз по дереву.
  2. Дерево отсортировано классически — меньшие значения находятся слева, бОльшие — справа.
  3. 2-3-дерево — отсортированное, сбалансированное дерево.

Итак, начнём с первой ноды, это число 5. Тут всё просто — 5 становится корнем.

Добавим число 12. Его мы также добавляем в корень (помним, что нода может иметь два значения), но теперь нам нужно отсортировать нашу ноду (сортировать два элемента, ха), т.е. уложить их в порядке возрастания. В итоге получается нода 5-12.

Понимаем красно-чёрное дерево. Часть 1: введение 1

Добавим следующее число. Пусть это будет 17. Давайте пока добавим наш элемент в единственную ноду и снова отсортируем ее. Получилась нода 5-12-17.

Внимательный читатель заметит тут подвох — выше я говорил о том, что наши ноды могут содержать не более двух элементов. Вот тут и происходит магия! Мы берём средний элемент нашей ноды и проталкиваем его наверх. Итог виден на картинке. Корнем стало число 12, левым сыном — число 5, правым — 17.

Понимаем красно-чёрное дерево. Часть 1: введение 2

То, что мы сделали выше, можно назвать балансировкой 2-3-дерева. Правило в этой балансировке простое: если в ноде оказывается 3 значения, среднее мы проталкиваем наверх. Алгоритм действий зависит от трёх условий:

  1. Нода является корнем. Тогда ничего не остаётся, как создать новую ноду с одним значением и сделать её новым корнем (как в нашем случае).
  2. Родительская нода имеет одно значение. Тогда мы просто добавляем значение к родителю и завершаем балансировку (при этом у родителя появляется третий потомок).
  3. Родительская нода имеет два значения. Тогда мы снова проталкиваем значение вверх, пока не придём к пункту 1 или 2.

Другие случаи балансировки 2-3-дерева

Окей, идём дальше. Давайте добавим число 3. Так как теперь мы не ограничиваемся одной нодой, спускаемся вниз. Понятно, что спуститься надо влево и добавить 3 к ноде со значением 5. Не забываем расставить 3 и 5 в нужном порядке. В итоге получилась нода 3-5.

Понимаем красно-чёрное дерево. Часть 1: введение 3

Потерпите, мы близимся к самому интересному:)

Давайте добавим число 4, которое также пойдет налево и присоединится к ноде 3-5. Получится нода 3-4-5, которую, как мы уже знаем, нужно привести к нужному виду. Что делаем? Балансируем наше дерево, т.е. проталкиваем значение 4 наверх.

Теперь самое интересное. Помимо того, что мы добавим 4 к корню, мы также добавим корню третьего потомка — это будет нода, которая была больше 4. В нашем случае это 5. Картина будет выглядеть так:

Понимаем красно-чёрное дерево. Часть 1: введение 4

Почему 5 не могла остаться на месте в своей ноде? Тут мы вспоминаем правило отсортированного дерева: значения меньше — слева, значения больше — справа. И так как 5 больше 4, мы не может оставить 5 слева, т.к. это нарушит наш инвариант. Поэтому ноде со значением 5 ничего не остаётся, кроме как переехать и стать потомком ноды 4-12 (кстати, если бы у 5 были потомки, они тоже переехали бы вместе с родителем).

Тут нужно сделать небольшую паузу и объяснить, как ориентироваться в нодах с тремя потомками. Всё просто:

  1. Значение, что меньше левого значения в ноде, будет левым потомком.
  2. Значение, что больше левого, но меньше правого значения в ноде, будет средним потомком.
  3. Значение, что больше правого значения в ноде, будет правым потомком.

Понимаем красно-чёрное дерево. Часть 1: введение 5

А теперь посмотрите на то, что получилось. Смело можно заявить, что это отсортированное, сбалансированное 2-3-дерево. Значения меньше лежат слева, значения больше — справа (тут, как и в случае со значениями 4-5-12, мы считаем, что 5 лежит справа от 4 и слева от 12). Корень имеет 2 значения и 3 потомка, что абсолютно соответствует описанию дерева выше. Сейчас вы можете сами попробовать добавить любое значение, чтобы удостовериться, что вы поняли логику (что произойдёт с деревом, если добавить значение 7, а затем 9?).

Окей, с самим деревом, я надеюсь, разобрались. Ноды добавляются, дерево балансируется, искать можно, всё супер. Но есть нюансы.

Главный минус такой структуры в том, что она, в отличие от бинарного дерева, неудобна в реализации. Нужно следить за количеством потомков и значением, плюс за их порядком, балансировкой (и это я ещё не говорил про удаление). Красно-чёрное дерево решает эту проблему.

Красно-чёрное дерево

Как мы выяснили, главный недостаток 2-3-дерева — структура. Тогда давайте попробуем превратить его в бинарное дерево. Чтобы добиться этого, нам нужно простое представление для 3-ноды. Давайте разделим 3-ноду на две 2-ноды и свяжем их ссылками. Пометим эти ссылки каким-нибудь свойством, например, цветом, (возьмём красный), чтобы отличать такие ссылки в дереве от всех остальных.

Понимаем красно-чёрное дерево. Часть 1: введение 6

Вообще говоря, мы не можем пометить сами ссылки, поэтому мы помечаем ноды.

Понимаем красно-чёрное дерево. Часть 1: введение 7

Итак, перед вами красно-чёрное дерево. Далее мы разберём несколько свойств КЧД, которые я считаю важными (но я думаю, что уже из прочитанного выше многое стало ясно).

Свойства красно-чёрного дерева

Фактически мы разбираем не просто КЧД, а левостороннее КЧД — одну из имплементаций КЧД, в которой красные ноды могут находится только слева. То есть от 3-ноды мы всегда отделяем значение меньше (что и было сделано выше). По сути своей левостороннее КЧД ничем не отличается от обычного, за исключением того, что это более простая и понятная имплементация. Аналогично левостороннему КЧД существует и правостороннее КЧД (логику его додумайте сами).

1. Две красные ноды не могут идти подряд. Это свойство приобретает смысл, если мы знаем, что красная нода — это по сути часть 3-ноды в 2-3-дереве. Ну а если две красные ноды идут подряд, то получается 4-нода, которой у нас не существует:)

2. Корень дерева всегда чёрный. Опять же, тут всё понятно: красная нода не может существовать без потомка.

3. Все null-ноды (ноды, которые не имеют потомков) — чёрные. Почему именно так, для себя объяснений я не нашел. Но хочу сказать, что это довольно удобное правило, когда дело доходит до балансировки дерева.

Раз уж мы затронули null-ноды, то стоит сказать, что в дереве у всех нод всегда должно быть два потомка, а если ссылка на потомка нулевая, то ведёт она как раз в null-ноду. На самом деле, тут встаёт вопрос в реализации, мне было удобнее добавлять null-ноду (меньше проблем с итераторами, балансировкой и прочим).

4. Высота дерева измеряется только по чёрным нодам и называется «чёрной высотой». Тут опять всё в целом становится очевидным: красная нода является только дополнением к ноде чёрной, является её частью, поэтому высоту принято считать по чёрным нодам.

На этом введение подходит к концу. В следующей части мы поговорим о том, как вставлять ноды в дерево и балансировать его.

Деревья, красно-черные деревья

— Нашел тут свои старые записи и приготовил для тебя немного интересного материала. Думаю, тебе будет интересно послушать.

— Давай. Ты всегда находишь что-то интересное, которое потом становится очень полезным.

— Ладно. Сегодня я хочу тебе рассказать про деревья, поэтому начну я с графов.

Граф – это система, состоящая из точек и линий, которые их соединяют. Точки называются вершинами графа, а линии – ребрами графа. Пример:

Деревья, красно-черные деревья - 1

Граф очень удобно использовать как математическую модель для различных реальных процессов и задач. Для графов придумано очень много различных задач и алгоритмов, поэтому их довольно часто используют.

Например, вершины – это города, а ребра – это дороги. Тогда поиск самой короткой дороги между городами превращается в задачу «дан граф, найти кратчайший путь между двумя вершинами».

Но не всегда путь из А в Б, занимает столько же, как и путь из Б в А. Поэтому иногда желательно бы иметь две различные линии. Для этого линии (ребра графа) заменяют на стрелки. Т.е. граф может содержать две стрелки: одну из А в Б, а вторую из Б в А.

Если в графе используются стрелки, его называют ориентированным графом, если просто линии – неориентированным графом.

У каждой вершины может быть свое количество ребер. Также вершина может не иметь ребер вообще. Или наоборот, быть соединена ребрами со всеми остальными вершинами. Если в графе каждая вершина соединена ребром с каждой – такой граф называют полным.

Если в графе по ребрам можно добраться до любой вершины, такой граф называют связным. Граф состоящий из трех отдельных вершин, без ребер вообще, это все равно граф, но несвязный.

Деревья, красно-черные деревья - 2

Чтобы соединить в связный граф N вершин, надо минимум N-1 ребер. Такой граф называется деревом.

При этом обычно одну вершину выбирают корнем дерева, а остальные объявляют ее ветвями. Ветви дерева, которые не имеют своих ветвей, называют листьями . Пример:

Деревья, красно-черные деревья - 3

Дерево называют бинарным, если у каждого элемента дерева не более двух потомков. Т.е. их может быть 0, 1 или 2. Выше справа как раз изображено бинарное дерево.

Дерево называют полным бинарным деревом, когда у каждой ветви 2 потомка, а все листья (без потомков) находятся в одном ряду.

Деревья, красно-черные деревья - 4

— А зачем нужны такие деревья?

— О, деревья применяются много где. Бинарные деревья поиска так вообще являются отсортированной структурой данных.

— Да очень просто. В каждой вершине мы храним некоторое значение. А для каждого элемента вводится правило – значение, которое хранится в потомке справа, больше, чем значение в вершине, а значение, которое хранится в потомке слева – меньше чем значение в вершине. Такое упорядочивание позволяет очень быстро находить нужные элементы в дереве.

— А можно поподробнее.

— Сортировка элементов дерева обычно выполняется добавлением. Вот, допустим, у нас есть 7 элементов: 13, 5, 4, 16, 8, 11, 10

Вот как добавляются элементы в такое дерево.

Деревья, красно-черные деревья - 5

Если мы ищем, например, число 7 в таком дереве, то поиск будет проходить так:

0) Начинаем с корня.

1а) Число 7 равно 13? Нет

1б) Число 7 больше 13? Нет, тогда идем в левое поддерево.

2а) Чисто 7 равно 5? Нет.

2б) Число 7 больше 5? Да, тогда идем в правое поддерево.

3а) Число 7 равно 8? Нет

3б) Число 7 больше 8? Нет, тогда идем в левое поддерево.

4а) Левого поддерева нет, значит, числа 7 в дереве нет.

— Ага. Т.е. нам надо проверять только вершины на пути от корня до предполагаемого места нужного числа. Да, это действительно быстро.

— Еще бы, если дерево сбалансировано, то для миллиона элементов понадобится обход всего около 20 вершин.

— Да, согласен, что это не много.

А что значит – сбалансированное дерево?

— Дерево без «перекосов» — без длинных ветвей. Ведь если бы мы подавали элементы при строительстве дерева в уже отсортированном порядке, у нас бы получилось длинное-предлинное дерево, состоящее из одной ветви.

— Гм. Действительно. И как тогда быть?

— Как ты уже, наверное, догадался, самым эффективным будет дерево, которое имеет ветви примерно равной длины. Тогда при каждом сравнении отбрасывается наибольшая часть поддерева из оставшегося.

— Т.е. нужно переделать дерево?

— Ага. Его нужно «сбалансировать» — сделать максимально похожим на полное бинарное дерево.

Для решения этой проблемы были придуманы самобалансирующиеся деревья. Когда после добавления элемента в дереве возникает перекос, оно немного меняет порядок элементов, и все становится ок. Пример балансировки:

Деревья, красно-черные деревья - 6

Одними из таких деревьев есть так называемые « красно -черные деревья».

— А почему их называют красно-черные?

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

Деревья, красно-черные деревья - 7

— А что это за принципы?

— 1) Красная вершина не может быть сыном красной вершины.

2) Черная глубина любого листа одинакова (черной глубиной называют количество черных вершин на пути из корня).

3) Корень дерева черный.

Я не буду рассказывать тебе, как это работает, у тебя уже небось голова кипит.

— Ага. Процессор греется и не слабо так.

Вот тебе ссылка, если захочешь – почитаешь тут подробнее.

А теперь – иди отдыхай.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *