Деревья двоичного поиска

Дерево двоичного поиска (ДДП) — это способ хранения множества в форме расширяемого упорядоченного списка с сохранением упорядоченности при вставке новых элементов без перемещения уже имеющихся.

ДДП — это дерево с нагруженными узлами, вес в любом узле которого больше любого веса в левом его поддереве и не больше любого веса в правом поддереве. Количество шагов алгоритма поиска элемента множества в таком дереве не превышает его высоты, т. е. имеет сложность O(log n). Такую же сложность имеют операции вставки нового элемента в дерево и удаления элемента.

ДДП можно получить из упорядоченной последовательности ключей, если двоичное дерево соответствующей мощности разметить внутренним (симметричным) способом, а затем заменить номера узлов соответствующими элементами последовательности. Если последовательность хранится в массиве, то построить ДДП можно методом деления пополам: поместить в корень дерева средний по порядку элемент, затем рекурсивно создать левое поддерево из первой половины последовательности, а правое — из второй.

Node * Build(int a, int b, int * data) //Сборка ДДП из массива узлов data

{ if (b < = a) return 0;

int c = (a + b) /2;

Node * s = new Node (data[ c ]);

s-> left = Build(a, c, data);

s-> right = Build(c+1, b, data);

return s;

}

Недостаток ДДП — в том, что оно хорошо работает в том случае, если сбалансировано, т. е. длины путей из корня в любой лист примерно одинаковы. Однако при поэлементной вставке в дерево упорядоченной последовательности оно вырождается, превращаясь в линейный список. Поиск, вставка и удаление в таком дереве будут выполняться не за логарифмическое, а за линейное время. Вероятность вырождения весьма велика. Так, из 7 узлов можно образовать только одно полностью сбалансированное дерево, а полностью вырожденных — 64. Поэтому алгоритмы работы с ДДП часто дополняют автобалансировкой после вставки и удаления. Наиболее употребительны следующие схемы:

1) АВЛ-деревья. Разность высот поддеревьев любого узла дерева не превышает 1. Информация о разности высот хранится в узле и используется для его перестройки после вставки и удаления узла;

2) красно-чёрные деревья. Узлы красятся в один из двух цветов — чёрный или красный. Если узел — красный, его сыновья — обязательно чёрные. Вставляемый узел — всегда красный. При появлении цепочки из двух красных узлов дерево перестраивается;

3) 2-3-деревья. Данные хранятся в листьях, над которыми делается надстройка из управляющих узлов, каждый из которых может иметь 2 или 3 сына и содержит наибольшие значения ключей в левом и в среднем поддеревьях, что необходимо для операции поиска. Если у узла оказывается 1 или 4 сына, дерево перестраивается.

Подробнее о ДДП и деревьях с автобалансировкой см. [1], с. 457–468, [2], с. 523–566, [5], с. 341–344.

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

Однако можно использовать тот факт, что из ДДП легко получить упорядоченную последовательность ключей внутренним обходом. Применив такой обход к двум ДДП одновременно, можно обработать последовательности алгоритмом слияния, модифицировав его для нужной операции над множествами. Результат в виде упорядоченной последовательности записывается в массив, из которого затем описанным выше методом деления пополам строится новое ДДП. Этот способ обеспечивает получение результата за время O(n) независимо от формы исходных ДДП, а результат всегда получается сбалансированным.

ДДП сами по себе мало пригодны для хранения множеств с повторениями, поскольку дубликаты ключей искажают форму дерева, образуя в нём мёртвые зоны: группы указателей, которые никогда не используются. Ситуацию можно улучшить, если вместо дубликатов ключей хранить в каждом узле значение кратности (1 или больше). Если же дубликаты должны быть представлены явно, их можно хранить в узлах как цепочки переполнения, по аналогии с хеш-таблицей.