다차원 검색 트리
-
R 트리 알고리즘프로그래밍 기초/알고리즘 2021. 12. 9. 16:48
R 트리 B 트리를 다차원 검색 트리로 확장한 트리 자료구조이다. R 트리에는 다음의 두 종류의 노드가 존재한다. 영역 노드 트리의 차원에 따라 노드가 가지는 공간을 표현하는 노드 키 노드 실제 키와 소속된 페이지 번호를 가지는 노드 R 트리는 다음의 성질을 갖는다. 루트를 제외한 모든 내부 노드는 └k/2┘ ~ k 개의 영역을 갖는다. 모든 리프 노드는 같은 깊이를 가진다. 모든 레코드는 리프 노드에서만 가리킨다. R 트리의 표현 R 트리는 KDB 트리와 달리 키를 포함하는 최소 영역에만 노드가 존재한다. 아래와 키가 존재할 때 R트리의 표현은 다음과 같다. 이름 key1 key2 A 8 100 B 4 10 C 6 35 D 1 10 E 6 60 F 5 45 G 7 85 H 3 20 I 10 70 J 2..
-
KDB 트리 알고리즘프로그래밍 기초/알고리즘 2021. 11. 30. 14:07
KDB 트리 B 트리를 다차원 검색 트리로 확장한 트리 자료구조이다. KDB 트리는 노드의 키를 통해 분기하는 게 아니라 전체 영역을 쪼개가며 진행하게 된다. KDB 트리에는 다음의 두 종류의 노드가 존재한다. 영역 노드 트리의 차원에 따라 노드가 가지는 공간을 표현하는 노드 키 노드 실제 키와 소속된 페이지 번호를 가지는 노드 이때, k 차원의 키를 사용하는 영역 노드는 다음과 같이 표현된다. (, , ... , ) ※ KDB 트리의 모든 내부 노드는 영역 노드이며, 모든 리프 노드는 키 노드이다. KD 트리에서의 검색 KD 트리의 검색은 다음의 순서를 따른다. 루트 노드에서부터 검색하려는 키가 포함된 영역을 가지는 영역 노드를 따라 진행한다. 리프 노드에 도달한 경우 리프 노드에 검색하려는 키가 존재..
-
KD 트리 알고리즘프로그래밍 기초/알고리즘 2021. 11. 18. 18:51
KD 트리 이진 검색 트리를 다차원 검색 트리로 확장한 트리 자료구조이다. KD 트리는 같은 레벨의 노드는 동등한 위치의 필드를 사용하여 분기를 진행하며 k 개의 필드를 가지는 KD 트리에서 레벨 k에 도달한 경우 다시 0 번째 필드를 사용하여 분기를 진행한다. ※ 다차원 검색 트리는 노드의 키가 하나의 필드가 아닌 여러 개의 필드로 이루어진 검색 트리를 말한다. KD 트리에서의 검색 기본적으로 이진 검색 트리와 동일한 방식으로 탐색을 진행하나 KD 트리는 각 레벨 별로 다른 필드를 사용하여 검색을 진행하는 점이 다르다. 레벨 0 에서는 첫 번째 필드를 사용하여 분기하고 레벨 1에서는 두 번째 필드를 사용하여 분기를 진행한다. 이렇게 진행하다 레벨 k 에서는 다시 첫 번째 필드를 사용하는 방식으로 검색을..