k-d Tree k차원 트리 kd tree

kd tree에서 어떤 원소와 가장 가까운 값을 찾는 방법이 어려웠다.

방법은 먼저, BST처럼 찾으려는 값을 해당 노드와 비교하여 작으면 왼쪽, 크면 오른쪽으로 tree를 타고 내려가고

타고 내려가면서 직선거리를 계산해 가장 작은 값을 구한다. 

그리고 타고 내려온 노드에서 root로 타고 올라가며 해당 노드의 경계선과의 거리가 최소거리보다 짧을 경우, 

해당노드의 반대편도 검사를 해줘야한다. 

교수님 C언어 구현 코드는 다음과 같다.

//(_x,_y)가 주어졌을 때 axis를 고려하여 _root
struct kdtree_node * whichWayToGo(struct kdtree_node *_root, int _x, int _y, int axis)
{
	if (axis == 0) // x축 비교
	{
		if (_root->data->x > _x)//내가 더 작은 경우
		{
			return _root->left;
		}
		else
		{
			return _root->right;
		}
	}
	else // y축 비교
	{
		if (_root->data->y > _y)
		{
			return _root->left;
		}
		else
		{
			return _root->right;
		}
	}
}

struct kdtree_node *RealNearestNeighbor(struct kdtree_node *_root,
	int _x,
	int _y,
	int _minDiff, //지금까지 최소거리 - > 초기 값은 INT MAX로
	struct kdtree_node *_minDiffNode, // 최소거리를 가진 자료
	int axis, //축
	int dim) //총 dimension은 2개
{
	if (_root == 0)//recursion의 탈출 조건 
	{
		return _minDiffNode;//걍 밑에 없으면 얘가 가장 작은 애 
	}
	//가장 퍼펙트한 매칭의 경우
	if (_root->data->x == _x && _root->data->y == _y)
	{
		return _root;
	}
	//지금 _root와 거리를 계산한다. 
	int dist = (_root->data->x - _x)*(_root->data->x - _x) + (_root->data->y - _y)*(_root->data->y - _y);
	if (dist < _minDiff)
	{
		_minDiff = dist;
		_minDiffNode = _root;
	}
	//이제 루트를 떠나 left right를 갈지 결정 
	struct kdtree_node *wayTo = whichWayToGo(_root, _x, _y, axis%dim);
	struct kdtree_node *NN =
		RealNearestNeighbor(wayTo, _x, _y, _minDiff, _minDiffNode, axis + 1, dim);//항상 2차원 데이터이므로 dim은 항상 2 
																				  //wayTo해서 왼쪽으로 갓는데 왼쪽이 null이면 탈출 해야함 -> 탈출 조건 필요 
																				  //경계선을 넘어가는지 아닌지 check해야하는 부분 
	int dist_to_NN = (NN->data->x - _x)*(NN->data->x - _x) + (NN->data->y - _y)*(NN->data->y - _y);//결정된 nearest neighbor까지의 거리를 구한다.
	if (axis%dim == 0)//x축에 대해서 검사
	{
		if (dist_to_NN > (_x - _root->data->x)*(_x - _root->data->x))
		{
			//경계선 넘어선 저쪽을 검사
			return RealNearestNeighbor(whichWayNotToGo(_root, _x, _y, axis%dim), _x, _y, dist_to_NN, NN, axis + 1, dim);//가는 곳 결정
		}
		else
		{
			return NN;
		}
	}
	else//y축에 대해서 검사
	{
		if (dist_to_NN > (_y - _root->data->y)*(_y - _root->data->y))
		{
			//경계선 넘어선 저쪽을 검사
			return RealNearestNeighbor(whichWayNotToGo(_root, _x, _y, axis%dim), _x, _y, dist_to_NN, NN, axis + 1, dim);//가는 곳 결정
		}
		else
		{
			return NN;
		}
	}

}

여기서 내가 이해한 내용은 결군엔

BST처럼 타고 내려가서 최소거리를 구한 후에 경계선을 비교해가며 재확인할 때,

1. BST처럼 조건 방향으로는 무조건 간다. 

2. 경계선과의 거리가 클 경우, 반대편은 확인하지 않아도 된다. (조건에 따라 선택사항이 됨)

이것이다. 

그러면 왜 굳이 최소 노드에서부터 bottom up 방향으로 타고 올라가야하는지 모르겠다.

최소노드를 구한 후에, root에서부터 다시 내려가면 되지 않을까?

