KD-트리 (K-Dimensional Tree) [k-차원 트리]
KD-트리 (K-Dimensional Tree) [k-차원 트리] KD-트리는 이진 탐색 트리를 확장한 것으로 k개(k>=2)의 필드로 이루어지는 키를 사용한다. 동일한 레벨에 있는 노드는 모두 동일한 하나의 필드만 이용해서 분기한다 KD-트리에서 검색을 이용해 내려간다는 것은 다차원 공간에서 이렇게 나누어진 결과에 따라 공간의 범위를 점점 좁혀나가는 것이다. 3차원일 경우 입체적인 형상이 된다. KD-트리 삽입 A(50, 50) → B(10, 70) → C(80, 85) → D(25, 20) → E(40, 85) → F(70, 85) → G(10, 60) 1. A(50, 50)이 루트 자리를 차지 2. B(10, 70)는 x값 10이 루트의 x값 50보다 작으므로 왼쪽 자식이 된다 3. C(80, 85..
2023. 10. 3.
