알고리즘 & 자료구조/알고리즘&자료구조
K-d 트리
3DMP
2013. 4. 14. 15:00
10.1 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점을 찾을 수 있게 된다.  |
반응형