K-d 트리

K-d 트리  2007/07/13 09:28 http://blog.naver.com/slump112/90019717360 10.1 k-d 트리 k-d 트리는 다차원의 점 데이타를 인덱스할 수 있는 가장 간단하면서도 기본적인 데이타 구조이다. k-d 트리는 일반적으로 디스크 저장을 고려하지 않고 주기억장치 상 에서 동작하는 인덱스 구조이다. 따라서 대용량의 데이타에 대해서는 적당하지 않고 소규모의 다차원 점 데이타를 인덱스할때 적당하다. 10.1.1 k-d트리의 데이타 삽입 k-d 트리는 기본적으로 이원 탐색 트리를 다차원 공간으로 확장한 것이다. 따라서 기본적인 구조나 알고리즘은 이원 탐색 트리와 유사하다. 삽입하려는 값이 트리의 기 존 노드의 값보다 작거나 같으면 왼쪽 자식노드에 저장하고, 보다 크면 오른쪽 자식 노드에 저장하게 된다. 이원 탐색 트리의 경우는 값이 하나이므로 그냥 비교를 할 수 있지만, 다차원 데이타의 경우 차원에 따라 여러 개의 값이 있으므로 그냥은 비교할 수 없다. 따라서 k-d 트리의 경우에는 각 차원을 번갈아가면서 비교하게 된다. 예를 들어 3차원의 (x,y,z) 값의 집합이 있을 경우, 트리의 첫번째 레벨에서는 x값에 대하여 비교를 하고,두번째 레벨에서는y값에 대해서 비교를 하고, 세번째 레벨에 대해서는 z 값에 대하여,네번째에서는 다시x값에 대하여 비교를 하는 식으로 트리를 구성하게된다. k-d 트리의 예로 2차원 공간에 그림 10.1과 같은 10개의 점이 있다고 가정하자. 이 점들을 차례로 k-d 트리에 삽입하여 보자.   우선 a점을 삽입하면 그림 10.2와 같이 k-d 트리의 루트로 a가 저장된다. 이 그림 에서 노드에 자식 포인터가 표시되지 않은 경우는 자식 포인터가 널 값을 지니고 있음 을 의미한다.   이제 다음 b 점을 삽입하자. 트리의 첫 레벨이므로 x축의 값을 서로 비교해야 한 다. b의 x값인 2는 a의 x값인 5보다 작으므로 트리의 왼쪽 자식 노드를 따라가야한다. 그런데, a의 왼쪽 자식 노드는 널이므로 b는 a의 왼쪽 자식 노드에 그림 10.3과 같이 삽입된다.   다음c를 입력하면 마찬가지로 루트노드인a에서 x값을 비교하면 c의 x값인 9가 a의 x값보다 크므로 그림 10.4와 같이 a의 오른쪽 자식노드에 삽입된다.   다음d를 입력하면 루트노드에서는a와 x축 값을 비교하여 왼쪽 자식노드인 b로 가게 된다. b와는 두번째 레벨이므로 y축의 값과 비교를 하면 d의 y축 값이 더 작으므 로 다시 왼쪽 자식노드로 이동하게 되고,이 경우 널 값이므로 그림10.5와 같이 b의 왼쪽 자식 노드로 저장된다.   마찬가지의 방법으로 나머지 데이타들을 삽입하면 그림 10.6과 같이 k-d 트리가 구성된다.   10.1.2 k-d 트리의 데이타 검색 k-d 트리의 검색 역시 삽입과 마찬가지로 트리의 레벨에 따라 각 차원의 값을 번 갈아서 비교한다. 예를 들어, 위와 같은 k-d 트리에서 (4,8) 위치의 점은 무엇인가? 하는 질의가 들어왔다고 가정하자.먼저 트리의 루트 노드에서는x값을 비교하여 질의 값의x값이 더 작으므로 왼쪽 자식 노드b를 방문하고, 다음 b에서는 y값을 비교하여 오른쪽 자식 노드인 j를 방문하게 된다. j와 질의 값을 비교하면 같으므로 (4,8) 위치 의 점은 j임을 알 수 있다. 마찬가지로 (6,2) 위치의 점을 검색한다고 하면 트리의 루 트부터 a, c를 거쳐 e 노드와 질의 값을 비교하게 된다. 여기서 질의의 x값이 e 점의 x값보다 작으므로 왼쪽 자식 노드를 방문해야 되지만,왼쪽 자식 노드가 널이므로 해 당하는 점이 없음을 알 수 있다. 따라서 k-d 트리의 높이를 h라 할 때, 이러한 점 검색 질의의 경우, 최악의 경우 의 수행시간은 O(h)가 된다. k-d 트리의 가장 큰 단점은 트리가 데이타가 입력되는 순서에 따라 달라진다는 점이다. 따라서 데이타의 분포나 입력 순서에 따라 트리가 균형적으로 구성되지 못하 여 트리의 높이가 높아질 수 있다. 예를 들어, 위와 같은 예에서 데이타가 g, d, b, e, h, a, f, c, i, j 와 같은 순서로 입력된다면 트리는 그림 10.7과 같이 구성된다. 이 경 우 c 점을 검색하기 위해서는 g, d, b, e, h, a, f 점의 노드를 방문하고 나서야 c점을 찾을 수 있게 된다. [출처] K-d 트리|작성자 후로그래머