kd-tree를 구성 할 때 '중간 값'에 대한 정의가 혼동 스럽습니다

Question

점 집합을 검색하기 위해 kd 트리를 작성하려하지만 위키 백과 문서에서 '중앙값'을 사용하는 것에 대해 혼란스러워하고 있습니다. 나는 확실히 아니에요 단순히 때문에 "중간을 선택 ..."라인에 대해 혼란스러워지고있어

function kdtree (list of points pointList, int depth) 
{ 
    if pointList is empty 
     return nil; 
    else 
    { 
     // Select axis based on depth so that axis cycles through all valid values 
     var int axis := depth mod k; 

     // Sort point list and choose median as pivot element 
     select median by axis from pointList; 

     // Create node and construct subtrees 
     var tree_node node; 
     node.location := median; 
     node.leftChild := kdtree(points in pointList before median, depth+1); 
     node.rightChild := kdtree(points in pointList after median, depth+1); 
     return node; 
    } 
} 

사용의 편의성을 위해, 위키 피 디아 문서로 KD 트리 구조의 의사 코드를 말한다 여기에 중간 값을 적용하는 '올바른'방법은 무엇입니까?

내가 아는 한, 홀수 크기의 (정렬 된) 숫자 목록의 중간 값은 중간 요소입니다 (일명 5 가지 목록, 요소 번호 3 또는 인덱스 2 기준). 배열), 짝수 크기 배열의 중앙값은 2 개의 중간 요소를 2로 나눈 값의 합계입니다 (일명 6 개 목록의 경우 중앙값은 요소 3과 4의 합계입니다. 또는 2와 3 , 인덱스가 0 인 경우 - 2로 나눈 값).

그러나 명확한 점 집합으로 작업 할 때 분명히 정의가 작동하지 않습니다. 그렇다면 길이가 짝수 인 숫자 목록, 특히 길이가 2 인 목록에 대해 올바른 중간 값을 선택하는 방법은 무엇입니까?

감사합니다. 감사합니다.

-Stephen

Answer 1

중간 값의 의미를 이해하지만 나에게 다른 것과 혼동스러워합니다. 구별되는 점은 무엇을 의미합니까?

위키 백과에서 제공하는 코드는 재귀 함수입니다. 포인트 세트가 있으므로 루트 노드를 만들고 세트의 중앙값을 선택합니다. 그런 다음 함수를 재귀 적으로 호출합니다. 원래 목록의 분할 값 (중앙값)보다 작은 모든 점을 갖는 매개 변수에서 전달되는 왼쪽 하위 트리에 대해, 동일한 하위 트리와 큰 하위 트리에 대해 전달합니다. 그런 다음 각 하위 트리에 대해 동일한 일이 발생하는 노드가 만들어집니다. 그것은 다음과 같이 진행됩니다

First step (root node): 
Original set: 1 2 3 4 5 6 7 8 9 10 
Split value (median): 5.5 

Second step - left subtree: 
Set: 1 2 3 4 5 
Split value (median): 3 

Second step - right subtree: 
Set: 6 7 8 9 10 
Split value (median): 8 

Third step - left subtree of left subtree: 
Set: 1 2 
Split value (median): 1.5 

Third step - right subtree of left subtree: 
Set: 3 4 5 
Split value (median): 4 

그래서 중간 그 하위 트리로 이동 숫자 (포인트, 데이터)의 설정에 따라 트리의 각 노드에 대해 선택

등

. 희망이 도움이됩니다.

Answer 2

당신은 다른 것보다 한쪽에 많은 요소 축을 선택해야합니다. 포인트 수가 홀수이거나 포인트가 가능하지 않은 경우, 가능하면 축척을 재분할 할 축을 선택하십시오.