Удаление элемента из дерева kd двух измерений - PullRequest
Новая
       40

Удаление элемента из дерева kd двух измерений

2 голосов
/ 09 марта 2010

Я хотел бы расширить класс дерева kd (2D), чтобы иметь возможность удалять узлы (точки). Это удаление должно проводиться без необходимости перестраивать большие участки дерева. Алгоритм, описанный в этих слайдах , на слайде 13, похоже, является тем, что я преследую. Однако я испытываю затруднения из-за описания функции findmin (), показанной на слайде 7, которая используется в алгоритме удаления узла.

Вопросы

  1. Что означает «i» на второй или последней строке? (Может быть, это ошибка автора, так как на нее нет ссылок в другом месте?)

  2. Что именно означает "какая ось"? Это глубина расщепляемой гиперплоскости, к которой мы хотим приблизиться?

  3. Что такое "минимальный ()", минимизирующий? Я думал, что это будет расстояние до оси, но мне кажется, что автор минимизирует точки, что для меня не имеет смысла.

Ответы [ 2 ]

4 голосов
/ 17 марта 2010

(1) Я думаю i - опечатка; У меня нет ничего подобного в моей реализации, и она, кажется, работает нормально (знаменитые последние слова ..).

(2) whichAxis - это плоскость, в которой вы ищете минимум. Так что в двумерных данных это будет либо x, либо y. Например. для точек (20,40) и (40,20) один является минимумом по x, а другой по y. Когда вы начинаете искать заменяющий узел, вы должны знать, в какой плоскости разбиения вы должны искать.

(3) Слайд написан немного странно. Вы хотите найти минимальное значение в соответствующей плоскости. Может быть, это прояснит немного (c #). Моя реализация для набора данных, использующего восточных и северных в качестве х и у. minAxis - это просто бул, потому что у меня всего два самолета. 

bool winner = minAxis ? (left.Easting < right.Easting) : (left.Northing < right.Northing);
return winner ? left : right;

... где left и right - минимальные значения, которые рекурсивно ищутся из левого и правого дочерних деревьев узла, в котором мы находимся. если это прояснит: -)

2 голосов
/ 22 мая 2013

Если вы хотите удалить узел A в данном дереве kd

(1) если nodeA является листовым узлом, просто установите его в null

(2), если узел A не является конечным узлом 

Assume nodeA split by x , you have two choice

1. find the largest nodeB (whose X is the largest) in left   
2. find the minimum nodeB (whoes X is the minimum) in right  (This pdf prefer it)

Примечание:

если вы поместите nodeB равным nodeA под nodeA.right, вы должны выбрать 2

если вы поместите nodeB равным nodeA под nodeA.left, вы должны выбрать 1

После этого замените узел A на узел B и удалите узел B.

...