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

Question

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

Вопросы

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

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

3. Что такое «минимум()», минимизация?Я думал, что это будет расстояние до оси, но мне кажется, что автор минимизирует точки, что для меня не имеет смысла.

Answer 1

(1) я думать я это опечатка;В моей реализации нет ничего подобного, и, похоже, все работает нормально (знаменитые последние слова...).

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

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

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

...где левый и верно — это минимальные значения, которые рекурсивно ищут в левом и правом дочерних деревьях узла, в котором мы находимся.Я могу опубликовать полную функцию, если так будет понятнее :-)

Answer 2

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

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

(2) если nodeA не является листовым узлом

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

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