– структура данных, представляющая собой древовидную структуру в виде набора связанных узлов.

Это конечное множество элементов, которое либо пусто, либо содержит элемент (корень ), связанный с двумя различными бинарными деревьями, называемыми левым и правым поддеревьями . Каждый элемент бинарного дерева называется узлом . Связи между узлами дерева называются его ветвями .

Способ представления бинарного дерева:

• A — корень дерева
• В — корень левого поддерева
• С — корень правого поддерева

Корень дерева расположен на уровне с минимальным значением.

Узел D , который находится непосредственно под узлом B , называется потомком B . Если D находится на уровне i , то B – на уровне i-1 . Узел B называется предком D .

Максимальный уровень какого-либо элемента дерева называется его глубиной или высотой .

Если элемент не имеет потомков, он называется листом или терминальным узлом дерева.

Остальные элементы – внутренние узлы (узлы ветвления).

Число потомков внутреннего узла называется его степенью . Максимальная степень всех узлов есть степень дерева.

Число ветвей, которое нужно пройти от корня к узлу x , называется длиной пути к x . Корень имеет длину пути равную 0 ; узел на уровне i имеет длину пути равную i .

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

Имеется много задач, которые можно выполнять на дереве.

Распространенная задача - выполнение заданной операции p с каждым элементом дерева. Здесь p рассматривается как параметр более общей задачи посещения всех узлов или задачи обхода дерева.

Если рассматривать задачу как единый последовательный процесс, то отдельные узлы посещаются в определенном порядке и могут считаться расположенными линейно.

Способы обхода дерева

Пусть имеем дерево, где A - корень, B и C - левое и правое поддеревья.

Существует три способа обхода дерева:

• Обход дерева сверху вниз (в прямом порядке): A, B, C — префиксная форма.
• Обход дерева в симметричном порядке (слева направо): B, A, C — инфиксная форма.
• Обход дерева в обратном порядке (снизу вверх): B, C, A — постфиксная форма.

Реализация дерева

Узел дерева можно описать как структуру:

struct tnode {

Int field; // поле данных

Struct tnode *right; // правый потомок
};

При этом обход дерева в префиксной форме будет иметь вид

