6.4. ПИРАМИДЫ ИЛИ ТЕТРАРНЫЕ ДЕРЕВЬЯ
Пирамиды или тетрарные деревья представляют собой структуру данных, которая широко используется и в машинной графике, и в обработке изображений. Ее применение дает наилучшие результаты в случаях, когда изображение представляет собой некоторую квадратную матрицу А, размеры которой определяются некоторой степенью числа 2, скажем, 
Матрицу А можно разбить на четыре квадратные матрицы: 
размеры которых в два раза меньше размеров матрицы А. Процесс такого разбиения можно рекурсивно повторить 
раз до тех пор, пока не будет достигнут уровень выделения одного пиксела. Эти уровни можно пронумеровать, начиная с нуля, которым обозначается изображение в целом, вплоть до 
соответствующего отдельным пикселам. Каждый выделяемый квадрат можно пометить одним из четырех символов — О, 1, 2 или 3, приписываемых посредством конкатенации к метке породившего его квадрата. В результате отдельные пикселы будут снабжены метками, состоящими из 
символов. Эту конструкцию можно представить в виде дерево, вершины которого соответствуют отдельным квадратам. Вершины дерева соединяются, если квадрат, соответствующий одной из них, непосредственно содержится в квадрате, соответствующем другой.
Корень дерева соответствует изображению в целом, листья — отдельным пикселам, а все остальные вершины характеризуются степенью исхода, равной 4. Дерево такого вида обычно называют деревом четвертой степени или тетрарным деревом. Такое дерево
Рис. 6.3 Часть тетрарного дерева
представлено на рис. 6.3, а на рис. 6.4 приведена система адресации для изображения размерами 8X8. Поскольку 
уровень состоит из 4 квадратов, общее число вершин дерева равно
Следовательно, число вершин приблизительно на 33% превышает число пикселов. Оказывается, что при решении многих прикладных задач для запоминания дерева достаточно использовать только 
ячеек. Построение подобного тетрарного дерева будет рассмотрено ниже.
Рис. 6.4. Пример, характеризующий систему адресации пикселов изображения размерами 
, соответствующую конструкции некоторого тетрарного дерева: первый разряд обозначает вершину первого уровня, второй — вершину второго уровня и т. д.
