Картинки из квадратов \ О гармоническом \ Бинарность \ Полные бинарные деревья \

10.4.4.15. Порождение Дерева при помощи операции сложения векторов

Начало см. здесь.
Начальная ситуация

Исходный пункт построения
Фиксируем на координатной плоскости единичные координатные векторы и :
Единичные координатные векторы и являются парой взаимно перпендикулярных ортов. В координатном виде векторы и записываются как вектор-столбцы высоты 2 в следующем виде:
Мы заменяем векторами и "дроби" и , с которых начинают построение Дерева Грэхем Р., Кнут Д., Паташник О. в своей книге "Конкретная математика":

Построение первой вставки
Складываем единичные координатные векторы и по "правилу параллелограмма" и получаем первую вставку — вектор . Представление о сложении векторов по "правилу параллелограмма" можно получить, например, в учебнике по аналитической геометрии Ильина В. А.,
Позняка Э. Г. здесь (см. особенно Рис. 2.4. на указанной странице).
В координатном виде это сложение будет выглядеть так:
То есть сложение вектор-столбцов происходит "покомпонентно": отдельно складываются первые и вторые компоненты соответствующих векторов. Более подробно об этом можно посмотреть у Кострикина А.И., Манина Ю.И. здесь (пункт 6 на указанной странице); либо у Б. Л. ван дер Вардена здесь.
Я использую символ в качестве символа для обозначения операции сложения векторов, чтобы отличать ее от операции сложения чисел, для обозначения которой будет использоваться обычный символ +.
Таким образом, я заменяю "дробь" , являющуюся "первой вставкой" в книге Грэхема Р., Кнута Д., Паташника О. "Конкретная математика":
на вектор .

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