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

— Привет, Амиго!

— Здорово, Риша!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример:

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

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

— Это как?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример:

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

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

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

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

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

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

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

Ссылка на дополнительный материал

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