Как устроены двоичные деревья и где они применяются?

Узел, находящийся на самом верхнем уровне, принято называть корнем дерева (root).

Узлы дерева, у которых нет дочерних узлов, называются листьями. В бинарном дереве оба указателя на дочерние узлы у листа равны nil или null — в зависимости от языка программирования.

Узел можно представить с использованием такой структуры данных на языке программирования C++:

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

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

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

В бинарном дереве существуют основные отношения между узлами.

У каждого узла может быть родительский узел. Родителем является узел, который находится выше. У узла также может быть левый потомок — на него указывает указатель left, и правый потомок — на него указывает указатель right.

Дерево — это рекурсивная структура данных: вся структура данных является деревом, где каждое поддерево также является деревом.

В программировании приходится представлять различные иерархии. Например:

• иерархию папок в директории;
• иерархию сотрудников предприятия.

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

Сбалансированное дерево — это дерево, в котором для каждого узла разница в высоте между его левым поддеревом и его правым поддеревом не превышает единицы.

Здесь используется такое понятие, как высота дерева.

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

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

Дерево считается несбалансированным, если высота левого и правого поддеревьев для какого-либо узла отличается больше чем на единицу.

Если требуется рассчитать высоту сбалансированного бинарного дерева при известном количестве элементов, то она будет примерно равна log(N):

 H = log(N) 

Почему она равна логарифму? Потому что при построении сбалансированного дерева на каждом уровне можно добавить примерно в 2 раза больше новых мест для элементов, чем на предыдущем уровне.

Например:

Каждый раз, когда высота дерева увеличивается всего на 1, количество мест, которые можно туда вместить, удваивается. Поэтому высота, то есть количество шагов или уровней, зависит от того, сколько раз нужно удвоить что-то, чтобы получить N. А это как раз и есть log(N).

Можно вывести обратную формулу. Если известна высота сбалансированного бинарного дерева, то относительно нее можно получить количество элементов в бинарном дереве:

 N ≈ 2H , где H — высота дерева.

Бинарное дерево поиска — это такое же бинарное дерево, но обладающее дополнительными свойствами:

Разберем на примере.

Например, если значение родителя равно 20, то значение левого потомка должно быть меньше либо равно 20 (в примере это 10), а значение правого потомка — больше 20 (в примере это 30).

Если значение узла равно 5, то значение левого ребёнка должно быть меньше либо равно 5 (в примере это 2), а значение правого ребёнка — больше 5 (в примере это 7).

При таком способе хранения данных в бинарном дереве поиска можно достаточно просто определить, где находится минимальный элемент. Он будет находиться в левом нижнем углу. Для его поиска необходимо пройти от корня в самый низ по левым потомкам.

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

Рассмотрим сбалансированное бинарное дерево поиска.

Высота сбалансированного бинарного дерева примерно равна log (N). В худшем случае потребуется пройти всю высоту бинарного дерева поиска, поэтому асимптотическая сложность будет логарифмической — O (log (N)).

При таком способе хранения элементов появляется ещё одно свойство.

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

Одно из основных предназначений бинарного дерева поиска — операция поиска.

Например, требуется найти в бинарном дереве поиска элемент со значением 12. При таком способе хранения данных можно использовать концепцию «разделяй и властвуй» — на каждом шаге отбрасывать половину элементов, как при использовании алгоритма бинарного поиска.

Поиск начинается с корня: если 12 меньше либо равно 20, поиск продолжается в левой стороне. Идти в правую сторону нет смысла, потому что там будут находиться элементы больше 20. На этом шаге отбрасывается половина элементов в рамках сбалансированного бинарного дерева.

Далее рассматривается узел со значением 10. Если 12 больше 10, поиск продолжается вправо. Идти влево по дереву нет смысла, потому что там находятся элементы меньше либо равные 10. Снова отбрасывается половина элементов.

Далее рассматривается элемент 15. Если 12 меньше либо равно 15, поиск продолжается в левой стороне. Правая часть отбрасывается.

Наконец, находится элемент со значением 12.

При поиске асимптотической сложности операции поиска в худшем случае нужно будет пройти всю высоту дерева. Если дерево сбалансированное, его высота примерно равна log (N). Поэтому поиск в сбалансированном бинарном дереве поиска будет работать за O (log N) по времени.

Самый худший случай — так называемое «дерево-бамбук». Оно похоже на связный список, но связным списком не является, потому что здесь есть указатель на левого и правого потомка.

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

Рассмотрим операцию вставки в бинарное дерево поиска. Например, требуется вставить элемент со значением 16.

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

Вставка начинается с корня, где мы смотрим:

Если в соответствующем месте нет элемента, то сюда вставляется элемент со значением 16.

Операция поиска в сбалансированном бинарном дереве поиска имеет логарифмическую временную сложность — O(log(N)), а в несбалансированном бинарном дереве поиска — линейную, O(N).

Поэтому временная сложность операции вставки будет такой же:

• в сбалансированном бинарном дереве поиска — O(log(N));
• в несбалансированном бинарном дереве поиска — O(N).

Рассмотрим операцию удаления, где, например, требуется удалить элемент 33 из бинарного дерева поиска.

Для удаления элемента сначала необходимо его найти.

Поиск начинается с 20. 33 > 20, поэтому поиск продолжается вправо; 33 > 30 — поиск продолжается вправо; 33 < 35 — поиск продолжается влево. Наконец, находится нужный элемент.

У него нет детей, это листовой узел, поэтому его можно удалить и присвоить nil.

Другой случай — удаление элемента со значением 25, то есть элемента, у которого есть один ребёнок.

Сначала выполняется поиск элемента: 25 > 20 — поиск продолжается вправо.
25 < 30 — поиск продолжается влево. После нахождения элемента видно, что у него есть только один ребёнок.

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

Про удаляемый элемент остаётся забыть.

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

Ещё более интересный случай — удаление элемента со значением 10, у которого есть два потомка.

В первую очередь необходимо найти этот элемент: 10 < 20, поэтому поиск продолжается влево. После нахождения элемента видно, что у него есть два потомка.

В этой ситуации есть 2 варианта:

Для поиска максимального элемента в этом поддереве необходимо идти вправо в самый низ. Найденный элемент будет являться максимальным.

Для поиска минимального элемента в этом поддереве необходимо идти влево, в самый низ.

Таким образом, значение 10 можно заменить либо на 7, либо на 12. И в том, и в другом случае свойство бинарного дерева поиска не будет нарушено.

При выборе первого подхода значение заменяется на 7, а про исходный элемент остаётся забыть.

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

Соответственно:

• сложность удаления в сбалансированном бинарном дереве поиска — O(log(N));
• сложность удаления в несбалансированном бинарном дереве поиска — O(N).

Бинарное дерево — иерархическая структура данных, в которой каждый узел может иметь не более двух потомков.

Бинарное дерево поиска расширяет эту структуру дополнительными правилами, благодаря которым поиск, вставка и удаление элементов в сбалансированном дереве выполняются за O(log(N)). При нарушении баланса дерево может превратиться в структуру, похожую на связный список, и сложность операций возрастает до O(N).

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


Если хотите подробнее разобраться в работе связных списков, то читайте статью «Что такое связные списки» и смотрите наше видео с наглядными примерами из курса по структурам данных.