KdTree 노드 제거

Question

저는 처음부터 KdTree를 구현하려고했습니다. 성공적으로 add-를 구현하고, 가장 가까운 neighbour-를 찾고, range 메소드에서 노드를 찾는다. 이제 노드 제거에 박혀있다.

위키 백과에 설명 된 방법은 모호하고 오히려 쓸모가 없습니다. 대신 시작 지점으로 these slides을 사용하고 있습니다. 그러나, 슬라이드 (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 ; 
}} 

null 및 t.right with remove(t.right, ...)로 모두 교체 t.left가 이해되지 않는다.

이 정보가 정확하며이 방법에 문제가 있습니까? 이 슬라이드에서 설명한 방법의 반대쪽에서 오른쪽 대신에 왼쪽에 같은 노드를 놓습니다. 이 방법은 여전히 ​​유효합니까?

Answer 1

리프가 아닌 노드를 제거 할 때는 을으로 바꿔 서브 트리 중 하나의 리프 노드로 바꿔야합니다. 즉, 리프 노드 부모가 NULL 포인터를 가져와야하고 리프 노드 자체가 포인터가 대체 될 노드의 값으로 설정되어야합니다.

하위 노드가 올바른 분할 축을 사용하지 않으므로 노드를 바꿔야하므로 하위 트리가 레벨을 변경하면 유효하지 않습니다. 최소 오른쪽 값 또는 최대 왼쪽 값은 여전히 ​​포인트를 동일한 축으로 분할하므로 대체에 사용됩니다.