2

KdTree をゼロから実装しようとしています。add-、最近傍の検索、range メソッドでのノードの検索を正常に実装したので、ノードの削除に行き詰まっています。

ウィキペディアに記載されている方法はあいまいで、役に立たないものです。代わりに、これらのスライドを出発点として使用しています。しかし、スライド 13 の remove メソッドの説明は私を混乱させます。

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ても意味がありません。nullt.right with remove(t.right, ...)

これは正しいですか。また、この方法には他に何か問題がありますか? これらのスライドで説明した方法とは逆に、右側ではなく左側に等しいノードを配置していることに注意してください。メソッドはまだ有効ですか？

4

1 に答える 1

2

リーフではないノードを削除する場合は、サブツリーの 1 つからのリーフ ノードに置き換える必要があります。つまり、リーフ ノードの親は NULL ポインターを取得する必要があり、リーフ ノード自体は置換されるノードの値に設定されたポインターを取得する必要があります。

どちらの子ノードも正しい分割軸を使用しないため、ノードを置き換える必要があります。そのため、レベルが変わるとサブツリーは無効になります。最小右値または最大左値は、ポイントを同じ軸で分割するため、置換に使用されます。

于 2011-11-01T22:22:46.150 に答える