— Привет, Амиго!
— Здорово, Риша!
— Нашел тут свои старые записи и приготовил для тебя немного интересного материала. Думаю, тебе будет интересно послушать.
— Давай. Ты всегда находишь что-то интересное, которое потом становится очень полезным.
— Ладно. Сегодня я хочу тебе рассказать про деревья, поэтому начну я с графов.
Граф – это система, состоящая из точек и линий, которые их соединяют. Точки называются вершинами графа, а линии – ребрами графа. Пример:
![Деревья, красно-черные деревья - 1](https://cdn.javarush.com/images/article/92f10cd4-0f78-44f7-b4bc-fb2a5ddb7509/original.jpeg)
Граф очень удобно использовать как математическую модель для различных реальных процессов и задач. Для графов придумано очень много различных задач и алгоритмов, поэтому их довольно часто используют.
Например, вершины – это города, а ребра – это дороги. Тогда поиск самой короткой дороги между городами превращается в задачу «дан граф, найти кратчайший путь между двумя вершинами».
Но не всегда путь из А в Б, занимает столько же, как и путь из Б в А. Поэтому иногда желательно бы иметь две различные линии. Для этого линии (ребра графа) заменяют на стрелки. Т.е. граф может содержать две стрелки: одну из А в Б, а вторую из Б в А.
Если в графе используются стрелки, его называют ориентированным графом, если просто линии – неориентированным графом.
У каждой вершины может быть свое количество ребер. Также вершина может не иметь ребер вообще. Или наоборот, быть соединена ребрами со всеми остальными вершинами. Если в графе каждая вершина соединена ребром с каждой – такой граф называют полным.
Если в графе по ребрам можно добраться до любой вершины, такой граф называют связным. Граф состоящий из трех отдельных вершин, без ребер вообще, это все равно граф, но несвязный.
![Деревья, красно-черные деревья - 2](https://cdn.javarush.com/images/article/8454e335-ce6b-4969-b30d-0d03058a583d/original.jpeg)
Чтобы соединить в связный граф N вершин, надо минимум N-1 ребер. Такой граф называется деревом.
При этом обычно одну вершину выбирают корнем дерева, а остальные объявляют ее ветвями. Ветви дерева, которые не имеют своих ветвей, называют листьями. Пример:
![Деревья, красно-черные деревья - 3](https://cdn.javarush.com/images/article/fe3df189-7091-4842-88c5-aa52a04ce5af/original.jpeg)
Дерево называют бинарным, если у каждого элемента дерева не более двух потомков. Т.е. их может быть 0, 1 или 2. Выше справа как раз изображено бинарное дерево.
Дерево называют полным бинарным деревом, когда у каждой ветви 2 потомка, а все листья (без потомков) находятся в одном ряду.
Пример:
![Деревья, красно-черные деревья - 4](https://cdn.javarush.com/images/article/a4bc608d-b5b8-488d-af46-5d84b331aa02/original.jpeg)
— А зачем нужны такие деревья?
— О, деревья применяются много где. Бинарные деревья поиска так вообще являются отсортированной структурой данных.
— Это как?
— Да очень просто. В каждой вершине мы храним некоторое значение. А для каждого элемента вводится правило – значение, которое хранится в потомке справа, больше, чем значение в вершине, а значение, которое хранится в потомке слева – меньше чем значение в вершине. Такое упорядочивание позволяет очень быстро находить нужные элементы в дереве.
— А можно поподробнее.
— Сортировка элементов дерева обычно выполняется добавлением. Вот, допустим, у нас есть 7 элементов: 13, 5, 4, 16, 8, 11, 10
Вот как добавляются элементы в такое дерево.
![Деревья, красно-черные деревья - 5](https://cdn.javarush.com/images/article/cbc668a8-e3ec-4cdd-a368-be1412e59a05/original.jpeg)
Если мы ищем, например, число 7 в таком дереве, то поиск будет проходить так:
0) Начинаем с корня.
1а) Число 7 равно 13? Нет
1б) Число 7 больше 13? Нет, тогда идем в левое поддерево.
2а) Чисто 7 равно 5? Нет.
2б) Число 7 больше 5? Да, тогда идем в правое поддерево.
3а) Число 7 равно 8? Нет
3б) Число 7 больше 8? Нет, тогда идем в левое поддерево.
4а) Левого поддерева нет, значит, числа 7 в дереве нет.
— Ага. Т.е. нам надо проверять только вершины на пути от корня до предполагаемого места нужного числа. Да, это действительно быстро.
— Еще бы, если дерево сбалансировано, то для миллиона элементов понадобится обход всего около 20 вершин.
— Да, согласен, что это не много.
А что значит – сбалансированное дерево?
— Дерево без «перекосов» — без длинных ветвей. Ведь если бы мы подавали элементы при строительстве дерева в уже отсортированном порядке, у нас бы получилось длинное-предлинное дерево, состоящее из одной ветви.
— Гм. Действительно. И как тогда быть?
— Как ты уже, наверное, догадался, самым эффективным будет дерево, которое имеет ветви примерно равной длины. Тогда при каждом сравнении отбрасывается наибольшая часть поддерева из оставшегося.
— Т.е. нужно переделать дерево?
— Ага. Его нужно «сбалансировать» — сделать максимально похожим на полное бинарное дерево.
Для решения этой проблемы были придуманы самобалансирующиеся деревья. Когда после добавления элемента в дереве возникает перекос, оно немного меняет порядок элементов, и все становится ок. Пример балансировки:
![Деревья, красно-черные деревья - 6](https://cdn.javarush.com/images/article/562c4f2e-2543-4ad8-be26-aaef2b823587/original.jpeg)
Одними из таких деревьев есть так называемые «красно-черные деревья».
— А почему их называют красно-черные?
— Их создатель придумал красить все вершины в два цвета. Один цвет – красный, второй – черный. И разные вершины подчиняются разным правилам. На этом и строится вся балансировка.
Пример:
![Деревья, красно-черные деревья - 7](https://cdn.javarush.com/images/article/bb86f58f-c9b2-4f94-8eca-da9ea78d7157/original.jpeg)
— А что это за принципы?
— 1) Красная вершина не может быть сыном красной вершины.
2) Черная глубина любого листа одинакова (черной глубиной называют количество черных вершин на пути из корня).
3) Корень дерева черный.
Я не буду рассказывать тебе, как это работает, у тебя уже небось голова кипит.
— Ага. Процессор греется и не слабо так.
Вот тебе ссылка, если захочешь – почитаешь тут подробнее.
Ссылка на дополнительный материал
А теперь – иди отдыхай.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