Начало см. здесь.

Настоящий Раздел носит вспомогательный характер и призван собрать воедино сведения главным образом справочного и технического характера, на которые было бы удобно ссылаться по ходу изложения. Поскольку мы будем интенсивно использовать понятие "дерева" в контексте Computer Science (и как здесь), то зафиксируем соответствующую терминологию.

Особое внимание уделим вопросам разметки нужных нам деревьев. Этих разметок может быть потенциально очень много и все они по своему важны. Так что в их многообразии важно не запутаться.

2. Неупорядоченные ориентированные деревья

Первоначальным для нас будет определение неупорядоченного ориентированного дерева, как оно приведено у Ахо-Ульмана. Мы принимаем также их соглашение о том, что "рисуя деревья, мы будем помещать корень вверху и направлять все дуги вниз". Это соглашение позволит нам не рисовать стрелки на дугах дерева. Один из примеров нарисованного таким образом неупорядоченного ориентированного дерева приведен ниже:

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

Для каждого неупорядоченного ориентированного дерева определено также понятие корня.

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

3. Упорядоченные бинарные деревья

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

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

Таким образом, приведенное выше неупорядоченное дерево, рассматриваемое теперь уже как упорядоченное дерево, изобразится следующим образом:

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

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

4. Полные бинарные деревья

Основными объектами нашего интереса будут полные бинарные деревья. Конечные и бесконечные. Стандартное определение конечного полного бинарного дерева приведено у Ахо-Хопкрофта-Ульмана здесь: "Двоичное дерево называется полным, если для некоторого целого числа k каждый узел глубины меньшей k имеет как левого, так и правого сына и каждый узел глубины k является листом".

Каждое конечное полное бинарное дерево является некоторым частным случаем определенного выше упорядоченного бинарного дерева.

Высотой полного бинарного дерева называется длина пути из его корня в какой-нибудь его лист. Таким образом, высота изображенного ниже полного бинарного дерева равна двум.

Полное бинарное дерево высоты k имеет ровно 2^{k + 1} - 1 вершин. В частности, приведенное полное бинарное дерево высоты 2 имеет ровно 7 вершин.

5. Размеченные полные бинарные деревья

Все же, основными объектами нашего интереса будут не просто полные бинарные деревья, а полные бинарные деревья определенным образом размеченные. Определение понятия разметки вершин и дуг упорядоченного графа (частным случаем которого является полное бинарное дерево) приведено у Ахо-Ульмана здесь.

В частном случае полного бинарного дерева высоты 2 нас будут интересовать следующие две уже рассмотренные разметки:

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

Далее покажем, что все эти четыре размеченные дерева имеют вполне определенный арифметический смысл (как и рассмотренные ранее два из них). Они будут также естественным образом ассоциированы с четырьмя цепочками Базового УСК степени 3. Об арифметическом смысле двух из этих деревьев говорилось здесь и здесь.