— Привет, Амиго!
— Здорово, Риша!
— Нашел тут свои старые записи и приготовил для тебя немного интересного материала. Думаю, тебе будет интересно послушать.
— Давай. Ты всегда находишь что-то интересное, которое потом становится очень полезным.
— Ладно. Сегодня я хочу тебе рассказать про деревья, поэтому начну я с графов.
Граф – это система, состоящая из точек и линий, которые их соединяют. Точки называются вершинами графа, а линии – ребрами графа. Пример:
Граф очень удобно использовать как математическую модель для различных реальных процессов и задач. Для графов придумано очень много различных задач и алгоритмов, поэтому их довольно часто используют.
Например, вершины – это города, а ребра – это дороги. Тогда поиск самой короткой дороги между городами превращается в задачу «дан граф, найти кратчайший путь между двумя вершинами».
Но не всегда путь из А в Б, занимает столько же, как и путь из Б в А. Поэтому иногда желательно бы иметь две различные линии. Для этого линии (ребра графа) заменяют на стрелки. Т.е. граф может содержать две стрелки: одну из А в Б, а вторую из Б в А.
Если в графе используются стрелки, его называют ориентированным графом, если просто линии – неориентированным графом.
У каждой вершины может быть свое количество ребер. Также вершина может не иметь ребер вообще. Или наоборот, быть соединена ребрами со всеми остальными вершинами. Если в графе каждая вершина соединена ребром с каждой – такой граф называют полным.
Если в графе по ребрам можно добраться до любой вершины, такой граф называют связным. Граф состоящий из трех отдельных вершин, без ребер вообще, это все равно граф, но несвязный.
Чтобы соединить в связный граф 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) Корень дерева черный.
Я не буду рассказывать тебе, как это работает, у тебя уже небось голова кипит.
— Ага. Процессор греется и не слабо так.
Вот тебе ссылка, если захочешь – почитаешь тут подробнее.
Ссылка на дополнительный материал
А теперь – иди отдыхай.
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