На этом шаге мы рассмотрим балансировку деревьев.
Если хотим, чтобы дерево, которое строим, никогда не выродилось в список, можно прибегнуть к процедуре балансировки. Балансировка - это метод, позволяющий не допустить возникновения слишком плохих деревьев. Обсудим здесь лишь основную идею алгоритма, оставив детали реализации для самостоятельных упражнений.
Высотой дерева называется длина самой длинной ветви. В дереве выделяется корень, левое поддерево и правое поддерево. В идеальном дереве высота hL левого поддерева равна высоте hR правого поддерева. Назовем дерево сбалансированным, если высоты левого и правого поддеревьев для каждой вершины отличаются не более чем на единицу.
Сбалансированные деревья не так уж плохи. В частности, идеальные деревья являются сбалансированными (лучшими из них).
Худшими из сбалансированных деревьев являются так называемые деревья Фибоначчи. Примером дерева Фибоначчи является
бинарное дерево, получающееся при последовательном создании вершин с информационными полями 8, 5, 11, 3, 7, 10, 12, 2, 4, 6, 7, 9, 1.
Согласно теореме Адельсона-Вельского и Ландиса высота сбалансированного дерева не превышает величины
При включении новой вершины в дерево может (но не обязательно) увеличиться высота одного из поддеревьев. Ситуации может быть три:
- вершина включается в поддерево меньшей высоты; его высота увеличивается на единицу, сбалансированность дерева улучшается;
- поддеревья имели одинаковую высоту; при включении новой вершины высота одного из них увеличивается на единицу, разность высот не превышает единицу, дерево остается сбалансированным;
- вершина включается в поддерево большей высоты; разность высот становится равной двум, дерево становится несбалансированным.
В третьем случае при включении вершины предпринимается перестройка дерева.
Что можно сделать? Видно, что ветви одного из поддеревьев, например, левого, слишком сильно опустились. Решением может быть: поднять левое поддерево на единицу и одновременно опустить на единицу правое. Эта модификация приводит к изменению корня. Поднимая левое поддерево (включая корень поддерева), делаем уровень корня поддерева более высоким, чем корень всего дерева. Следовательно, корень левого поддерева становится корнем всего дерева. Требуется изменить и некоторые связи между вершинами: поскольку корни меняются ролями, меняются на обратные и отношения "предок - потомок".
Для удобства дальнейшего изложения введем следующие обозначения: h(t) - высота дерева t; t = vuw - дерево, состоящее из левого поддерева v, корня и u правого поддерева w.
Ясно, что имеет место соотношение h(t) = 1 + max(h(v), h(w)).
Пусть до включения новой вершины в левое поддерево имело место равенство h(v) = h(w)+l. Представим, что дерево имеет вид t = (A×B)zR, т. е. корнем является z, правым поддеревом R, левое поддерево имеет корень x, и, в свою очередь, состоит из левого поддерева A и правого поддерева B. Соотношение высот: h(A)=h(B)=h(R). Новая вершина включается в поддерево A, после чего высота его увеличивается на единицу. Общее соотношение высот может стать равным h(v)=h(w)+2.
Преобразуем дерево t в новую форму: (A×B)zR => А×(ВzR).
Высоты поддеревьев A, B и R не изменились, но высота дерева t уменьшилась на единицу, и дерево стало сбалансированным.
Симметричная ситуация имеет место, если новая вершина включается в поддерево R дерева t = A×(BzR). В этом случае преобразование балансировки будет обратным: A×(ВzR) => (А×В)zR.
Если же новая вершина включается в поддерево B, то эти преобразования ничего не дают (поддерево B не поднимается).
Разбалансировка дерева за счет включения новой вершины в B требует более внимательно взглянуть на структуру этого поддерева. Выделим в нем корень, левое и правое поддеревья, В = CyD. Таким образом, исходное дерево будет представлено в виде t=(Ax(CyD))zR. Вершина, включенная в поддерево В и увеличившая высоту дерева t, принадлежит одному из поддеревьев С или D. Неважно, какому именно. Оба их можно поднять. Преобразование
(Ax(CyD))zR => (АxС)y(DzR)
разделяет поддеревья C или D, привязывая их к различным корням, и уменьшает высоту дерева t на единицу. Заметим, что все описанные преобразования меняют корень дерева t, что надо учитывать при написании списка формальных параметров процедур.
Напомним, что в сбалансированном дереве для каждой вершины должно выполняться условие отличия высот левого и правого поддеревьев не более чем на единицу. Поэтому, говоря выше о дереве t, имеется в виду не только дерево в целом, но любое поддерево, в котором нарушалась балансировка.
Дополнительную информацию по балансировке деревьев можно получить здесь.
На следующем шаге мы рассмотрим оптимизацию алгоритмов.