root에서 내려갈 때는, BST처럼 조건 방향은 무조건 가고,

경계선과의 거리 비교에 따라 반대편은 갈 수도 안 갈 수도 있다.

코드 진행 과정 직접 적어본 것.

Q. 다음과 같은 x, y 2차원 데이터가 들어올 때, (5, 3)과 가장 근접한 노드는?

(5, 1) (6, 9) (1, 1) (2, 3) (1, 5) (4, 6) (7, 10) (3, 7) 

각 노드에 방문하고, 확인하는 순서를 tree에 표시하면 다음과 같다.

위의 그림과 코드는 bottom up방식인데, 그러면 root에서부터 타고 내려가는 top down방식으로 해도 상관없지 않을까? 라고 생각해서

top down방식으로 문제에 접근할 경우, 방문하는 노드와 확인하는 순서를 표시해봤다.

두 방식 모두 동일한 수의 노드를 방문하고, 확인하는 것을 알 수 있다. 

그렇다면 위의 예시에서만 적용되는 것인지 궁금해서 다른 예시로도 풀어보았다.

Q. 다음과 같은 (x, y) 2차원 데이터가 들어올 때, (4, 8)과 가장 근접한 노드는?

(5, 1) (6, 9) (1, 1) (2, 3) (1, 5) (4, 6) (7, 10) (3, 7) 

 

이 예시에도 동일하게 노드들을 방문하고 확인하는 것을 알 수 있다.

내 방식 ( BST처럼 tree를 타고 내려가서 최소노드를 구한 뒤, root부터 재차 확인하는 방식. top-down ) 으로 구현한 코드

struct kdtree_node *FindMinDiffNode(struct kdtree_node *_root, int _x, int _y) {
	
	struct kdtree_node *minDiffNode = 0;
	int minDiff = INT_MAX;
	struct kdtree_node *cur = _root;
	int axis = 0; // 처음에 x축
	
	while (1) {
		//탈출 조건
		if (cur == 0) {
			return minDiffNode;
		}
		else {
			int dist = (cur->data->x - _x)*(cur->data->x - _x) + (cur->data->y - _y)*(cur->data->y - _y);
			if (dist < minDiff) {
				minDiff = dist;
				minDiffNode = cur;
			}
			cur =whichWayToGo(cur, _x, _y,axis);
			axis = (axis + 1) % 2;
		}
	}
}

struct kdtree_node *NearestNode(struct kdtree_node *_root, int _x, int _y,
								struct kdtree_node *_minDiffNode,
								int _axis) {

	// 탈출조건
	if (_root == 0) {
		return _minDiffNode;
	}

	int minDiff = (_minDiffNode->data->x - _x)*(_minDiffNode->data->x - _x)
		+ (_minDiffNode->data->y - _y)*(_minDiffNode->data->y - _y);

	int dist_to_root = (_root->data->x - _x)*(_root->data->x - _x)
		+ (_root->data->y - _y)*(_root->data->y - _y);
	if (dist_to_root < minDiff) {
		_minDiffNode = _root;
	}

	// root부터 아래까지 타고 내려가기
	struct kdtree_node *cur = _root;

	if (_axis ==0) { // x비교
		int dist = (_root->data->x - _x)*(_root->data->x - _x);
		if (dist < minDiff) {
			// 반대편도 확인해주기
			_minDiffNode = NearestNode(whichWayNotToGo(_root,_x,_y, _axis),_x,_y,_minDiffNode, (_axis + 1) % 2);
		}
		// 반대편 제외시키고 원래 방향으로만 내려가면됨
		_minDiffNode = NearestNode(whichWayToGo(_root, _x, _y, _axis), _x, _y, _minDiffNode, (_axis + 1) % 2);
	
	}
	else {  //y비교
		int dist = (_root->data->y - _y)*(_root->data->y - _y);
		if (dist < minDiff) {
			_minDiffNode = NearestNode(whichWayNotToGo(_root, _x, _y, _axis),_x,_y,_minDiffNode, (_axis + 1) % 2);
		}
		else {
			_minDiffNode = NearestNode(whichWayToGo(_root, _x, _y, _axis), _x, _y, _minDiffNode, (_axis + 1) % 2);
		}
	}

	// 가장 짧은 node와 dist를 가지고 
	// root부터 아래로 내려가면서
	// 반대 저쪽편도 확인해줘야하는지 비교
}