-
R 트리 삽입
기본적으로 R 트리의 삽입은 B 트리의 삽입처럼 동작한다.
- 삽입 가능한 노드를 찾은 뒤 값을 삽입 시도한다.
- 노드에 여분의 공간이 있으면 그대로 종료한다.
- 노드에 여분이 없으면 오버 플로우 처리를 하여 형제 노드에 분배한다.
이때, 노드를 분배하게 되면 R 트리의 영역에 변동이 생기게 된다.
가령 기존 트리에 M, N을 순서대로 삽입한다면 M을 삽입할 때는 여유 공간이 있어 값을 추가하고 종료하지만 N 이 삽입될 때는 형제 노드에 값을 분배하면서 영역이 달라지는 것을 확인할 수 있다.
쉽게 배우는 알고리즘 R 트리 그림 5-31 R 트리 삭제
R 트리의 삭제 처리도 기존 B 트리와 동일하게 진행된다. 다만, 이 때도 마찬가지로 언더플로우에 대한 처리를 진행하게 되면 영역의 모양은 달라지게 된다.