Сбалансированные деревья поиска

Алла: Деревья это, конечно, интересно, но я не поняла пока, зачем они нужны. Находить элементы можно и в массиве. И при этом не нужны ссылки на дочерние узлы, которые, между прочим, занимают память!
image
Тимофей: Сейчас всё узнаешь!
Предположим, нужно найти элемент 20.
Так мы будем искать его в дереве:
  1. Сравним искомый элемент со значением в корне. 20 больше 10, значит пойдём направо.
  2. Сравним искомый элемент 20 и вершину 15. 20 больше 15, снова пойдём направо.
  3. Текущий элемент равен искомому. Остановим поиск.
Чтобы найти элемент, нам потребовалось сделать три сравнения.
Целое число, большее или равное log⁡27\log_27 — это 3. Мы нашли элемент за логарифмическое время!
А что будет, если нам нужно найти элемент в списке?
Потребуется в худшем случае nn операций сравнения. В нашем случае — 7 операций.
Алла: Но ведь в отсортированном массиве тоже можно искать за логарифмическое время.
Тимофей: А если он не отсортирован?
Алла: Ну, если нет, то нельзя. Но можно отсортировать! Или попросить, чтобы кто-то другой отсортировал.
Тимофей: На это понадобится O(nlog⁡n)O(n\log n) операций. И как быть при вставке и удалении элементов? На это в худшем случае требуется O(n)O(n) операций.
Алла: Я поняла! Получается, для поиска элемента идеально подойдёт дерево поиска?
Тимофей: Не всегда. Для связного списка мы рассматривали худший случай. Но в лучшем случае можно найти элемент за 1 операцию сравнения. А иногда — за nn.
image
Это бинарное дерево поиска?
Но если мы воспользуемся таким деревом, в худшем случае при поиске элемента потребуется O(n)O(n) операций.
Алла: А, значит в худшем случае всё равно придётся долго искать! Я так и знала.
Тимофей: Ты не права. Для эффективной операции поиска дерево должно быть сбалансировано.
Интуитивно понятно, что это значит:
image
Алла: А каким требованиям соответствует сбалансированное дерево поиска?
Это различные критерии сбалансированности. Если дерево удовлетворяет им, то операции вставки, поиска и удаления в худшем случае требуют O(log⁡n)O(\log n) времени.

Критерий 1:

Для любого узла количество узлов в левом и правом поддереве NlN_l, NrN_r отличается не более, чем на 1.
Nr⩽Nl+1,Nl⩽Nr+1N_r \leqslant N_l +1, \\N_l \leqslant N_r +1.
Это — идеально сбалансированное дерево.
image
Первое дерево — несбалансированное в соответствии с этим критерием. В левом поддереве 4 подузла, а в правом — 2. Количество отличается более чем на 1, условие не выполнено.
Второе удовлетворяет условию сбалансированности.
Рассмотрим ещё два критерия сбалансированности деревьев. Они не такие строгие, как первый, но тоже гарантируют выполнение операций поиска, вставки и удаления за логарифмическое время.

Критерий № 2:

Бинарное дерево поиска сбалансировано, если для любого узла количество подузлов в левом и правом поддеревьях удовлетворяют условиям:
Nr⩽2Nl+1,Nl⩽2Nr+1N_r \leqslant 2N_l + 1, \\N_l \leqslant 2N_r + 1.
Такое дерево называют АВЛ-деревом.
Его изобрели советские учёные Адельсон-Вельский Г.М. и Ландис Е.М. Дерево назвали, сложив первые буквы фамилий — АВЛ.
image
Пример на рисунке — АВЛ-дерево, потому что для любой вершины высоты правого и левого поддеревьев отличаются не больше, чем на 1.
Если обозначить высоту дерева через hh, а минимальное количество вершин — через NN, то для АВЛ дерева функция зависимости NN от hh имеет вид:
N(h)=Θ(λh)N(h) = \Theta(\lambda^h), где λ=5+12≈1,62.\lambda = \displaystyle \frac {\sqrt5 + 1}{2}\approx 1, 62.
Для того, чтобы освежить в памяти определения, связанные с асимптотической сложностью, посмотрите этот урок.

Критерий №3:

Бинарное дерево поиска сбалансировано, если для любого узла высоты левого и правого поддеревьев удовлетворяют условиям:
Hr⩽Hl+1,Hl⩽Hr+1H_r \leqslant H_l + 1, \\H_l \leqslant H_r + 1.
Красно-чёрное дерево строится по следующим принципам:
  • Вершины дерева разделены на красные и чёрные.
  • Каждая вершина хранит поля ключ и значение.
  • Каждая вершина имеет указатели left, right, parent.
  • Отсутствующие указатели помечаются указателями на узел nil.
  • Каждый лист nil — чёрный.
  • Если вершина — красная, то её дочерние вершины — чёрные.
Алла: Кто-то рисовал флаг Удмуртии и лишние краски остались или зачем их покрасили?
Тимофей: Эта характеристика используется при балансировке дерева.
Алла: А что такое балансировка?
Тимофей: Это операция, которая помогает сохранять свойства сбалансированности при добавлении и удалении элементов.
image
При использовании такого дерева функция, которая показывает зависимость количества вершин в дереве от его высоты, будет такая:
N(h)⩾2h−12N(h) \geqslant 2^{ \frac{h - 1}{2}}.
То есть при одинаковом количестве листьев красно-чёрное дерево может быть выше АВЛ-дерева, но не более чем в 1.39 раз.
Алла: А почему тогда красно-черные деревья часто используют в стандартных библиотеках? Какая разница в производительности АВЛ и красно-чёрных деревьев?
Тимофей: АВЛ-деревья быстрее работают при поиске. Если в вашей задаче операции поиска преобладают, делайте выбор в пользу этого вида деревьев. Красно-чёрные деревья эффективнее при операциях вставки и удаления. В целом, красно-чёрные деревья демонстрируют относительно высокую эффективность для всех операций. С их применением реализованы многие структуры данных в популярных языках программирования. Например, map, multimap, multiset в C++, java.util.TreeMap, java.util.TreeSet.
Алгоритмы реализации идеально сбалансированного дерева, АВЛ и красно-чёрных деревьев сложные. Скорее всего, вы не столкнётесь с ними на практике. Но важно помнить, что применение этих деревьев гарантирует в худшем случае логарифмическую сложность при поиске, вставке и удалении элементов.
Решите задачи B, F: https://contest.yandex.ru/contest/18996/problems/B/.