간격 트리 (Interval Tree)
Kernel에서도 많이 쓰이는 구조로, key 값으로 특정 하나의 값이 아니라 구간이 들어간다. Interval tree는 OS에서 프로세스 address영역을 관리 할 때 용이하게 쓰인다.
![](http://shumin.co.kr/wp/wp-content/uploads/2021/01/image-20.png)
만약 위와 같은 tree 구조가 있을 때, 특정 구간 (예를 들면 [12 ~ 13])이 포함되어 있는지를 확인 할 것이다. 이 때도 augmented tree와 동일하게 augmented 값을 활용한다.
Interval tree의 경우엔 key 값이 2개이기 때문에, 그 중에 큰 값을 augmented 값으로 사용한다. 그리고 만약 sub-node가 2개 이상 존재할 때는 augmented 값 중 큰 값을 사용한다. 이 내용을 적용해서 다시 tree를 보면 아래와 같다.
![](http://shumin.co.kr/wp/wp-content/uploads/2021/01/image-21.png)
구현
Interval tree의 각 노드가 어떻게 구성되어 있는지 보면 1) 시작 값, 2) 마지막 값, 3) augmented 값으로 구성된다.
struct interval_tree_node { struct rb_node rb; unsigned long start; /* Start of interval */ unsigned long last; /* Last location _in_ interval */ unsigned long __subtree_last; };
Interval tree를 augmented RB tree에서 확장해서 사용하기 위해선 augmented 값을 기존 방식 (모든 sub-tree의 augmented의 합에 1을 더한 값)에서 업데이트를 해야한다. 이를 위해서 Kernel code에선 자동으로 함수를 생성하도록 define
구문을 사용한다.
INTERVAL_TREE_DEFINE(struct interval_tree_node, rb, unsigned long, __subtree_last, START, LAST,, interval_tree) #define INTERVAL_TREE_DEFINE(ITSTRUCT, ITRB, ITTYPE, ITSUBTREE, ITSTART, ITLAST, ITSTATIC, ITPREFIX) /* Callbacks for augmented rbtree insert and remove */ \ \ static inline ITTYPE ITPREFIX ## _compute_subtree_last(ITSTRUCT *node) \ { \ ITTYPE max = ITLAST(node), subtree_last; \ if (node->ITRB.rb_left) { \ subtree_last = rb_entry(node->ITRB.rb_left, \ ITSTRUCT, ITRB)->ITSUBTREE; \ if (max < subtree_last) \ max = subtree_last; \ } \ if (node->ITRB.rb_right) { \ subtree_last = rb_entry(node->ITRB.rb_right, \ ITSTRUCT, ITRB)->ITSUBTREE; \ if (max < subtree_last) \ max = subtree_last; \ } \ return max; \ }
위 예시 코드는 interval_tree.c
와 interval_tree_generic.h
에서 발취해왔다. 위 코드가 실제 pre-processor를 거치게 되면 아래와 같은 코드가 될 것이다.
unsigned long interval_tree_compute_subtree_last(struct interval_tree_node *node) { unsigned long max = (node)->last, subtree_last; if (node->rb.rb_left) { subtree_last = rb_entry(node->rb.rb_left, struct interval_tree_node, rb)->__subtree_last; if (max < subtree_last) max = subtree_last; } if (node->rb.rb_right) { subtree_last = rb_entry(node->rb.rb_right, struct interval_tree_node, rb)->__subtree_last; if (max < subtree_last) max = subtree_last; } return max; }
위 코드를 보면 왼쪽과 오른쪽 sub-tree에서 max 값을 찾아서 큰 값을 찾아내는 함수를 볼 수 있다. 여기서 중요한 점은 삽입 할 때는 start 값을 가지고 좌우 탐색을 진행하며, augmented 값을 업데이트 할 때는 last 값을 사용한다.
탐색
예제를 통해서 Interval tree에서 탐색되는 과정을 보면 아래 그림과 같다.
![](http://shumin.co.kr/wp/wp-content/uploads/2021/01/image-22.png)
우선 root node에서 left node가 있는지를 보고, 있다면 start
값 (12)과 node->rb.rb_left
값 (14)를 비교한다. 만약 참이면 왼쪽 sub-tree로 이동한다. 만약 왼쪽 sub-tree의 augmented 값이 10이라고 하면 왼쪽에 대해서 검색하지 않을 것이다.
그리고 다시 왼쪽 sub-tree의 augmented 값과 비교하게 될텐데, 이때 12보다 작은 8이기 때문에 현재 node의 값을 비교해본다. node->start <= last
(5 <= 13)가 참이 되고, start <= node->last
(12 <= 10)가 참이 되지 않는다. 이때 오른쪽 노드를 검색해서 존재하면 오른쪽으로 node
가 이동한다. start <= node->__sub_tree_last
(12 <= 14)조건에 만족하기 때문에 continue
구문을 수행한다.
다시 왼쪽 sub-tree가 존재하는지 보고 값을 확인해도 start <= left->__sub_tree_last
조건을 만족하지 않으면서, 다음 조건인 node->start <= last
를 만족하면서 [12, 14]를 가리키는 노드를 return 한다.
struct interval_tree_node * interval_tree_subtree_search(struct interval_tree_node *node, unsigned long start, unsigned long last) { while (true) { if (node->rb.rb_left) { struct interval_tree_node *left = rb_entry(node->rb.rb_left, struct interval_tree_node, rb); if (start <= left->__sub_tree_last) { node = left; continue; } } if (node->start <= last) { if (start <= node->last) return node; if (node->rb.rb_right) { node = rb_entry(node->rb.rb_right, struct interval_tree_node, rb); if (start <= node->__sub_tree_last) continue; } } return NULL; } }
Interval tree는 process 할당 영역, disk 영역 등등 지금은 선형 구간에서 많이 쓰이고 있지만, 면이나 입체에서도 쓰면 충돌 감지도 할 수 있다.
최종적으로 노드 삽입과 검색을 위한 테스트 코드는 아래와 같다.
#include <stdio.h> #include <stdlib.h> #include <string.h> #include "interval_tree.h" #include "rbtree_augmented.h" #include "interval_tree_generic.h" #define INFO_NUM 6 struct interval_tree_node * interval_tree_subtree_search( struct interval_tree_node *, unsigned long, unsigned long); typedef struct { unsigned long start; unsigned long last; unsigned long __subtree_last; int color; } NODE_INFO; int __display(struct rb_node *temp, NODE_INFO (*array)[10], int *row, int *col) { struct interval_tree_node *info; if(temp == 0) return 0; ++*row; __display(temp->rb_left, array, row, col); info = rb_entry(temp, struct interval_tree_node, rb); array[*row][(*col)].color = rb_color(temp); array[*row][(*col)].start = info->start; array[*row][(*col)].last = info->last; array[*row][(*col)++].__subtree_last = info->__subtree_last; __display(temp->rb_right, array, row, col); --*row; } void display(struct rb_root *root) { int row = -1; int col = 0; NODE_INFO a[10][10] = {0,}; __display(root->rb_node, a, &row, &col); system("clear"); for(int i=0; i<10; i++) { for(int j=0; j<10; j++) { if(a[i][j].__subtree_last) { if(a[i][j].color == RB_RED) printf("<%2lu,%2lu,%2lu>", a[i][j].start, a[i][j].last, a[i][j].__subtree_last); else printf("[%2lu,%2lu,%2lu]", a[i][j].start, a[i][j].last, a[i][j].__subtree_last); } else printf("%10c", ' '); } printf("\n"); } getchar(); } int main() { struct rb_root root = {0}; int i, index; struct interval_tree_node *temp; struct interval_tree_node nodes[INFO_NUM] = { {{0,},13,15,}, {{0,},5,10,}, {{0,},20,23,}, {{0,},3,8,}, {{0,},12,14,}, {{0,},5,10,}, }; display(&root); for(i=0; i<INFO_NUM; i++) { interval_tree_insert(nodes+i, &root); display(&root); } temp = interval_tree_subtree_search( nodes, 12, 13 ); if( temp ) printf("%lu,%lu\n", temp->start, temp->last); else printf("%lu,%lu\n", 12UL, 16UL); return 0; }