На этом шаге мы рассмотрим метод балансировки.
При проектировании некоторых алгоритмов приходиться идти на различные компромиссы, т.е. по возможности сбалансировать вычислительные затраты на использование различных частей алгоритмы. Метод балансировки рассматривается как балансировка деревьев. Дерево - важная структура данных, применяемая для хранения, обработки и предоставления информации. Дерево состоит из элементов, обычно называемых вершинами или углами, и связей между вершинами, называемыми дугами, ребрами или ссылками. Среди вершин выделяется одна, которая называется корнем. Она является родительской по отношению к другим связанным с ней вершинам. Все вершины, связанные с корнем дугами, называются потомками. Каждая вершина в дереве, кроме корня, имеет точно одну родительскую вершину и больше потомков. Дерево имеет два свойства:
- оно связано: из корня нужно пройти по дугам к каждой вершине;
- оно не содержит циклов, т.е. замкнутых последовательностей вершин и дуг.
В компьютерных науках часто используются деревья, в которых все вершины содержат ограниченное число потомков (не более двух).
Если это число 2 (0,1,2), то такие деревья называются бинарными. Если у вершины два потомка, то дерево делится на левое поддерево и правое. Различают идеальные и вырожденные деревья.
Идеальное дерево - дерево, в котором все вершины располагаются на k уровнях: корень - на 1-м, две вершины на 2-м, четыре - на 3-м. Новая вершина может быть помещена только на k+1 уровень.
Вырожденное дерево - дерево, которое представляет собой линейный список элементов, упорядоченных по возрастанию или убыванию информационных полей.
Критерий качества дерева - это длина самой длинной ветви. На единицу от этого значения отличается количество уравнений дерева, т.е. его высота (на единицу меньше). Деревья минимальной высоты имеют максимальное количество вершин на одном уровне. Таким образом хорошие с точки зрения поиска и вставки вершины - это деревья минмальной высоты. Они имеют минимальное количество вершин на каждом уровне.
Метод балансировки - метод позволяющий не допустить слишком плохих деревьев.
Суть: дерево называется сбалансированным, если высота hl левого поддерева и высота hr правого поддерева для каждой вершины отличаются не более чем на единицу. Лучшие из сбалансированных деревьев являются идеальными. При включении новой вершины в дерево может (но не обязательно) увеличиваться высота одного из деревьев.
Возможно 3 ситуации.
- Вершина включается в поддерево меньшей высоты, его высота увеличивается на единицу, дерево становиться сбалансированным (идеальным).
- Поддеревья имеют одинаковую высоту. При включении новой вершины, высота одной из них увеличивается на единицу, дерево остается сбалансированным.
- Вершина включается в поддерево большей высоты, разность высот становиться равной двум. Дерево становится не сбалансированным. Варианты решения: нужно ветви одного из поддеревьев поднять на одну единицу и одновременно на единицу опустить другое. Эта модификация приводит к изменению формы дерева. Поднимая левое поддерево, включая его корень, мы, тем самым, делаем уровень корня левого поддерева выше, чем корень самого дерева. Следовательно, корень левого поддерева становиться корнем всего дерева. В этом случае придется изменить некоторые связи между вершинами, так как если корни меняются ролями, то на обратное меняется и отношения предок-потомок.
На следующем шаге мы рассмотрим метод Лагранжевых релаксаций.
