скачать doc
2.Деревья поиска
2.1.Идеально сбалансированные бинарные деревья
Как известно (см. [*], раздел 5), решении задачи поиска элемента в произвольном одномерном массиве из n элементов требует в худшем случае n сравнений, а в среднем n/2 сравнений (при равномерном распределении предъявляемых для поиска элементов). В упорядоченном массиве задача поиска решается алгоритмом бинарного поиска не более чем за
сравнений, и это оптимальный результат для алгоритмов, основанных на сравнениях (см. [*], раздел 5). По количеству сравнений бинарный поиск является эталоном для решения задач поиска. Однако если кроме поиска требуется производить и другие операции с данными, например, такие как вставка или удаление элемента, то массив не является подходящей структурой данных, поскольку выполнение этих операций требует количества перемещений элементов массива в среднем пропорционального его размеру. Говорят, что эти операции являются массовыми.Использование деревьев для организации данных, с которыми требуется выполнять операции поиска, вставки и удаления, оказывается более предпочтительным.
Далее будем предполагать, что каждый элемент данных d содержит поле ключа d.key (или в других обозначениях key(d) или k(d)), который используется для сравнений в ходе операций поиска.
Возможно, не всякие (по структуре) деревья будут одинаково эффективными для поиска. Если вспомнить деревья решений, используемые при анализе алгоритма бинарного поиска [*], то естественно ожидать, что лучшие результаты будут получаться в случае более ровных деревьев, например, деревьев, имеющих минимальную высоту при заданном количестве узлов.
Рассмотрим так называемые идеально сбалансированные деревья. Идеально сбалансированным назовем такое бинарное дерево T , что для каждого его узла x справедливо соотношение nL(x) nR(x) 1, где nL(x) количество узлов в левом поддереве узла x, а nR(x) количество узлов в правом поддереве узла x. Примеры некоторых идеально сбалансированных деревьев даны на рисунке.
Л
егко установить, что в идеально сбалансированном дереве число узлов n и высота дерева h связаны соотношением
или в другой форме 
(Здесь и далее высота дерева определена так, что при n = 0 имеем h = 0, а при n = 1 имеем h = 1).Рассмотрим алгоритм построения идеально сбалансированного дерева по последовательности данных a1, a2, …, an (например, находящейся в файле f_input). Идея этого рекурсивного алгоритма ясна из следующего рисунка (здесь nL = n div 2 и nR = n – nL – 1, т. е. n = nL + nR +1)
Считаем, что тип данных BTree, представляющий бинарное дерево, определен как
type BTree = Node;
Node = record
Info: Elem;
LSub, RSub: BTree
end {Node}
Кроме того, базовые функции этого типа, например, Null, Create, Root, Left, Right, ConsBT, MakeRoot определены так же, как в [**], раздел 3.
Тогда алгоритм, реализованный в виде рекурсивной функции, есть
function Tree (n: Nat0): BTree;
var nL, nR: Nat0; b1, b2: BTree; x: Elem;
begin if n = 0 then Tree := nil else
begin nL := n div 2; nR := n – nL – 1;
b1 := Tree (nL);
Read (f_input, x);
b2 := Tree (nR);
Tree := ConsBT (x, b1, b2)
end
end {Tree}
Здесь ConsBT (x, b1, b2) функция-конструктор, строящая новое дерево из корня x и левого b1 и правого b2 поддеревьев.
Р
ассмотрим примеры работы этого алгоритма. Пусть во входном файле находится последовательность a, b, c, d, e, f, g, h, i, а стартовый вызов функции Tree (n) производится так: Reset(f_input); b := Tree (n). На рисунке представлены деревья, построенные с помощью функции Tree (n) при значениях n = 1, 2, 3, 4, 5, 6, 7, 8, 9.
Отметим, что наш алгоритм строит такие идеально сбалансированные деревья, что nL(x) nR(x) = 0 или 1, т. е. при nL(x) ≠ nR(x) именно левое поддерево содержит на один узел больше. При этом структура дерева определяется только значением параметра n, а содержимое узлов зависит от расположения элементов во входной последовательности. В предыдущем примере из-за того, что входная последовательность упорядочена, все построенные деревья обладают интересным свойством: при обходе этих деревьев «слева направо», т. е. при симметричном или ЛКП обходе (см. [**] раздел 3), порождается исходная упорядоченная последовательность. Тот факт, что получается исходная последовательность, не удивителен, поскольку алгоритм построения дерева следует той же ЛКП схеме – сначала строится левое поддерево, затем определяется корень дерева, а затем уже строится правое поддерево, после чего происходит сборка результирующего дерева.
Полезно в качестве упражнения рассмотреть алгоритмы построения идеально сбалансированных деревьев, отличающиеся порядком чередования рекурсивных вызовов и вызова процедуры чтения из файла, т. е. рассмотреть следующие варианты:
| Вариант с КЛП схемой | Вариант с ЛПК схемой |
| begin nL := n div 2; nR := n – nL – 1; Read (f_input, x); b1 := Tree (nL); b2 := Tree (nR); Tree := ConsBT (x, b1, b2) end | begin nL := n div 2; nR := n – nL – 1; b1 := Tree (nL); b2 := Tree (nR); Read (f_input, x); Tree := ConsBT (x, b1, b2) end |
Если бы входная последовательность не была упорядочена, то построенное нашей функцией Tree дерево не обладало бы отмеченным свойством упорядоченности.
Деревья, в результате ЛКП обхода которых получается упорядоченная последовательность узлов, называются деревьями поиска и будут подробно рассмотрены далее.