if (tree!=NULL) {

cout << tree->field; //Отображаем корень дерева

Обход дерева в инфиксной форме будет иметь вид

void treeprint(tnode *tree) {

if (tree!=NULL) { //Пока не встретится пустой узел

cout << tree->field; //Отображаем корень дерева

Обход дерева в постфиксной форме будет иметь вид

void treeprint(tnode *tree) {

if (tree!=NULL) { //Пока не встретится пустой узел

cout << tree->field; //Отображаем корень дерева

Бинарное (двоичное) дерево поиска – это бинарное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):

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

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

Как правило, информация, представляющая каждый узел, является записью, а не единственным полем данных.

Для составления бинарного дерева поиска рассмотрим функцию добавления узла в дерево.

Добавление узлов в дерево

struct tnode * addnode(int x, tnode *tree) {

If (tree == NULL) { // Если дерева нет, то формируем корень

tree =new tnode; // память под узел

tree->field = x; // поле данных

tree->left = NULL;

tree->right = NULL; // ветви инициализируем пустотой

}else if (x < tree->field) // условие добавление левого потомка

tree->left = addnode(x,tree->left);

Else // условие добавление правого потомка

tree->right = addnode(x,tree->right);

Return (tree);
}

Удаление поддерева

void freemem(tnode *tree) {

If (tree!=NULL) {

freemem(tree->left);

freemem(tree->right);

Delete tree;

Пример Написать программу, подсчитывающую частоту встречаемости слов входного потока.

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

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

В дереве каждый узел содержит:

• указатель на текст слова;
• счетчик числа встречаемости;
• указатель на левого потомка;
• указатель на правого потомка.

Рассмотрим выполнение программы на примере фразы

При этом дерево будет иметь следующий вид

Пример реализации

#include
#include
#include
#include
#define MAXWORD 100
struct tnode { // узел дерева

Char *word; // указатель на строку (слово)

Int count; // число вхождений

Struct tnode *left; // левый потомок

Struct tnode *right; // правый потомок
};
// Функция добавления узла к дереву
struct tnode *addtree(struct tnode *p, char *w) {

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

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

Построение kd-дерева

Алгоритм построения kd-дерева можно представить следующим образом (будем называть прямоугольный параллелепипед англоязычным словом "бокс" (box)).

"Добавить" все примитивы в ограничивающий бокс. Т.е построить ограничивающий все примитивы бокс, который будет соответствовать корневому узлу дерева.

Если примитивов в узле мало или достигнут предел глубины дерева, завершить построение.

Выбрать плоскость разбиения, которая делит данный узел на два дочерних . Будем называть их правым и левым узлами дерева.

Добавить примитивы, пересекающиеся с боксом левого узла в левый узел, примитивы, пересекающиеся с боксом правого узла в правый.

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

1. Выбрать плоскость разбиения по центру.

Самый простой способ - выбирать плоскость по центру бокса. Сначала выбираем ось (x, y или z), в которой бокс имеет макимальный размер, затем разбиваем бокс по центру.

Рисунок 1 : Разбиение по центру

Этот способ имеет плохую адаптивность. Классическое октодерево имеет те же недостатки. Интуитивно можно описать причину плохой скорости на таких деревьях тем, что в каждом узле достаточно много пустого пространства, через которое луч траверсится (проходи через дерево во время поиска) в то время как пустое пространство должно сразу-же по-возможности отбрасываться. Более строгое объяснение будет дано чуть позже.

2. Выбрать плоскость по медиане.

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

Рисунок 2 : Разбиение по медиане

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

3. Surface Area Heuristic (SAH)

Каковы же критерии хорошо-построенного kd-дерева? На интуитивном уровне это на самом деле это не очень понятно, хотя выражение "как можно больше пустого пространство должно быть отброшено как можно быстрее" наверное подойдет.

Используем формальный подход. Введем функцию стоимости прослеживания (cost traversal), которая будет отражать, насколько дорого по вычислительным ресурсам прослеживать данный узел случайным набором лучей. Будем вычислять ее по следующей формуле.

SAH(x) = CostEmpty + SurfaceArea(Left)*N(Left) + SurfaceArea(Right)*N(Right)

Где CostEmpty - стоимость прослеживания пустого узла (некоторая константа), SurfaceArea - площадь поверхности соответствующего узла, а N - число примитивов в нем. Нужно выбирать плоскость разбиениея так, чтобы минимизировать эту функцию. Аргумент функции x является одномерной координатой плоскости разбиения.

Хорошими кандидатами на минимум SAH могут служить границы примитивов. Простой алгоритм посторения выглядит следующим образом. Каждый раз при выборе плоскости нужно перебрать всевозможные границы примитивов по трем измерениям, вычислить в них значение функции стоимости и найти минимум среди всех этих значений. Когда мы вычисляем SAH для каждой плоскости, то нам необходимо знать N(left) и N(right) - количества примитивов справа и слева от плоскости. Если вычислять N простым перебором, в итоге получится квадратичный по сложности алгоритм построения.

Рисунок 3 : Разбиние с учетом SAH

На рисунке 4 можно увидеть, что SAH сразу отбрасывает большие пустые пространства, плотно ограничивая геометрию.

Рисунок 4 : kd-дерево, построенное с учетом SAH

Surface Area Heuristic порождает более интеллектуальный критерий остановки, чем предел глубины дерева или малое количество примитивов. Если для выбранной плоскости разбиения суммарная стоимость прослеживания дочерних узлов больше, чем стоимость прослеживания текущего узла как листа (то есть по формуле SurfaceArea(Node)*N(Node)), то посторение дерева следует остановить.

4. Быстрое построение kd дерева

Вариант 0

Разбивайте по центру, выбирая ось, по которой размер бокса максимален. Этот способ самый быстрый, но на некоторых сценах трассировка лучей в таком дереве примерно в 2-3 раза медленнее.

Вариант 1

Самое простое что можно сделать чтобы ускорить построение - это снизить количество перебираемых плоскостей. Вместо того, чтобы перебирать N плоскойстей (где N - количество примитивов), можно вычислить SAH лишь в небольшом числе заранее фиксированных мест. Входной бокс равномерно разбивается по каждой оси на M частей. Обычно M лежит в пределах от нескольких десятков до пары сотен. N(left) и N(right) попрежнему вычисляются перебором, но теперь нам придется сделать полный перебор по массиву всего лишь M раз, а не N. Таким образом, алгоритм приобретает сложность N*M. Фактически, мы достигли ускорения за счет огрубления SAH, дискретизовав ее. Однако оказывается, что значение минимума полученной грубой функции как правило не сильно отличается от ее точного минимума.

Вариант 2

Что можно сделать, чтобы ускорить вариант 1? Нужно избавиться от полного перебора во время вычисления N(left) и N(right). Для этого построим дерево, в каждом узле которого записана некоторая разбивающая плоскость и количество примитивов справа и слева от плоскости. struct IntervalTree

Float split;

Int numPrimsOnLeftSide;

Int numPrimsOnRightSide;

IntervalTree* left;

IntervalTree* right;

На самом деле нам потребуется три таких дерева на каждом уровне - по одному на x,y,z. Входной интервал каждый раз будем делить пополам. Имея такое дерево, можно за log(N) операций достаточно точно определить количество примитивов справа и слева от плоскости. Алгоритм поиска в дереве выглядит достаточно просто.

vec2i IntervalTree::TraversePlane(

Int onRightSide = prims .size ()-i ;

// ...

Число onLeftSide мы знаем абсолютно точно, а вот число onRightSide - не совсем. Дело в том, что плоскость может разбивать некоторые примитивы и в этом случае один и тот же примитив лежит как справа от плоскости, так и слева, что данный алгоритм не учитывает. На практике эта проблема практически себя не проявляет.

Вариант 4

Можно ускорить поиск минимума ф-ии SAH, использовуя како-нибудь метод минимизации с несколькими начальными приближениями. Скажем, метод золотого сечения. В данном случае мы так же избавляемся от метода полного перебора. Нужно только учитывать, что SAH приобретает более-менее гладкую форму только при большом числе примитивов. Плюс этого подхода в том, что вычисление SAH брутфорсом легко перекладывается на GPU. Поэтому оценивая каждый раз SAH грубой силой и сведя количество оценок к небольшому числу (~10-20 max), можно строить kd дерево таким методом очень быстро.

Вариант 5 (Binning)

Часто используют именно этот вариант . Ссуть состоит в следующем:

Нужно поделить пространство на регулярные интервалы по x,y и z. Каждый такой интервал называется корзиной (bin). Обычно ограничиваются небольшым числом корзин ~32.

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

Прослеживание луча в kd-дереве на CPU

Классический алгоритм бинарного поиска в kd деревьях (kd-tree traversal в англоязычной литературе), применяющийся в большинстве CPU реализаций, состоит примерно в следующем. На первом шаге алгоритма необходимо посчитать пересечение луча с ограничивающим сцену корневым параллелепипедом и запомнить информацию о пересечении в виде двух координат (в пространстве луча) – t_near и t_far, обозначающих пересечение с ближней и дальней плоскостями соответственно. На каждом следующем шаге необходима информация только о текущем узле (его адрес) и этих двух координатах.

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

Рисунок 5 : Прослеживание луча в kd дереве

В случае A (t_split >= t_far) или B (t_split < t_near) луч пересекает только один дочерний узел, поэтому можно просто отбросить правый (соответственно левый) узел и продолжить поиск пересечения в оставшемся узле.

В случае C луч пересекает оба дочерних узла, поэтому необходимо сначала поискать пересечение в ближнем узле и если оно не найдено, искать его в дальнем. Так как в общем случае неизвестно, сколько раз произойдет последнее событие, необходим стек. Каждый раз, когда луч пересекает оба дочерних узла, адрес дальнего узла, t_near и t_far помещаются в стек и поиск продолжается в ближнем. Если в ближнем узле пересечение не найдено, из стека достаются адрес дальнего узла, t_near, t_far и поиск продолжается в дальнем узле.

Прослеживание луча в kd-дереве на GPU

Так как на GPU изначально отсутствует стек, появились бесстековые алгоритмы и алгоритмы, использующие искусственный стек небольшой длины. На GPU известны пять алгоритмов прослеживания пути луча - restart, backtrack, push- down, short stack и алгоритм прослеживания в kd дереве со связками.

kd-tree restart

Рисунок 2 :работа restart алгоритма .

Когда луч не находит пересечение в листе, его t_far приравнивается к t_near и поиск продолжается с корня kd-дерева (рис. 2). Грубо говоря, просто подвигается origin луча - то есть его точка испускания и поиск начинается сначала. Это приводит к тому, что луч проходит по одним и тем же узлам много раз, что неэффективно .

kd-tree push-down

Небольшая модификация restart алгоритма, заключающаяся в том, что луч стартует не с корня дерева, а с некоторого поддерева. Однако, в качестве нового поддерева узел может быть выбран, только если в течение всего спуска к нему не встретилось ни одного узла, в котором луч бы пересекал оба дочерних узла.

То есть, если при спуске по ближайшим узлам kd дерева хотя бы один раз встретился узел, в котором луч пересекает и ближний и дальний дочерние узлы, то именно этот дальний дочерний узел должен выть выбран в качестве поддерева. Далее, если луч промахнулся, рестарт будет произведен с запомненного дальнего узла и можно опять попытаться найти новое поддерево . Фактически, это попытка завести стек длинной 1 элемент.

kd-tree short stack

Авторы также использовали короткий стек. Пока размера стека хватает, идет его заполнение аналогично классическому алгоритму. Когда стек переполняется, он начинает работать как кольцевой буффер. Если стек пуст, необходимо произвести рестарт. Например, если в стеке длинной 4 содержаться узлы с номерами (1), (4), (6), (8), то при добавлении нового элемента (12), стек будет иметь следующий вид: (12), (4), (6), (8). То есть будет затерт первый элемент. Удаляться элементы будут в том порядке в каком они добавлялись (то есть сначала 12, потом 8, 6 и наконец 4), но когда из стека будет удален элемент (4), нужно будет произвести рестарт, так как мы затерли элемент (1). Смысл короткого стека в том, что он сильно сокращает количество restart-ов, которое приходится делать лучу.

kd-tree backtrack

Если сохранять в узлах kd дерева ссылку на родительские узлы, в случае промаха по этой ссылке можно добраться до родителя. Кроме того, потребуется хранить в каждом узле его ограничивающий паралеллипипид, чтобы иметь возможность вычислить новый t_far в случае промаха.

Ct_near можно поступить так же, как и в случае restart алгоритма . Это потребует дополнительно 6*4 (для координат паралеллипипида) + 4 (для ссылки на родителя) = 28 байт. Так как память на GPU довольно ограничена, такое расточительство может создать проблемы. К тому же, каждый раз при подъеме придется считать пересечение луча и выровненного по осям паралеллипипида, что конечно не бесплатно по вычислительным ресурсам. Следует особо отметить, что kd дерево с сохраненными паралеллипипид будет занимать намного больше памяти, чем хорошо построенное BVH дерево в этой же сцене. Основная причина здесь в том, что в kd дереве паралеллипипиды будут иметь больше общих точек, которые в итоге будут дублироваться.

kd-tree со связками

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

Этот алгоритм, как и backtrack позволяет избежать многократных прохождений по одним и тем же узлам дерева. Однако, шесть ссылок требуют дополнительно 24 байта памяти, что в сумме с имеющимися 8 дает 32 байта.

Р исунок 3 : kd дерево со связками .

Преимущества kd деревьев

1. Очень простой и эффективный алгоритм траверса. Даже для GPU.
2. Занимают мало памяти (8 байт на узел).

Недостатки kd деревьев

Трудоемкое построение, а именно, поиск разбиения с минимальным SAH.

Имеет большую глубину, чем BVH. Больше шагов при построении.

Заключение

Резюмируя, можно сказать, что kd дерево идеально для трасссировки лучей. Это верно как для CPU так и для GPU.

Литература

Wald I. Realtime Ray Tracing and Interactive Global Illumination. PhD thesis, Saarland University, 2004.

1. Shevtsov M., Soupikov A., Kapustin A.

   Highly Parallel Fast KD-tree Construction for Interactive Ray Tracing of Dynamic Scenes. In Proceedings of the EUROGRAPHICS conference, 2007.

Foley T., Sugerman J. KD-Tree Acceleration Structures for a GPU Raytracer. In Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, p. 15-22, 2005.

Horn D., Sugerman J., Houston M., Hanrahan P. Interactive k-D Tree GPU Raytracing. Proceedings of the symposium on Interactive 3D graphics and games on Fast rendering, p. 167-174, 2007.

Popov S.,Günther J.,Seidel H.-P.,Slusallek P. Stackless KD-Tree Traversal for High Performance GPU Ray Tracing. In Proceedings of the EUROGRAPHICS conference, 2007.

Математическое описание

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

Существуют однородные и неоднородные k-d деревья. У однородных k-d деревьев каждый узел хранит запись. При неоднородном варианте внутренние узлы содержат только ключи, листья содержат ссылки на записи.

В неоднородном k-d дереве при параллельно оси -мерной гиперплоскости в точке . Для корня нужно разделить точки через гиперплоскость на два по возможности одинаково больших множества точек и записать в корень, слева от этого сохраняются все точки у которых , справа те у которых . Для левого поддерева нужно разделить точки опять на новую «разделенную плоскость» , а сохраняется во внутреннем узле. Слева от этого сохраняются все точки у которых . Это продолжается рекурсивно над всеми пространствами. Потом всё начинается снова с первого пространства, до того пока каждую точку можно будет ясно идентифицировать через гиперплоскость.

K-d дерево можно построить за . Поиск диапазона может быть выполнен за , при этом обозначает размер ответа. Требование к памяти для самого дерева ограничено .

Операции с k -d деревьями

Структура

Структура дерева, описанная на языке C++ :

Const N= 10 ; // количество пространств ключей Struct Item{ // структура элемента int key[ N] ; // массив ключей определяющих элемент char * info; // информация элемента } ; Struct Node{ // структура узла дерева Item i; // элемент Node * left; // левое поддерево Node * right; // правое поддерево }

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

Анализ поиска элемента

Очевидно, что минимальное количество просмотренных элементов равно , а максимальное количество просмотренных элементов - , где - это высота дерева. Остаётся посчитать среднее количество просмотренных элементов .

Заданный элемент.

Рассмотрим случай . Найденными элементами могут быть:

и так для каждого пространства ключей. При этом средняя длина поиска в одном пространстве составляет:

Средняя величина считается по формуле:

Остаётся найти вероятность . Она равна , где - число случаев, когда , и - общее число случаев. Не сложно догадаться, что

Подставляем это в формулу для средней величины:

то есть, , где - высота дерева.

Если перейти от высоты дерева к количеству элементов, то:

Где - количество элементов в узле.

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

Добавление элементов

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

Алгоритм продвижения по дереву:

For (int i = 0 ; tree; i++ ) // i - это номер пространства if (tree- > x[ i] < tree- > t) // t - медиана tree = tree- > left; // переходим в левое поддерево else tree = tree- > right; // переходим в правое поддерево

Добавление выполняется за , где - высота дерева.

Удаление элементов

При удалении элементов дерева может возникнуть несколько ситуаций.

• Удаление листа дерева - довольно простое удаление, когда удаляется один узел, и указатель узла-предка просто обнуляется.

• Удаление узла дерева (не листа) - очень сложная процедура, при которой приходится перестраивать всё поддерево для данного узла.

Иногда процесс удаления узла решается модификациями k-d дерева. К примеру, если у нас в узле содержится массив элементов, то при удалении всего массива узел дерева остаётся, но новые элементы туда больше не записываются.

Поиск диапазона элементов

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

Алгоритм

Z – узел дерева [ (x_0_min, x_1_min, x_2_min,..., x_n_min) ,(x_0_max, x_1_max, x_2_max,..., x_n_max) ] - заданный диапазон Функция Array(Node * & Z) { If ([ x_0_min, x_1_min, x_2_min,..., x_n_min] < Z) { Z= Z- > left; // левое поддерево } else If ([ x_0_max, x_1_max, x_2_max,..., x_n_max] > Z) { Z= Z- > right; // правое поддерево } Else{ // просмотреть оба поддерева Array(Z- > right) ; // запустить функцию для правого поддерева Z= Z- > left; // просмотреть левое поддерево } }

Анализ

Очевидно, что минимальное количество просмотренных элементов это , где - высота дерева. Так же очевидно, что максимальное количество просмотренных элементов это , то есть просмотр всех элементов дерева. Остаётся посчитать среднее количество просмотренных элементов .

Заданный диапозон.

Оригинальная статья про k-d деревья даёт такую характеристику: для фиксированного диапазона.

Если перейти высоты дерева к количеству элементов, то это будет:

Поиск ближайшего соседа

Поиск ближайшего элемента состоит из 2-х задачек. Определение возможного ближайшего элемента и поиск ближайших элементов в заданном диапазоне, то есть

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

При этом при нахождении более близкого элемента корректируется радиус поиска.

Алгоритм

Z – корень дерева| List – список ближайших элементов| [ x_0,x_1,x_2...,x_n] - элемент для которого ищется ближайшие Len – минимальная длина Функция Maybe_Near(Node * & Z) { // поиск ближайшего возможного элемента While(Z) { // проверка элементов в узле for (i= 0 ; i< N; i++ ) { len_cur= sqrt ((x_0- x[ i] _0) ^ 2 + (x_1- x[ i] _1) ^ 2 + ... + (x_n- x[ i] _n) ^ 2 ) ; // длина текущего элемента if (Len> // установление новой длины Delete(List) ; // очистка списка Add(List) ; // добавить новый элемент в список If((x_0= x[ i] _0) && (x_1= x[ i] _1) && ... && (x_n= x[ i] _n) ) Return 1 ; } If([ x_0,x_1,x_2...,x_n] < Z) Z= Z- > left; // левое поддерево If([ x_0,x_1,x_2...,x_n] > Z) Z= Z- > right; // правое поддерево } } Функция Near(Node * & Z) { // поиск наиближайшего элемента в заданном диапазоне While(Z) { // проверка элементов в узле for (i= 0 ; i< N; i++ ) { len_cur= sqrt ((x_0- x[ i] _0) ^ 2 + (x_1- x[ i] _1) ^ 2 + ... + (x_n- x[ i] _n) ^ 2 ) ; // длина текущего элемента if (Len> длины текущего элемента) { Len= len_cur; // установление новой длины Delete(List) ; // очистка списка Add(List) ; // добавить новый элемент в список } Else if (длины равны) Add(List) ; // добавить новый элемент в список } If([ x_0,x_1,x_2...,x_n] + len> Z) { // если диапазон больше медианы Near(Z- > right) ; // просмотреть оба дерева Z= Z- > left; } If([ x_0,x_1,x_2...,x_n] < Z) Z= Z- > left; // левое поддерево If([ x_0,x_1,x_2...,x_n] > Z) Z= Z- > right; // правое поддерево } }

Анализ

Очевидно, что минимальное количество просмотренных элементов это , где h - это высота дерева. Так же очевидно, что максимальное количество просмотренных элементов это , то есть просмотр всех узлов. Остаётся посчитать среднее количество просмотренных элементов.

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

Для второй части, как мы уже вычислили, поиск элементов в заданном диапазоне равен . Что бы узнать среднее достаточно просто сложить эти 2 величины:

См. также

Примечания

Ссылки

• libkdtree++ , an open-source STL-like implementation of k -d trees in C++.
• FLANN and its fork nanoflann , efficient C++ implementations of k -d tree algorithms.
• kdtree A simple C library for working with KD-Trees
• libANN Approximate Nearest Neighbour Library includes a k -d tree implementation
• Caltech Large Scale Image Search Toolbox : a Matlab toolbox implementing randomized k -d tree for fast approximate nearest neighbour search, in addition to LSH, Hierarchical K-Means, and Inverted File search algorithms.
• Heuristic Ray Shooting Algorithms , pp. 11 and after
• Into contains open source implementations of exact and approximate (k)NN search methods using k -d trees in C++.

). k -d деревья - особый вид двоичных деревьев поиска .

Математическое описание

K-мерное дерево - это несбалансированное дерево поиска для хранения точек из $\backslash mathbb\{R\}^k$. Оно предлагает похожую на R-дерево возможность поиска в заданном диапазоне ключей. В ущерб простоте запросов, требования к памяти $O(kn)$ вместо $O((log(n))^\{k-1\})$.

Существуют однородные и неоднородные k-d деревья. У однородных k-d деревьев каждый узел хранит запись . При неоднородном варианте внутренние узлы содержат только ключи, листья содержат ссылки на записи.

В неоднородном k-d дереве $H\_i(t)\; =\; (x\_1,\; x\_2,\; \backslash ldots\; ,\; x\_\{i-1\},\; t\; ,\; x\_\{i+1\},\; \backslash ldots\; ,\; x\_k)$ при $1\; \backslash leq\; i\; \backslash leq\; k$ параллельно оси $(k-1)$-мерной гиперплоскости в точке $t$. Для корня нужно разделить точки через гиперплоскость $H\_1(t)$ на два по возможности одинаково больших множества точек и записать $t$ в корень, слева от этого сохраняются все точки у которых

K-d дерево можно построить за $O(n(k+log(n)))$. Поиск диапазона может быть выполнен за $O(n^\{1-\backslash frac\{1\}\{k\}\}+a)$, при этом $a$ обозначает размер ответа. Требование к памяти для самого дерева ограничено $O(kn)$.

Операции с k -d деревьями

Структура

Структура дерева, описанная на языке C++ :

const int N=10; // количество пространств ключей struct Item { // структура элемента int key[N]; // массив ключей определяющих элемент char *info; // информация элемента }; struct Node { // структура узла дерева Item i; // элемент Node *left; // левое поддерево Node *right; // правое поддерево }

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

Анализ поиска элемента

Очевидно, что минимальное количество просмотренных элементов равно $1$, а максимальное количество просмотренных элементов - $O(h)$, где $h$ - это высота дерева. Остаётся посчитать среднее количество просмотренных элементов $A\_n$.

$$ - заданный элемент.

Рассмотрим случай $h=3$. Найденными элементами могут быть:

find(t_1): [(x_0=t_1)]; A=1.

find(t_2): [(x_0

find(t_3): [(x_0>t_1)\land(x_0=t_3)]; A=2.

find(t_4): [(x_0

find(t_5): [(x_0t_2)\land(x_0=t_5)]; A=3.

find(t_6): [(x_0

find(t_7): [(x_0t_3)\land(x_0=t_7)]; A=3.

и так для каждого пространства ключей. При этом средняя длина поиска в одном пространстве составляет:

$A=\backslash frac\{1+2+2+3+3+3+3\}\{7\}=\backslash frac\{17\}\{7\}\backslash approx\; 2,4$.

Средняя величина считается по формуле: $A\_n=\backslash sum\_\{k=1\}^n\; kp\_\{n,k\}$

Остаётся найти вероятность $p\_\{n,k\}$. Она равна $p\_\{n,k\}=\backslash frac\{p\_\{A,k\}\}\{p\_\{n\}\}$, где $p\_\{A,k\}$ - число случаев, когда $A=k$ и $p\_\{n\}$ - общее число случаев. Не сложно догадаться, что $p\_\{n,k\}=\backslash frac\{2^\{k-1\}\}\{2^n-1\}$.

Подставляем это в формулу для средней величины:

A_n=\sum_{k=1}^n kp_{n,k}=\sum_{k=1}^n {k\frac{2^{k-1}}{2^n-1}}=\frac{1}{2^n-1}\sum_{k=1}^n {k2^{k-1}}=

\frac{1}{2^n-1}\sum_{k+1=1}^n {({k+1})2^k}=\frac{1}{2^n-1}(\sum_{k+1=1}^n {k2^k} + \sum_{k+1=1}^n {2^k})

\frac{1}{2^n-1}(\sum_{k=1}^n {k2^k} + \sum_{k=1}^n {2^k} - 2^n - n2^n)

=\frac{1}{2^n-1}(n2^{n+2} - (n+1)2^{n+1} +2 - 2^n + 2^3 -1 - n2^n) = \frac{2^n (n-1) +1}{2^n-1} ,

то есть $A\_h=\backslash frac\{2^h\; (h-1)\; +1\}\{2^h-1\}$, где $h$ - высота дерева.

Если перейти от высоты дерева к количеству элементов, то:

$A\_n=~O(\backslash frac\{2^h\; (h-1)\; +1\}\{2^h-1\})\; =\; ~O(h\backslash frac\{2^h\}\{2^h-1\}\; -\; 1)\; =\; ~O(log(\backslash frac\{n\}\{N\}\; +1)\backslash frac\{2^\{log(\backslash frac\{n\}\{N\}\; +1)\}\}\{2^\{log(\backslash frac\{n\}\{N\}\; +1)\}-1\}\; -\; 1)=~O(log(\backslash frac\{n\}\{N\}\; +1)\backslash frac\{n+N\}\{n\}-1)\; =$

$=~O(log(\backslash frac\{n\}\{N\}\; +1)^\{\backslash frac\{n+N\}\{n\}\}-1)$, где $N$ - количество элементов в узле.

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

Добавление элементов

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

Алгоритм продвижения по дереву:

for (int i = 0; tree; i++) // i - это номер пространства if (tree->x[i] < tree->t) // t - медиана tree = tree->left; // переходим в левое поддерево else tree = tree->right; // переходим в правое поддерево

Добавление выполняется за $O(h)$, где $h$ - высота дерева.

Удаление элементов

При удалении элементов дерева может возникнуть несколько ситуаций:

• Удаление листа дерева - довольно простое удаление, когда удаляется один узел и указатель узла-предка просто обнуляется.

• Удаление узла дерева (не листа) - очень сложная процедура, при которой приходится перестраивать всё поддерево для данного узла.

Иногда процесс удаления узла решается модификациями k-d дерева. К примеру, если у нас в узле содержится массив элементов, то при удалении всего массива узел дерева остаётся, но новые элементы туда больше не записываются.

Поиск диапазона элементов

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

Алгоритм

Z – узел дерева [(x_0_min, x_1_min, x_2_min,..., x_n_min),(x_0_max, x_1_max, x_2_max,..., x_n_max)] - заданный диапазон Функция Array(Node *&Z){ If (left; // левое поддерево } else If (>Z){ Z=Z->right; // правое поддерево } Else{ // просмотреть оба поддерева Array(Z->right); // запустить функцию для правого поддерева Z=Z->left; // просмотреть левое поддерево } }

Анализ

$O(h)$, где $h$ - высота дерева. Так же очевидно, что максимальное количество просмотренных элементов это $O(2^h-1)$, то есть просмотр всех элементов дерева. Остаётся посчитать среднее количество просмотренных элементов $A\_n$.

$[(x\_\{0\_\{min\}\},\; x\_\{1\_\{min\}\},\; x\_\{2\_\{min\}\},...,\; x\_\{n\_\{min\}\}),(x\_\{0\_\{max\}\},\; x\_\{1\_\{max\}\},\; x\_\{2\_\{max\}\},...,\; x\_\{n\_\{max\}\})]$ - заданный диапазон.

Оригинальная статья про k-d деревья даёт такую характеристику: $A\_n=~O(h\; \backslash cdot\; log(h))$ для фиксированного диапазона.

Если перейти от высоты дерева к количеству элементов, то это будет: $A\_n=~O(log(log(n-1))^\{log(n-1)\})$

Поиск ближайшего соседа

Поиск ближайшего элемента разделяется на две подзадачи: определение возможного ближайшего элемента и поиск ближайших элементов в заданном диапазоне.

Дано дерево $tree$. Мы спускаемся по дереву к его листьям по условию и определяем вероятный ближайший элемент по условию $l\_\{min\}=\backslash sqrt\{((\{x\_0-x[i]\_0\})^2\; +\; (\{x\_1-x[i]\_1\})^2\; +\; ...\; +\; (\{x\_n-x[i]\_n\})^2)\}$. После этого от корня дерева запускается алгоритм поиска ближайшего элемента в заданном диапазоне, который определяется радиусом $R=l\_\{min\}=\backslash sqrt\{((\{x\_0-x[i]\_0\})^2\; +\; (\{x\_1-x[i]\_1\})^2\; +\; ...\; +\; (\{x\_n-x[i]\_n\})^2)\}$.

Радиус поиска корректируется при нахождении более близкого элемента.

Алгоритм

Z – корень дерева| List – список ближайших элементов| - элемент для которого ищется ближайшие Len – минимальная длина Функция Maybe_Near(Node *&Z){ // поиск ближайшего возможного элемента While(Z){ // проверка элементов в узле for(i=0;iдлины текущего элемента){ Len=len_cur; // установление новой длины Delete(List); // очистка списка Add(List); // добавить новый элемент в список } Else if(длины равны) Add(List); // добавить новый элемент в список If((x_0=x[i]_0) && (x_1=x[i]_1) && ... && (x_n=x[i]_n)) Return 1; } If(left; // левое поддерево If(>Z) Z=Z->right; // правое поддерево } } Функция Near(Node *&Z){ // поиск ближайшего элемента в заданном диапазоне While(Z){ // проверка элементов в узле for(i=0;iдлины текущего элемента){ Len=len_cur; // установление новой длины Delete(List); // очистка списка Add(List); // добавить новый элемент в список } Else if(длины равны) Add(List); // добавить новый элемент в список } If(+len>Z){ // если диапазон больше медианы Near(Z->right); // просмотреть оба дерева Z=Z->left; } If(left; // левое поддерево If(>Z) Z=Z->right; // правое поддерево } }

Анализ

Очевидно, что минимальное количество просмотренных элементов это $O(h)$, где h - это высота дерева. Так же очевидно, что максимальное количество просмотренных элементов это $O(2^h-1)$, то есть просмотр всех узлов. Остаётся посчитать среднее количество просмотренных элементов.

$[(x\_0,\; x\_1,\; x\_2,...,\; x\_n)]$ - заданный элемент, относительно которого нужно найти ближайший. Эта задача разделяется на две подзадачи: нахождение ближайшего элемента в узле и нахождение ближайшего элемента в заданном диапазоне. Для решения первой подзадачи потребуется один спуск по дереву, то есть $O(h)$.

Для второй подзадачи, как мы уже вычислили, поиск элементов в заданном диапазоне выполняется за $O(h\; \backslash cdot\; log(h))$. Чтобы узнать среднее, достаточно просто сложить эти две величины:

$=~O(h)+\; ~O(h\; \backslash cdot\; log(h))\; =\; ~O(h)\; \backslash cdot\; (\{~O(log(h))+1\}))$.

См. также

Напишите отзыв о статье "K-мерное дерево"

Примечания

Ссылки

• , an open-source STL-like implementation of k -d trees in C++.
• and its fork , efficient C++ implementations of k -d tree algorithms.
• A simple C library for working with KD-Trees
• Approximate Nearest Neighbour Library includes a k -d tree implementation
• : a Matlab toolbox implementing randomized k -d tree for fast approximate nearest neighbour search, in addition to LSH , Hierarchical K-Means, and Inverted File search algorithms.
• , pp. 11 and after
• contains open source implementations of exact and approximate (k)NN search methods using k -d trees in C++.

Отрывок, характеризующий K-мерное дерево

Анатоль последнее время переселился к Долохову. План похищения Ростовой уже несколько дней был обдуман и приготовлен Долоховым, и в тот день, когда Соня, подслушав у двери Наташу, решилась оберегать ее, план этот должен был быть приведен в исполнение. Наташа в десять часов вечера обещала выйти к Курагину на заднее крыльцо. Курагин должен был посадить ее в приготовленную тройку и везти за 60 верст от Москвы в село Каменку, где был приготовлен расстриженный поп, который должен был обвенчать их. В Каменке и была готова подстава, которая должна была вывезти их на Варшавскую дорогу и там на почтовых они должны были скакать за границу.
У Анатоля были и паспорт, и подорожная, и десять тысяч денег, взятые у сестры, и десять тысяч, занятые через посредство Долохова.
Два свидетеля – Хвостиков, бывший приказный, которого употреблял для игры Долохов и Макарин, отставной гусар, добродушный и слабый человек, питавший беспредельную любовь к Курагину – сидели в первой комнате за чаем.
В большом кабинете Долохова, убранном от стен до потолка персидскими коврами, медвежьими шкурами и оружием, сидел Долохов в дорожном бешмете и сапогах перед раскрытым бюро, на котором лежали счеты и пачки денег. Анатоль в расстегнутом мундире ходил из той комнаты, где сидели свидетели, через кабинет в заднюю комнату, где его лакей француз с другими укладывал последние вещи. Долохов считал деньги и записывал.
– Ну, – сказал он, – Хвостикову надо дать две тысячи.
– Ну и дай, – сказал Анатоль.
– Макарка (они так звали Макарина), этот бескорыстно за тебя в огонь и в воду. Ну вот и кончены счеты, – сказал Долохов, показывая ему записку. – Так?
– Да, разумеется, так, – сказал Анатоль, видимо не слушавший Долохова и с улыбкой, не сходившей у него с лица, смотревший вперед себя.
Долохов захлопнул бюро и обратился к Анатолю с насмешливой улыбкой.
– А знаешь что – брось всё это: еще время есть! – сказал он.
– Дурак! – сказал Анатоль. – Перестань говорить глупости. Ежели бы ты знал… Это чорт знает, что такое!
– Право брось, – сказал Долохов. – Я тебе дело говорю. Разве это шутка, что ты затеял?
– Ну, опять, опять дразнить? Пошел к чорту! А?… – сморщившись сказал Анатоль. – Право не до твоих дурацких шуток. – И он ушел из комнаты.
Долохов презрительно и снисходительно улыбался, когда Анатоль вышел.
– Ты постой, – сказал он вслед Анатолю, – я не шучу, я дело говорю, поди, поди сюда.
Анатоль опять вошел в комнату и, стараясь сосредоточить внимание, смотрел на Долохова, очевидно невольно покоряясь ему.
– Ты меня слушай, я тебе последний раз говорю. Что мне с тобой шутить? Разве я тебе перечил? Кто тебе всё устроил, кто попа нашел, кто паспорт взял, кто денег достал? Всё я.
– Ну и спасибо тебе. Ты думаешь я тебе не благодарен? – Анатоль вздохнул и обнял Долохова.
– Я тебе помогал, но всё же я тебе должен правду сказать: дело опасное и, если разобрать, глупое. Ну, ты ее увезешь, хорошо. Разве это так оставят? Узнается дело, что ты женат. Ведь тебя под уголовный суд подведут…
– Ах! глупости, глупости! – опять сморщившись заговорил Анатоль. – Ведь я тебе толковал. А? – И Анатоль с тем особенным пристрастием (которое бывает у людей тупых) к умозаключению, до которого они дойдут своим умом, повторил то рассуждение, которое он раз сто повторял Долохову. – Ведь я тебе толковал, я решил: ежели этот брак будет недействителен, – cказал он, загибая палец, – значит я не отвечаю; ну а ежели действителен, всё равно: за границей никто этого не будет знать, ну ведь так? И не говори, не говори, не говори!
– Право, брось! Ты только себя свяжешь…
– Убирайся к чорту, – сказал Анатоль и, взявшись за волосы, вышел в другую комнату и тотчас же вернулся и с ногами сел на кресло близко перед Долоховым. – Это чорт знает что такое! А? Ты посмотри, как бьется! – Он взял руку Долохова и приложил к своему сердцу. – Ah! quel pied, mon cher, quel regard! Une deesse!! [О! Какая ножка, мой друг, какой взгляд! Богиня!!] A?
Долохов, холодно улыбаясь и блестя своими красивыми, наглыми глазами, смотрел на него, видимо желая еще повеселиться над ним.
– Ну деньги выйдут, тогда что?
– Тогда что? А? – повторил Анатоль с искренним недоумением перед мыслью о будущем. – Тогда что? Там я не знаю что… Ну что глупости говорить! – Он посмотрел на часы. – Пора!
Анатоль пошел в заднюю комнату.
– Ну скоро ли вы? Копаетесь тут! – крикнул он на слуг.
Долохов убрал деньги и крикнув человека, чтобы велеть подать поесть и выпить на дорогу, вошел в ту комнату, где сидели Хвостиков и Макарин.
Анатоль в кабинете лежал, облокотившись на руку, на диване, задумчиво улыбался и что то нежно про себя шептал своим красивым ртом.
– Иди, съешь что нибудь. Ну выпей! – кричал ему из другой комнаты Долохов.
– Не хочу! – ответил Анатоль, всё продолжая улыбаться.
– Иди, Балага приехал.
Анатоль встал и вошел в столовую. Балага был известный троечный ямщик, уже лет шесть знавший Долохова и Анатоля, и служивший им своими тройками. Не раз он, когда полк Анатоля стоял в Твери, с вечера увозил его из Твери, к рассвету доставлял в Москву и увозил на другой день ночью. Не раз он увозил Долохова от погони, не раз он по городу катал их с цыганами и дамочками, как называл Балага. Не раз он с их работой давил по Москве народ и извозчиков, и всегда его выручали его господа, как он называл их. Не одну лошадь он загнал под ними. Не раз он был бит ими, не раз напаивали они его шампанским и мадерой, которую он любил, и не одну штуку он знал за каждым из них, которая обыкновенному человеку давно бы заслужила Сибирь. В кутежах своих они часто зазывали Балагу, заставляли его пить и плясать у цыган, и не одна тысяча их денег перешла через его руки. Служа им, он двадцать раз в году рисковал и своей жизнью и своей шкурой, и на их работе переморил больше лошадей, чем они ему переплатили денег. Но он любил их, любил эту безумную езду, по восемнадцати верст в час, любил перекувырнуть извозчика и раздавить пешехода по Москве, и во весь скок пролететь по московским улицам. Он любил слышать за собой этот дикий крик пьяных голосов: «пошел! пошел!» тогда как уж и так нельзя было ехать шибче; любил вытянуть больно по шее мужика, который и так ни жив, ни мертв сторонился от него. «Настоящие господа!» думал он.
Анатоль и Долохов тоже любили Балагу за его мастерство езды и за то, что он любил то же, что и они. С другими Балага рядился, брал по двадцати пяти рублей за двухчасовое катанье и с другими только изредка ездил сам, а больше посылал своих молодцов. Но с своими господами, как он называл их, он всегда ехал сам и никогда ничего не требовал за свою работу. Только узнав через камердинеров время, когда были деньги, он раз в несколько месяцев приходил поутру, трезвый и, низко кланяясь, просил выручить его. Его всегда сажали господа.

Главная » Язва » KD-деревья и R-деревья. Анатомия KD-Деревьев Добавление узлов в дерево