СБАЛАНСИРОВАННЫЕ ДЕРЕВЬЯ

Для добавления элементов к дереву и реорганизации дерева, лучше всего подходит теория и алгоритмы сбалансированных деревьев, прекрасно изложенные в монографии Н. Вирта [3]. Дерево называется сбалансированным тогда и только тогда, когда высоты двух поддеревьев каждой из его вершин отличаются не более чем на единицу.

Рассмотрим алгоритм включения элемента в сбалансированное дерево. Если у нас есть корень r и левое (L) и правое (R) поддеревья, то необходимо различать 3 возможных случая. Предположим, что включение в L новой вершины, приведет к увеличению на 1 его высоты, тогда возможно:

1. h_L = h_R (где h – высота дерева). Тогда после включения L и R станут разной высоты, но критерий сбалансированности не будет нарушен.

2. h_L < h_R, L и R станут равной высоты, то есть сбалансированность улучшится.

3. h_L > h_R, критерии сбалансированности нарушатся и дерево необходимо перестраивать.

Для примера, возьмем дерево, представленное на рис. 3.4. Вершины с ключами 9 и 11 можно включить, не нарушая сбалансированности дерева; дерево с корнем 10 становится односторонним (случай 1), а с корнем 8 – лишь лучше сбалансированным (случай 2). Отдельное включение ключей 1,3,5 или 7 требует последующей балансировки.

При внимательном изучении этой ситуации можно обнаружить, что существует лишь две по существу различные возможности, требующие индивидуального подхода. Оставшиеся могут быть выведены из этих двух на основе симметрии. Первый случай возникает при включении в дерево на рис. 3.4 ключей 1 или 3, ситуация характерная для второго случая, возникает при включении ключей 5 или 7.

Схематично эти случаи представлены на рисунке 3.5, где прямоугольниками обозначены поддеревья, причем “добавленная” при включении высота отмечена перечеркиванием.

Простые преобразования сразу же восстанавливают сбалансированность. Их результат приведен на рисунке 3.6. Обратите внимание, что допускаются лишь перемещения в вертикальном направлении, в то время как относительное горизонтальное расположение вершин и поддеревьев должно остаться неизменным.

Алгоритм включения и балансировки существенно зависит от того, каким образом хранится информация о сбалансированности дерева. Крайнее решение – хранить эту информацию полностью неявно, в структуре самого дерева. Однако в этом случае сбалансированность узла нужно определять всякий раз, когда включение затрагивает этот узел. Это ведет к очень большим затратам.

Другая крайность – хранить в каждой вершине показатели сбалансированности. В этом случае определение узла дерева представляется в виде:

Type Ptr=Pointer to Node;

Type Balance=[–1..+1];

Type Node=record

count: Integer;

left,right:Ptr;

hol:Balance;

end;

Показатель сбалансированности вершины можно определять как разность между высотой правого поддерева и левого. Процесс включения вершины фактически состоит из трех последовательно выполняемых пунктов:

1. Проходя по пути поиска, пока не убедимся, что ключа в дереве нет.

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

3. “Отступления” по пути поиска и проверки в каждой вершине показателя сбалансированности. Если необходима – балансировка.

Хотя при таком методе и требуются некоторые избыточные проверки (если сбалансированность уже зафиксирована, то нет необходимости проверять ее в вышестоящих вершинах), традиционно придерживаются именно этой корректной схемы, так как ее можно реализовать простым расширением процедуры поиска элемента в дереве с включениями. В этой процедуре описываются действия, связанные с поиском в каждой вершине, и в силу рекурсивной природы этой процедуры ее легко приспособить для выполнения дополнительных действий при возвращении вдоль пути поиска. Информация, которую необходимо передавать на каждом шаге, указывает, увеличилось ли или нет высота поддерева, где произошло включение. Поэтому кроме традиционных параметров, x ключ поиска и p – указатель вершины дерева, добавляется булевское значение (параметр – переменная) h, – означающее – “ высота дерева увеличилась”.

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

Исключением из сбалансированного дерева– процесс еще более сложный, чем включение в него. Тем не менее, операции поиска, включения и исключения из сбалансированного дерева выполняются даже в худшем случае за время пропорциональное t*(log ₂ N), где t – некоторое константа, а N – количество элементов в таблице.

Поиск по сайту: