Лекции 13-14: деревья поиска, почти сбалансированные деревья.
Красно-черные деревья и реализация множества на их основе

Содержание лекции

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

• для любой нетерминальной вершины V значения во всех вершинах левого поддерева с корнем V должны быть меньше, чем значение в вершине V;
• значения во всех вершинах правого поддерева с корнем V должны быть больше, чем значение в вершине V.

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

Опишем более подробно устройство дерева поиска. Каждая вершина дерева представляет собой следующую структуру:

    class TreeNode {
    public:
        TreeNode* left;   // Указатель на левого сына
        TreeNode* right;  // Указатель на правого сына
        TreeNode* parent; // Указатель на отца
        void*     value;  // Указатель на значение в узле
                          // или на пару (ключ, значение ключа)
    };

В большинстве алгоритмов удобно считать, что у любой вершины v дерева есть родительская вершина. В противном случае пришлось бы многократно рассматривать отдельно случаи, когда указатель v->parent равен нулю. Используется следующий прием: вводится специальная "заголовочная" вершина header, которая присутствует даже у пустого дерева. Корень непустого дерева является левым сыном вершины header. Поле header->right всегда содержит нулевое значение. Всюду ниже мы будем считать, что используется заголовочная вершина header, левым сыном которой является корень дерева.

Алгоритм поиска

Запишем на псевдокоде алгоритм поиска в дереве. Мы ищем элемент x в поддереве с корнем root. Результатом поиска является вершина *node, определяемая следующим образом:

• если элемент x содержится в множестве, то *node — указатель на вершину, содержащую x;
• если элемент x не содержится в множестве, то *node — указатель на вершину, которая при добавлении x к множеству должна стать родительской для новой вершины V, содержащей x. Новая вершина V добавляется как терминальная, а у найденной вершины *node отсутствует левый сын, если x меньше значения в вершине *node, или правый сын, если больше.

int find(
    Вход:  E x,             // искомый элемент,
           TreeNode* root,  // указатель на вершину поддерева
    Выход: TreeNode** node  // найденная вершина
)
начало алгоритма
    TreeNode* v, vp;
    E y;
    int res = -1;
    v = root;
    vp = root;
    цикл пока v != 0
        y = v->value;       // y = значение в вершине v
        если x == y         // x равно значению в вершине =>
            *node = v;      //   запомним указатель на вершину
            return 0;       //   успешное завершение
        иначе если x < y    // x меньше значения в вершине =>
            vp = v;         //   запомним указатель на отца
            res = -1;       //   запомним результат сравнения
            v = v->left;    //   переходим к левому сыну
        иначе               // иначе     // x > y
            vp = v;         //   запомним указатель на отца
            res = 1;        //   запомним результат сравнения
            v = v->right;   //   переходим к правому сыну
        конец если
    конец цикла
                            // x не содержится в дереве
    *node = vp;             // *node = указатель на отца
    return res;
конец алгоритма

Число сравнений в данном алгоритме не превышает высоты дерева h. Таким образом, время работы алгоритма равно O(h).

Алгоритм добавления элемента

Добавление элемента к упорядоченному дереву легко реализуется с помощью алгоритма поиска. Сначала применяется описанный выше алгоритм find. Если вершина найдена, то в случае обычного множества ничего делать не надо; в случае нагруженного множества надо лишь изменить нагрузку элемента. Для простоты мы ограничимся в дальнейшем случаем обычного множества.

Если элемент не содержится в дереве, то алгоритм find находит вершину, которая должна стать родительской для новой вершины. Новая вершина, содержащая добавляемый элемент множества, становится левым или правым сыном найденной вершины в зависимости от величины добавляемого элемента в сравнении с элементом в родительской вершине. Для определения того, каким сыном должен стать новый узел, используется значение последнего сравнения, которое возвращается алгоритмом find. Запишем на псевдокоде алгоритм insert добавления вершины после выполнения поиска.

алгоритм insert(
    Вход:  TreeNode* parentNode, // родительская вершина,
                                 // найденная при поиске
           E x,          // добавляемый элемент
           int compare   // результат сравнения x со
)                        //     значением в вершине parentNode
начало алгоритма
    TreeNode* n = new TreeNode; // создать новую вершину дерева
    n->left = 0; n->right = 0;  // новая вершина терминальная
    n->parent = parentNode;     // она будет ребенком найденной вершины
    n->value = x;
    если compare < 0            // если x меньше, чем значение в вершине
        parentNode->left = n;   //     добавляем n как левого сына
    иначе                       // иначе
        parentNode->right = n;  //     добавляем n как правого сына
    конец если
конец алгоритма

Поиск минимального и максимального элементов поддерева

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

TreeNode* minimalNode(
    Вход: TreeNode* subTreeRoot // указатель на вершину поддерева
)
начало алгоритма
    RBTreeNode* x = subTreeRoot;
    цикл пока (x != 0 && x->left != 0)
        x = x->left;
    конец цикла
    return x;
конец алгоритма

Алгоритм обхода вершин дерева поиска

Для упорядоченного дерева очень важен алгоритм обхода вершин в соответствии с их порядком. Обход начинается с вершины, содержащей минимальное значение. Затем находим вершину, содержащую следующее значение, и так далее. Алгоритм заканчивается, когда очередной вершиной является "заголовочная" вершина header (родитель для корня дерева).

Для обхода используется алгоритм nextNode, который по данному указателю на вершину node находит указатель на вершину, содержащую следующее значение. Отметим, что для максимальной вершины дерева следующей является "заголовочная" вершина header.

Алгоритм реализуется очень просто: если у вершины node есть правый сын, то возвращается минимальная вершина правого поддерева; иначе, если node является левым сыном своего отца, то возвращаем указатель на отца. Наконец, если оба эти условия не выполняются, т.е. node есть правый сын своего отца и у него нет правого сына, то в цикле идем вверх по дереву, пока текущий узел является правым сыном своего отца. После цикла текущий узел является левым сыном своего отца. Возвращаем ссылку на отца.

Приведенные ниже рисунки иллюстрируют три эти случая. Буквой V обозначена текущая вершина, буквой N — вершина, которая содержит следующее значение. Отметим, что алгоритм нигде не использует сравнения значений, содержащихся в вершинах дерева.

Случай 1: у вершины V есть правый сын.

Случай 2: у вершины V нет правого сына, и она является левым сыном своего отца.

Случай 3: у вершины V нет правого сына, и она является правым сыном своего отца.

TreeNode* nextNode(
    Вход: TreeNode* node
)
начало алгоритма
    если (node->right != 0)                 // у node есть правый сын
        return minimalNode(node->right)
    иначе если (node == node->parent->left) // node -- левый сын
        return node->parent;
    иначе
        RBTreeNode* x = node->parent;
        цикл пока (x == x->parent->right)   // пока x -- правый сын
            x = x->parent;                  //     идем вверх по дереву
        конец цикла
        утв: x -- левый сын своего отца
        return x->parent;
    конец если
конец алгоритма

Алгоритм previousNode, который по указателю на вершину дерева находит указатель на предыдущую вершину, реализуется аналогично.

Сбалансированные деревья

Рассмотрим произвольное дерево поиска. В худшем случае время работы алгоритма поиска равняется длине максимального пути от корня дерева к терминальной вершине, т.е. высоте дерева. Для того, чтобы поиск выполнялся по возможности быстрее, дерево должно иметь минимальную высоту при заданном числе вершин. Для этого нужно, чтобы все возможные пути к терминальным вершинам имели бы примерно одинаковую длину (более точно, для любой вершины дерева число вершин в ее левом и правом поддеревьях почти совпадали).

Перейдем к строгим определениям. Удобно считать, что у каждой вершины дерева есть ровно два сына. Для этого добавим к дереву внешние, или нулевые вершины. Если у какой-либо вершины дерева отсутствует левый или правый сын, то добавляем внешнюю вершину и считаем ее левым или правым сыном соответственно. Для терминальных вершин добавляются два внешних сына. Внешние вершины будем также называть листьями. Обычные вершины дерева будем называть собственными вершинами, причем слово "собственные" иногда будем опускать.

При программировании на Си внешние дети вершины t соответствуют нулевым значениям указателей t->left и t->right. Добавление внешних вершин к дереву показано на рисунке. Внешние вершины (нулевые вершины, листья) изображены прямоугольниками серого цвета, внутри которых написано слово Null, символизирующее нулевой указатель.

Длиной пути от корня дерева к внешней вершине будем называть число собственных вершин этого пути (т.е. последняя внешняя вершина не считается).

Определение. Дерево называется сбалансированным, или полным, если длины всех путей от корня к внешним вершинам равны между собой. Дерево называется почти сбалансированным, если длины всевозможных путей от корня к внешним вершинам отличаются не более, чем на единицу.

На рисунке приведены примеры сбалансированного и почти сбалансированного деревьев.

Справедливы следующие утверждения (их доказательства опущены ввиду тривиальности).

Предложение 1. Число собственных вершин в сбалансированном дереве высоты h равно 2^h-1.

Следствие 2. Высота сбалансированного дерева, содержащего n собственных вершин, равна log₂(n+1).

Предложение 3. Число вершин произвольного дерева не превосходит числа вершин сбалансированного дерева той же высоты.

Следствие 4. Для высоты h произвольного дерева, содержащего n вершин, справедливо неравенство: h ≥ log₂(n+1).

Эффективность реализации множества с помощью дерева поиска зависит от текущей высоты дерева, т.к. при выполнении большинства операций сначала происходит поиск элемента, а время работы алгоритма поиска пропорционально высоте. При заданном числе вершин n наименьшую высоту имеет сбалансированное или почти сбалансированное дерево (последнее в случае, когда n не равно 2^h-1). Если дерево почти сбалансировано, то время поиска не превосходит log₂(n) + 1. Однако в случае произвольного дерева время поиска может в худшем случае линейно равняться n (если дерево вытянуто в прямую линию). Поэтому при добавлении элементов к множеству желательно перестраивать дерево так, чтобы сохранялось то или иное свойство, близкое к сбалансированности. Это гарантирует быстрое выполнение поиска.

Предложение 5. Пусть существует константа C ≥ 1 такая, что длины всех путей от корня к внешним вершинам (листьям) дерева отличаются не более чем в C раз. Более точно, пусть m₀ — длина минимального пути, m₁ — максимального, и выполняется неравенство m₁ ≤ C m₀. Тогда высота дерева не превосходит C log₂(n+1), где n — число собственных вершин дерева.

Доказательство.  Пусть h — высота дерева. Из условия предложения вытекает, что длины всех путей от корня к листьям дерева не меньше чем h/C. Следовательно, дерево содержит сбалансированное поддерево высоты l ≥ h/C. Поэтому число n всех вершин дерева не меньше, чем число вершин сбалансированного поддерева. По предложению 1, число вершин сбалансированного поддерева высоты l равно 2^l-1. Следовательно,

  n ≥ 2^l-1 ≥ 2^h/C-1,
  log₂(n+1) ≥ h/C,
  h ≤ C log₂(n+1).

Предложение доказано.

Будем называть дерево, удовлетворяющее условию предложения 5, почти сбалансированным с баланс-фактором C, где C ≥ 1. Для таких деревьев время поиска логарифмически зависит от числа вершин:

  t = O(log₂n),

где константа в представлении O-большого равна C. В практическом программировании константы в оценке времени работы алгоритма не очень важны — существенна лишь зависимость времени работы от n. Логарифмическая зависимость — наилучшая из всех возможных, поэтому в классе почти сбалансированных деревьев с баланс-фактором C поиск выполняется за оптимальное время.

