R 트리 알고리즘

  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	30
K	8	50
L	4	50

 

쉽게 배우는 알고리즘 R 트리 그림 5-30

 

R 트리에서의 삽입과 삭제

R 트리의 삽입과 삭제 연산은 기본적으로 B 트리와 동일하게 진행된다.

단, 최소 영역에만 노드가 존재하므로 병합 혹은 분배가 일어났을 때 영역 노드가 함께 변하게 된다.

 

가령 그림 5-30의 데이터에 M과 N을 순서대로 삽입하게 된다면 트리의 영역은 다음과 같이 변하게 된다.

 

쉽게 배우는 알고리즘 R 트리 그림 5-31

 

NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소 (github.com)

GitHub - NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소

 

참고문헌

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