R 트리
-
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..