KD(k - dimensional tree) 트리에 대해서 개념을 이해하고 동작 원리를 파악한다.
KD 트리는 다차원 공간에서 데이터를 효율적으로 저장하고 탐색하기 위해 고안된
공간 분할 이진 탐색 트리이다.
주로 2차원 도는 3차원 이상의 좌표 기반 데이터를 다룰 때 사용되고 최근접 이웃 탐색, 범위 탐색 등 다양하게 사용된다.
이진 탐색 트리와 비슷하지만 k차원의 좌표 값을 가진다는 점에서 다르다.
KD 트리에서 깊이는 분할 기준 차원이다.
KD 트리의 생성 규칙을 정리하면