KD-Tree에서 2 차원에서 요소를 삭제합니다

Question

노드 (포인트)를 제거하기 위해 KD-Tree (2D) 클래스를 연장하고 싶습니다. 이 제거는 나무의 큰 부분을 재건 할 필요없이 수행되어야합니다. 이것들에 설명 된 알고리즘 슬라이드, 슬라이드 13은 내가 뒤에있는 것 같습니다. 그러나 노드 제거 알고리즘에 사용되는 슬라이드 7에서 발견 된 "findmin ()"에 대한 설명에 어려움을 겪습니다.

질문

1. "I"는 두 번째에서 마지막 줄에서 무엇을 의미합니까? (아마도 이것은 다른 곳에서는 참조되지 않기 때문에 저자의 실수일까요?)

2. "whitaxis"는 정확히 무엇입니까? 우리가 가장 가까워지고 싶은 분할 과면의 깊이입니까?

3. "최소 ()", 최소화는 무엇입니까? 나는 이것이 축까지의 거리 일 것이지만, 저자가 포인트를 최소화하는 것처럼 보인다.

Answer 1

(1) i 생각한다 나 오타입니다. 나는 그것의 구현에 그런 것이없고, 그것은 잘 작동하는 것처럼 보인다 (유명한 마지막 단어 ..).

(2) whitaxis 최소값을 찾고있는 평면입니다. 따라서 2 차원 데이터에서는 x 또는 y입니다. 예를 들어 포인트 (20,40) 및 (40,20)의 경우, 하나는 x에서 최소이고 다른 하나는 y에서 최소입니다. 교체 노드를 검색하기 시작하면 검색 해야하는 분할 평면을 알아야합니다.

(3) 슬라이드는 조금 이상하게 쓰여진다. 해당 평면에서 최소값을 찾고 싶습니다. 어쩌면 이것은 약간 (C#)를 명확하게 할 것입니다. 내 구현은 데이터 세트를 사용하는 것입니다 이스트 팅과 북쪽 x와 y로. Minaxis는 단지 두 개의 비행기 만 가지고 있기 때문에 BOOL입니다.

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

...어디 왼쪽 그리고 오른쪽 우리가있는 노드의 왼쪽과 오른쪽 자식 나무에서 재귀 적으로 검색된 최소 값입니다. 전체 기능을 명확하게하면 다음을 게시 할 수 있습니다 :-)

Answer 2

주어진 KD-Tree에서 NODEA를 삭제하려면

(1) Nodea가 잎 노드 인 경우 널로 만드십시오.

(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에 넣으면 2를 선택해야합니다.

nodeb를 nodea.left 아래에두면 1을 선택해야합니다.

그런 다음 NODEA를 NODEB로 교체하고 NODEB를 삭제하십시오.