-
KD 트리 개요
KD 트리는 이진 검색 트리를 확장한 것으로 k 개의 필드로 이루어진 키를 사용하며, 이진 검색 트리와 비슷하게 동작 하나 레벨 별로 분기 시 하나의 필드만을 사용한다는 점이 다르다.
쉽게 배우는 알고리즘 KD 트리 그림 5-21 위 그림에서 보는 것처럼 KD 트리는 같은 레벨의 노드는 동등한 위치의 필드를 사용하여 분기를 진행하며 k 개의 필드를 가지는 KD 트리에서 레벨 k에 도달한 경우 다시 0 번째 필드를 사용하여 분기를 진행한다.