Можно показать, что при добавлении случайных элементов к дереву поиска с помощью рассмотренного выше алгоритма, в котором новая вершина добавляется как терминальная после выполнения поиска родительской вершины, сбалансированность "в среднем" сохраняется, т.е. с большой вероятностью баланс-фактор не будет превышать, скажем, двух. Тем не менее существует несколько схем модификации деревьев после добавления и удаления вершин, при которых баланс-фактор всегда будет ограничен при любом сценарии добавления. Наиболее популярны два класса сбалансированных деревьев: AVL-деревья и красно-черные деревья.

AVL-деревья названы так в честь двух авторов, впервые предложивших их: Адельсона--Вельского и Ландиса. Каждая вершина AVL-дерева хранит дополнительно разность высот ее левого и правого поддеревьев, причем эта разность в AVL-дереве может принимать лишь три значения: -1, 0, 1. Можно показать, что для AVL дерева длина максимального пути корня к внешнему листу не превышает константы 1.5, умноженной на длину минимального пути, т.е. баланс-фактор в смысле использованного выше определения равен 1.5. (Более точно, баланс-фактор для достаточно больших n не превышает квадратного корня из двух.) Следовательсно, поиск в AVL-деревьях осуществляется за логарифмическое время.

Красно-черные деревья

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

• корень дерева окрашен в черный цвет;
• у красной вершины дети черные (если они есть);
• всякий путь от корня дерева к внешней вершине (листу) содержит одно и то же число черных вершин.

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

Для удобства описания алгоритмов мы будем считать также, что все внешние вершины окрашены в черный цвет, а заголовочная вершина дерева (та, которая является родительской для корня дерева) — в красный.

Пример красно-черного дерева приведен на рисунке. Черные вершины изображаются кружками серого цвета, красные вершины — белого.

Пусть h_b — черная высота красно-черного дерева, т.е. количество черных вершин в произвольном пути от корня дерева к внешней вершине (не включая саму внешнюю вершину). По определению красно-черного дерева, эта величина определена корректно (не зависит от пути). Для дерева, изображенного на рисунке, h_b=2. Поскольку любой путь от корня к внешней вершине начинается с черной вершины (в красно-черном дереве корень всегда черный) и не может содержать двух красных вершин подряд (у красной вершины дети обязательно черные), то длина любого пути не превосходит 2h_b. С другой стороны, длина минимального пути к внешней вершине не меньше чем h_b. Таким образом, в случае красно-черного дерева для длин m₀ и m₁ минимального и максимального путей к внешним вершинам выполняются неравенства

  m₁ ≤ 2 h_b,

  m₀ ≥ h_b,

  m₁ ≤ 2 m₀.

Таким образом, красно-черное дерево является почти сбалансированным с баланс-фактором 2. Из предложения 5 вытекает логарифмическая оценка на высоту h красно-черного дерева, содержащего n вершин:

  h   ≤ 2 log₂(n+1).

Поиск элемента в красно-черном дереве осуществляется за логарифмическое время:

  t = O(log₂n),

где константа в представлении O-большого равна двум.

Добавление элементов в красно-черное дерево

При добавлении нового элемента к красно-черному дереву мы сначала применяем обычный алгоритм добавления вершины к дереву поиска, который был рассмотрен выше (алгоритм insert). Новая вершина (она в рассмотренном алгоритме всегда является терминальной) окрашивается в красный цвет. Если родительская вершина для добавленной имеет черный цвет, то все свойства красно-черного дерева при этом сохраняются, и никаких дополнительных действий не требуется. Однако, если родительская вершина красная, то нарушается требование того, что дети красной вершины должны быть черными, и нужно выполнить процедуру восстановления структуры красно-черного дерева. Обычно эта процедура называется восстановлением баланса или ребалансировкой. В алгоритме ребалансировки с деревом совершаются локальные действия, не меняющие упорядоченности его вершин. Действия бывают двух типов:

• перекрашивание вершин дерева,
• вращение вершины дерева влево или вправо.

Операция вращения вершины дерева

Определим преобразования вращения. Левое вращение вершины x :

