-
R 트리
B 트리를 다차원 검색이 가능하도록 수정한 검색 트리로 KDB 트리와 달리 키를 모두 포함하는 최소 영역에만 노드가 존재한다.
B 트리와 마찬가지로 영역 노드와 키 노드, 두 가지 노드가 존재한다.
R 트리는 다음의 성질을 갖는다.
- 루투를 제외한 모든 내부 노드는 └k/2┘ ~ k 개의 영역을 갖는다.
- 모든 리프 노드는 같은 깊이를 가진다.
- 모든 레코드는 리프 노드에서만 가리킨다.
아래와 키가 존재할 때 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 30 K 8 50 L 4 50 
쉽게 배우는 알고리즘 R 트리 그림 5-30 ※ R 트리는 한 노드에 있는 영역이 서로 겹칠 수 있으며 검색 경로가 유일하지 않을 수 있다.