Сегодня поговорим о бинарных (двоичных) деревьях поиска, а также об их реализации в стандартной библиотеке шаблонов.
Прежде, чем перейти к шаблонам set и map, нужно поговорить о том, как они устроены. “Под капотом” оба контейнера представляют собой именно двоичное дерево поиска. Перейдем к его определению.
Напомню, что деревом называется связный граф без циклов. Мы будем использовать иерархическое корневое двоичное дерево, то есть такое, в котором указано, какая вершина для какой является родителем, и у каждой вершины есть не более 2х потомков, причем не более одного правого и не более одного левого (что логично); У всех вешин, кроме корня, есть ровно один родитель, у корня их нет. Также в каждой вершине дерева будем хранить число. Таким образом, двоичное дерево (пока что не поиска) выглядит как-то так, как показано на картинке справа.
Двоичное дерево высоты n называется полным, если любой узел высоты, меньшей n, имеет 2х потомков, а любой узел высоты n не имеет потомков.
Рис.1 Двоичное дерево
Введем двоичное дерево поиска итеративно:
Дерево, состоящее из одно элемента, является двоичным деревом поиска.
Корневое двоичное иерархическое дерево является двоичным деревом поиска, если:
Таким образом, любой элемент левого поддерева $<$ элемент корня $<$ любой элемент правого поддерева.
Заметим, что по такому определению в двоичном дереве поиска не может быть двух равных элементов.
Теперь еще раз посмотрим на двоичное дерево, изображенное на рисунке 1. Оно не является двоичным деревом поиска, так как, например, в левом поддереве корня есть элемент 7, хотя в корне хранится число 1.
Пример двоичного дерева поиска приведен ниже:
Теперь задумаемся, а зачем нам такое дерево. Оказывается, в нем можно быстро искать элементы. Допустим, мы хотим проверить, если в дереве, изображенном на рисунке 2, число 7. Начинаем смотреть с корня: в корне находится число 8. Но это значит, что если число 7 и есть в двоичном дереве поиска, то только в левом поддереве корня, так как 7 меньше 8, а все элементы, меньшие 8, хранятся в левом поддереве. Теперь “спускаемся” в левое поддерево нашего изначального дерева, попадаем в вершину, в которой записано число 3. Рассуждая аналогично, делаем вывод, что число 7 если и есть в дереве, то находится в правом поддереве поддерева с вершиной в 3-ке.
Рис. 2. Двоичное дерево поиска
Продолжая действовать аналогичным образом, получим, что мы нашли элемент 7, выполнив всего 4 сравнения, хотя структура хранит в себе 10 чисел. Если бы мы хранили это множество как массив и, чтобы проверить, если число 7 в нем, сравнивали бы 7 со всеми элементами множества, то мы выполнили бы в худшем случае 10 операций.
Используя же двоичное дерево поиска, мы в худшем случае “спустимся” до самого нижнего элемента. Таким образом, сложность операции поиска — это высота двоичного дерева поиска.
Как уже было сказано, сложность операции поиска — это высота двоичного дерева поиска. Но граф может выглядеть, например, так, как показано на рисунке 3. Это дерево является двоичным деревом поиска, но имеет высоту n. Таким образом, поиск в нем будет не быстрее поиска в массиве. Таким образом, нужно пытаться создавать сбалансированные деревья поиска, то есть такие, в которых для каждой вершины высоты поддеревьев отличаеются не больше чем на 1. Тогда, используя алгоритм поиска, каждую итерацию мы будем “отбрасывать” половину дерева поиска, и сложность операции будет $O(logn)$.
Рис. 3. “Бамбук” высоты n
#include <set>