Правое вращение вершины x :

По рисункам видно, что оба преобразования не меняют упорядоченности вершин дерева. Преобразования носят локальный характер, при их выполнении меняется лишь фиксированное число ссылок в вешинах дерева вблизи вершины, которая "вращается" влево или вправо. Запишем на псевдокоде процедуру вращения вершины x влево.

void rotateLeft(
    Вход: TreeNode* x
)
начало алгоритма
    TreeNode* y = x->right; // y -- правый сын x
    утв: y != 0

    // Узлы x и y меняются местами (подчиненный "y" бывшего
    // начальника "x" становится новым начальником)
    // Делаем y корнем модифицированного поддерева
    TreeNode* p = x->parent;
    y->parent = p;
    если (x == p->left) // x -- левый сын своего отца
        p->left = y;
    иначе               // x -- правый сын своего отца
        p->right = y;
    конец если

    // Бывший левый сын узла "y" становится правым сыном узла "x"
    x->right = y->left;
    если (y->left != 0)
        y->left->parent = x;
    конец если

    // Бывший начальник "x" становится подчиненным нового начальника "y"
    y->left = x;
    x->parent = y;
конец алгоритма

Правое вращение вершины x реализуется аналогично.

Операция левого или правого вращения вершины во многих случаях позволяет "исправить" балансировку дерева, как показывает следующий пример. В нем мы применяем вращение вершины x влево.

Восстановление структуры красно-черного дерева после добавления вершины (ребалансировка)

В процедуре ребалансировки рассматриваются 6 различных случаев. В случаях 1-3 отец узла x является левым сыном своего отца, т.е. деда x.

1. У узла x есть красный "дядя" (брат отца x). При этом x может быть левым или правым сыном своего отца — случаи эти рассматриваются аналогично.
   
2. У узла x "дядя" (брат отца) либо черный, либо его вообще нет (т.е. сыном является лист или внешний узел, который мы также считаем черным), и узел x является правым сыном своего отца.
   
3. У узла x "дядя" (брат отца) либо черный, либо его вообще нет, и узел x является левым сыном своего отца.
   

Случаи 4-6 зеркально симметричны случаям 1-3, в них отец узла x является правым сыном своего отца, т.е. деда x. Рассматриваются они аналогично случаям 1-3 заменой слова "левый" на "правый" и обратно, так что мы их описывать не будем.

Укажем, какие действия выполняются в каждом из случаев 1-3 для восстановления балансировки дерева.

Случай 1 (красный дядя)

Этот случай наиболее прост:

• перекрашиваем отца и дядю узла x в черный цвет;
• перекрашиваем деда узла x в красный цвет;
• перемещаем метку x вверх по дереву на деда узла x: и переходим в цикле к восстановлению нового узла x (деда предыдущего x)
       x = x->parent->parent
  

Цикл завершается, либо когда мы достигли корня дерева (если корень был перекрашен в красный цвет, то надо перекрасить его обратно в черный), либо когда отец узла x черный.

Случай 2 (дядя черный или его вообще нет, узел x является правым сыном своего отца)

Этот случай сводится к случаю 3 путем следующих преобразований:

• перемещаем метку x на вверх по дереву: x = x->parent;
• левое вращение x.

Случай 3 (дядя черный или его вообще нет, узел x является левым сыном своего отца)

В этом случае выполняются следующие действия:

• перекрашиваем отца узла x в черный цвет;
• перекрашиваем деда (т.е. отца отца) x в красный;
• выполняем правое вращение деда x.

Отметим, что всего в процедуре восстановления структуры красно-черного дерева (ребалансировки) может выполняться не более O(h) операций; поскольку для красно-черного дерева h  ≤  2 log₂(n+1), получаем, что время выполнения ребалансировки равно O(log₂ n). В этой процедуре выполняются перекрашивание узлов дерева и операции вращения, причем общее число вращений — не больше двух (одно вращение в случае 3 и два в случае 2).

Проект "TreeSet": файл TreeSet.zip