알고리즘...89

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 트리는 한 노드에 있는 영역이 서로 겹칠 수 있으며 검색 경로가 유일하지 않을 수 있다.

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