Удаление узла KdTree - PullRequest
Новая
       14

Удаление узла KdTree

2 голосов
/ 01 ноября 2011

Я пытался реализовать KdTree с нуля. Успешно внедрив add-, найдите ближайший сосед и найдите узлы в методах диапазона, я застрял на удалении узлов.

Метод, описанный в Википедии, является расплывчатым и довольно бесполезным. Вместо этого я использую эти слайды в качестве отправной точки. Однако описание метода удаления на слайде 13 меня смущает: 

KDNode remove ( KDNode t , Point p , int cd ) {
if ( t == null ) return null;
else if (p.cd < t.data) t.left = remove (t.left , p , cd +1);
else if (p.cd > t.data) t.right = remove (t.right , p , cd +1);
else {
  if (t.right == null && t.left == null ) return null ;
  if (t.right != null )
    t.data = findmin(t.right , cd , cd +1);
  else {
    t.data = findmin (t.left , cd , cd +1);
    t.left = null;
}

t.right = remove (t.right , t . data , cd +1);
return t ;
}}

Обе замены t.left на null и t.right with remove(t.right, ...) не имеют смысла.

Это правильно, и пока мы находимся в этом, есть ли что-то еще не так с этим методом? Следует отметить, что напротив метода, описанного на этих слайдах, я расположил равные узлы слева, а не справа. Метод все еще действителен?

1 Ответ

2 голосов
/ 02 ноября 2011

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

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

...