빨강 검정 나무.. ??
학부생때 '레드 블랙 트리'를 보통 자료구조 시간에 들어보셨을 수도 있지만 못 들으신 분들은 이게 뭔 트리인지 하실겁니다. '이진트리', 'AVL트리'까지는 들어봤는데 말이죠. 혹시 레드(red)고 블랙(black)이니 빨갛고 까만 열매를 가진 트리인가라고 생각하신 분들은 통찰력이 뛰어난 분들입니다. 우리가 다룰 레드 블랙 트리도 진짜로 비슷하게 생겼거든요. '레드 블랙 트리'를 알기 위해서는 기본적으로 '이진트리'에 대해 알고 있어야 합니다. '이진트리'는 '이진탐색트리'라고도 부르는데 생겨난 목적이 탐색을 위해 태어난 녀석이기 때문이라죠. 사실 빠른 탐색만을 위해서 존재한다면 해쉬(hash) 자료구조를 따라갈 녀석이 없겠지만, 해쉬(hash) 자료구조는 용량을 팔아 속도를 얻는 녀석이기 때문에 효율성면에서는 이진트리보다는 경쟁력이 떨어집니다. 그렇기 때문에 용량도 적당히 사용하고 비교적 탐색속도도 빠른 이진탐색을 사용하는 것이죠. 그렇다면 왜 이진탐색이 빠른걸까요? 바로 아래와 같이 생겨먹었기 때문입니다.
'이진트리'는 보시는 바와 같이 루트 노드부터 검색을 시작하게 되는데 자식은 꼭 두명이여야만 하고, 자신보다 작은 값을 왼쪽 노드에 두고 큰 값을 오른쪽 노드에 두는 규칙을 가지고 있습니다. 때문에 탐색시 모든 노드를 고려할 필요가 없습니다. 예를 들어 위의 '이진트리'에서 11을 찾는다고 치면 단 두번의 비교로 11을 찾을 수가 있다는 거죠. 와우~! 하지만 이렇게나 괜찮은 '이진탐색트리'에도 치명적인 단점이 고려했으니 바로 아래와 같은 경우는 해결하지 못 한다는 점이었습니다. 쿠궁....
위와 같이 값이 한쪽으로 쏠리게 들어왔을 경우에 가장 아래에 있는 값을 검색하기 위해서는 결국 모든 경우를 고려해야 한다는 겁니다. 이건 일반적인 순차검색과 다를바가 없죠. 즉 균형잡힌 경우에는 O(logN)의 속도를 보장하지만 위와 같이 쏠린 경우에는 O(N)의 성능밖에 못 내는 것입니다. 이렇듯 최악의 조건까지 고려해야지만 훌륭한 알고리즘이라고 할 수 있습니다. 이게 바로 '균형이진트리' 의 탄생비화(?) 입니다.
'균형이진트리'의 종류로는 AVL트리, 2-3-4트리, 레드 블랙 트리등이 있습니다. AVL트리는 균형이진트리의 초기모델로서 최악의 조건에서 성능적으로 레드 블랙 트리보다 후달리기에 지금 시점에서는 레드 블랙 트리가 대중적으로 사용되고 있습니다. 둘다 성능은 O(logN)이며 최악의 조건에서도 O(logN)을 보장하고 있습니다. 대단하지 않나요?ㅎㅎㅎ
일단 커널코드를 보기 전에 이렇게나 대단한 레드 블랙 트리가 어떠한 원리로 움직이는지에 대해 개념적으로 짚고 넘어가도록 하겠습니다. 뭐든지 기본이 중요한 법이니깐요. ^^ 우선 레드 블랙 트리의 모양새는 아래와 같습니다.
레드 블랙 트리를 처음 보시는 분이라면 이름 한번 잘 지었다고 생각들겁니다. 정말로 트리가 알록달록 빨강 까망이니깐요 ㅎㅎㅎ 하지만 심심한 트리에다 멋 부린다고 이렇게 꾸민 것이 아닙니다. 알록달록한 빨갛고 검은색의 컬러가 사실 트리의 균형을 맞추는 열쇠입니다. 그 비결은 예제를 통해서 알아보도록 하겠습니다. 우선 예제를 보기 위해 레드 블랙 트리의 규칙을 알려드리겠습니다.
1. 모든 노드는 빨강 아니면 검정이다.
2. 루트 노드는 검정이다.
3. 모든 잎 노드는 검정이다.
4. 빨간 노드의 자식들은 모두 검정이다. 하지만 검정노드의 자식이 빨강일 필요가 없다.
5. 루트 노드에서 모든 잎 노드 사이에 있는 검은 색 노드의 수는 모두 동일하다.
이렇게 총 5가지의 규칙이 있는데 규칙은 아래에서 위로 올라갈수록 우선순위가 높아집니다. 즉 4번보다는 2번이 더 우선순위가 높은 것이죠. 이를 명심하시구 예제를 보시도록 하겠습니다.
① 우선 첫번째 '1'이 삽입되었습니다. 첫번째 노드 이므로 당연히 루트가 됩니다. 새 노드의 초기값은 빨강이지만 2번 규칙에 따르려면 루트 노드는 검정색이어야 하는 군요. 그럼 일단 새 노드를 검정색으로 칠하겠습니다.
② 기존의 노드에 새로운 노드 '2'가 들어왔습니다. '2'는 '1'보다 크므로 '1'의 오른쪽에 옵니다. 여기서 새로 들어오는 노드는 무조건 빨강색입니다. 이유는 새로운 노드의 초기값이 빨강으로 되어있기 때문이죠.
③ '3'을 삽입해 보았습니다. 헉! 하지만 이때 4번 규칙을 위반하게 되는군요. 이럴 경우에는 여러가지 경우의 수로 분기할 수 있습니다.(아래 5가지 경우 중에 2번에 해당) 레드 블랙 트리에서는 부모가 빨강일때 새로운 노드가 삽입된다면, 새로 삽입되는 노드의 위치가 왼쪽 또는 오른쪽에 오느냐에 따라 결과가 달라집니다. 여기서는 부모의 오른쪽에 오므로 ⑴할아버지를 중심으로 왼쪽으로 회전(__rb_rotate_left)하게 됩니다. 그리고 ⑵내려온 노드는 빨강이 되고 올라간 노드는 검정이 됩니다.
⑴ 삼촌이 없고 새노드가 부모의 왼쪽 자식인 경우 (X)
⑵ 삼촌이 없고 새노드가 부모의 오른쪽 자식인 경우 (O)
⑶ 삼촌이 있고 삼촌도 빨간색일 경우 (X)
⑷ 삼촌이 있고 삼촌은 검은색이며 새노드가 부모의 왼쪽 자식인 경우 (X)
⑸ 삼촌이 있고 삼촌은 검은색이며 새노드가 부모의 오른쪽 자식인 경우 (X)
④ '4'를 삽입하게 되었을때 삼촌이 있고 삼촌도 빨간색일 경우라면 어떻게 될까요? 이럴 때는 기존 노드의 색상을 수정하게 됩니다. 바로 부모노드와 삼촌노드를 검은색으로 칠하고 할아버지 노드를 빨간색으로 칠하면 됩니다. 하지만 할아버지를 빨간색으로 칠하게 되면 2번 규칙에 위배되므로 다시 검정색으로 칠합니다.
⑴ 삼촌이 없고 새노드가 부모의 왼쪽 자식인 경우 (X)
⑵ 삼촌이 없고 새노드가 부모의 오른쪽 자식인 경우 (X)
⑶ 삼촌이 있고 삼촌도 빨간색일 경우 (O)
⑷ 삼촌이 있고 삼촌은 검은색이며 새노드가 부모의 왼쪽 자식인 경우 (X)
⑸ 삼촌이 있고 삼촌은 검은색이며 새노드가 부모의 오른쪽 자식인 경우 (X)
⑤ '5'를 삽입하였습니다. 아래의 경우중 2번에 해당하므로 ⑴할아버지를 중심으로 왼쪽으로 회전(__rb_rotate_left)하게 됩니다. 그리고 ⑵내려온 노드는 빨강이 되고 올라간 노드는 검정이 됩니다. 아까 한번 했었던 동작이죠?ㅎㅎㅎ
⑴ 삼촌이 없고 새노드가 부모의 왼쪽 자식인 경우 (X)
⑵ 삼촌이 없고 새노드가 부모의 오른쪽 자식인 경우 (O)
⑶ 삼촌이 있고 삼촌도 빨간색일 경우 (X)
⑷ 삼촌이 있고 삼촌은 검은색이며 새노드가 부모의 왼쪽 자식인 경우 (X)
⑸ 삼촌이 있고 삼촌은 검은색이며 새노드가 부모의 오른쪽 자식인 경우 (X)
⑦ '6'을 삽입하였습니다. 아까와 같은 경우가 또 왔군요. 삼촌이 있고 삼촌도 빨간색일 경우라면 부모노드와 삼촌노드를 검은색으로 칠하고 할아버지 노드를 빨간색으로 칠하면 됩니다.
⑴ 삼촌이 없고 새노드가 부모의 왼쪽 자식인 경우 (X)
⑵ 삼촌이 없고 새노드가 부모의 오른쪽 자식인 경우 (X)
⑶ 삼촌이 있고 삼촌도 빨간색일 경우 (O)
⑷ 삼촌이 있고 삼촌은 검은색이며 새노드가 부모의 왼쪽 자식인 경우 (X)
⑸ 삼촌이 있고 삼촌은 검은색이며 새노드가 부모의 오른쪽 자식인 경우 (X)
⑧ '7'을 삽입하였습니다. 아래의 경우중 2번에 해당하므로 ⑴할아버지를 중심으로 왼쪽으로 회전(__rb_rotate_left)하게 됩니다. 그리고 ⑵내려온 노드는 빨강이 되고 올라간 노드는 검정이 됩니다. 그런데 트리가 뭔가 어정쩡한게 균형이 안 맞아보이기는 합니다; 과연...
⑴ 삼촌이 없고 새노드가 부모의 왼쪽 자식인 경우 (X)
⑵ 삼촌이 없고 새노드가 부모의 오른쪽 자식인 경우 (O)
⑶ 삼촌이 있고 삼촌도 빨간색일 경우 (X)
⑷ 삼촌이 있고 삼촌은 검은색이며 새노드가 부모의 왼쪽 자식인 경우 (X)
⑸ 삼촌이 있고 삼촌은 검은색이며 새노드가 부모의 오른쪽 자식인 경우 (X)
⑨ '8'을 삽입하였습니다. 마찬가지로 삼촌이 있고 삼촌도 빨간색일 경우라면 부모노드와 삼촌노드를 검은색으로 칠하고 할아버지 노드를 빨간색으로 칠하면 됩니다.
⑴ 삼촌이 없고 새노드가 부모의 왼쪽 자식인 경우 (X)
⑵ 삼촌이 없고 새노드가 부모의 오른쪽 자식인 경우 (X)
⑶ 삼촌이 있고 삼촌도 빨간색일 경우 (O)
⑷ 삼촌이 있고 삼촌은 검은색이며 새노드가 부모의 왼쪽 자식인 경우 (X)
⑸ 삼촌이 있고 삼촌은 검은색이며 새노드가 부모의 오른쪽 자식인 경우 (X)
그런데 여기서 문제가 발생합니다. 색깔을 바꾸기는 했는데 여전히 할아버지 노드와 증조 할아버지 노드가 똑같은 빨강이군요. 여기서 레드 블랙 트리의 4번 규칙을 어긋나게 됩니다.
1. 모든 노드는 빨강 아니면 검정이다.
2. 루트 노드는 검정이다.
3. 모든 잎 노드는 검정이다.
4. 빨간 노드의 자식들은 모두 검정이다. 하지만 검정노드의 자식이 빨강일 필요가 없다.
5. 루트 노드에서 모든 잎 노드 사이에 있는 검은 색 노드의 수는 모두 동일하다.
이럴 경우에는 아래 그림처럼 할아버지 노드를 새 노드로 생각하고 다시한번 규칙을 검사하게 됩니다.
할아버지 노드를 새 노드라고 생각하셨나요? 왜 그럴까라고 의심이 드시겠지만 일단 믿고 가자구요~ㅎㅎㅎ 그럼 다시 시작해보겠습니다. 새 노드인 '6'의 값을 가지는 노드의 부모를 보니 빨강입니다. 그렇다면 아래의 규칙 5번에 걸리게 되는군요. 생각해보니 지금까지 적용되었던 경우의 수중에 5번은 처음입니다. 과연 5번일 경우에는 노드가 어떻게 변하게 될까요? 바로 아래 그림과 같습니다. 즉 ⑴할아버지를 중심으로 왼쪽으로 회전(__rb_rotate_left)하게 됩니다. 그리고 ⑵내려온 노드는 빨강이 되고 올라간 노드는 검정이 됩니다. 그런데 여기서 부모 노드가 올라가면서 왼쪽 자식을 버리게 되는데, 이때 ⑶내려온 노드가 올라온 노드의 왼쪽 자식을 입양합니다.
⑴ 삼촌이 없고 새노드가 부모의 왼쪽 자식인 경우 (X)
⑵ 삼촌이 없고 새노드가 부모의 오른쪽 자식인 경우 (X)
⑶ 삼촌이 있고 삼촌도 빨간색일 경우 (X)
⑷ 삼촌이 있고 삼촌은 검은색이며 새노드가 부모의 왼쪽 자식인 경우 (X)
⑸ 삼촌이 있고 삼촌은 검은색이며 새노드가 부모의 오른쪽 자식인 경우 (O)
⑩ 우와~ 1에서 8까지 삽입이 끝나고 나니 자동으로 균형을 이루고 있는 트리를 볼 수 있습니다. 놀랍지 않습니까? 이것이 바로 레드 블랙 트리 입니다.
이렇듯 레드 블랙 트리는 삽입과 동시에 균형을 맞추고 있으며 최소한의 포인터 연산으로 균형을 잡고 있음을 알 수 있습니다. 그럼 진짜로 위의 메커니즘대로 작동하는지 커널 코드를 윈도우 환경에 맞게 변형하여 테스트 보았습니다. 아래 스크린 샷에 보여지는 트리는 레드 블랙 트리를 왼쪽으로 눕혀놓은 거라고 보시면 됩니다. ^^
커널 코드를 분석하기에 앞서 윈도우에 돌아가는 변형된 레드 블랙 트리 코드를 설명하는 것은 개념을 자칫 흔들 수 있기에 생략하도록 하겠습니다. 그럼 이제 레드 블랙 트리가 뭔지 알았으니 커널 코드를 봐야겠죠? 위의 레드 블랙 트리가 리눅스에 어떻게 적용되었는지 리눅스 커널(Linux Kernel version 3.3)을 통해 살펴보도록 하겠습니다.
아래는 linux-3.3.3\linux-3.3.3\include\linux\rbtree.h 의 내용입니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 | /* Red Black Trees (C) 1999 Andrea Arcangeli<andrea@suse.de> This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA linux/include/linux/rbtree.h To use rbtrees you'll have to implement your own insert and search cores. This will avoid us to use callbacks and to drop drammatically performances. I know it's not the cleaner way, but in C (not in C++) to get performances and genericity... Some example of insert and search follows here. The search is a plain normal search over an ordered tree. The insert instead must be implemented in two steps: First, the code must insert the element in order as a red leaf in the tree, and then the support library function rb_insert_color() must be called. Such function will do the not trivial work to rebalance the rbtree, if necessary.-----------------------------------------------------------------------static inline struct page * rb_search_page_cache(struct inode * inode, unsigned long offset){ struct rb_node * n = inode->i_rb_page_cache.rb_node; struct page * page; while (n) { page = rb_entry(n, struct page, rb_page_cache); if (offset< page->offset) n = n->rb_left; else if (offset > page->offset) n = n->rb_right; else return page; } return NULL;}static inline struct page * __rb_insert_page_cache(struct inode * inode, unsigned long offset, struct rb_node * node){ struct rb_node ** p = &inode->i_rb_page_cache.rb_node; struct rb_node * parent = NULL; struct page * page; while (*p) { parent = *p; page = rb_entry(parent, struct page, rb_page_cache); if (offset< page->offset) p = &(*p)->rb_left; else if (offset > page->offset) p = &(*p)->rb_right; else return page; } rb_link_node(node, parent, p); return NULL;}static inline struct page * rb_insert_page_cache(struct inode * inode, unsigned long offset, struct rb_node * node){ struct page * ret; if ((ret = __rb_insert_page_cache(inode, offset, node))) goto out; rb_insert_color(node, &inode->i_rb_page_cache); out: return ret;}-----------------------------------------------------------------------*/#ifndef _LINUX_RBTREE_H#define _LINUX_RBTREE_H#include<linux/kernel.h>#include<linux/stddef.h>struct rb_node{ unsigned long rb_parent_color;#define RB_RED 0#define RB_BLACK 1 struct rb_node *rb_right; struct rb_node *rb_left;} __attribute__((aligned(sizeof(long)))); /* The alignment might seem pointless, but allegedly CRIS needs it */struct rb_root{ struct rb_node *rb_node;};#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))#define rb_color(r) ((r)->rb_parent_color & 1)#define rb_is_red(r) (!rb_color(r))#define rb_is_black(r) rb_color(r)#define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0)#define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0)static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p){ rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;}static inline void rb_set_color(struct rb_node *rb, int color){ rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;}#define RB_ROOT (struct rb_root) { NULL, }#define rb_entry(ptr, type, member) container_of(ptr, type, member)#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)#define RB_EMPTY_NODE(node) (rb_parent(node) == node)#define RB_CLEAR_NODE(node) (rb_set_parent(node, node))static inline void rb_init_node(struct rb_node *rb){ rb->rb_parent_color = 0; rb->rb_right = NULL; rb->rb_left = NULL; RB_CLEAR_NODE(rb);}extern void rb_insert_color(struct rb_node *, struct rb_root *);extern void rb_erase(struct rb_node *, struct rb_root *);typedef void (*rb_augment_f)(struct rb_node *node, void *data);extern void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data);extern struct rb_node *rb_augment_erase_begin(struct rb_node *node);extern void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data);/* Find logical next and previous nodes in a tree */extern struct rb_node *rb_next(const struct rb_node *);extern struct rb_node *rb_prev(const struct rb_node *);extern struct rb_node *rb_first(const struct rb_root *);extern struct rb_node *rb_last(const struct rb_root *);/* Fast replacement of a single node without remove/rebalance/add/rebalance */extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root);static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, struct rb_node ** rb_link){ node->rb_parent_color = (unsigned long )parent; node->rb_left = node->rb_right = NULL; *rb_link = node;}#endif /* _LINUX_RBTREE_H */ |
위에 외부 지정자 extern으로 선언된 함수나 구조체 변수들은 구현부 파일에서 확인할 수 있습니다. 구현부 파일은 아래와 같습니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 | /* Red Black Trees (C) 1999 Andrea Arcangeli<andrea@suse.de> (C) 2002 David Woodhouse<dwmw2@infradead.org> This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA linux/lib/rbtree.c*/#include<linux/rbtree.h>#include<linux/module.h>static void __rb_rotate_left(struct rb_node *node, struct rb_root *root){ struct rb_node *right = node->rb_right; struct rb_node *parent = rb_parent(node); if ((node->rb_right = right->rb_left)) rb_set_parent(right->rb_left, node); right->rb_left = node; rb_set_parent(right, parent); if (parent) { if (node == parent->rb_left) parent->rb_left = right; else parent->rb_right = right; } else root->rb_node = right; rb_set_parent(node, right);}static void __rb_rotate_right(struct rb_node *node, struct rb_root *root){ struct rb_node *left = node->rb_left; struct rb_node *parent = rb_parent(node); if ((node->rb_left = left->rb_right)) rb_set_parent(left->rb_right, node); left->rb_right = node; rb_set_parent(left, parent); if (parent) { if (node == parent->rb_right) parent->rb_right = left; else parent->rb_left = left; } else root->rb_node = left; rb_set_parent(node, left);}void rb_insert_color(struct rb_node *node, struct rb_root *root){ struct rb_node *parent, *gparent; while ((parent = rb_parent(node)) && rb_is_red(parent)) { gparent = rb_parent(parent); if (parent == gparent->rb_left) { { register struct rb_node *uncle = gparent->rb_right; if (uncle && rb_is_red(uncle)) { rb_set_black(uncle); rb_set_black(parent); rb_set_red(gparent); node = gparent; continue; } } if (parent->rb_right == node) { register struct rb_node *tmp; __rb_rotate_left(parent, root); tmp = parent; parent = node; node = tmp; } rb_set_black(parent); rb_set_red(gparent); __rb_rotate_right(gparent, root); } else { { register struct rb_node *uncle = gparent->rb_left; if (uncle && rb_is_red(uncle)) { rb_set_black(uncle); rb_set_black(parent); rb_set_red(gparent); node = gparent; continue; } } if (parent->rb_left == node) { register struct rb_node *tmp; __rb_rotate_right(parent, root); tmp = parent; parent = node; node = tmp; } rb_set_black(parent); rb_set_red(gparent); __rb_rotate_left(gparent, root); } } rb_set_black(root->rb_node);}EXPORT_SYMBOL(rb_insert_color);static void __rb_erase_color(struct rb_node *node, struct rb_node *parent, struct rb_root *root){ struct rb_node *other; while ((!node || rb_is_black(node)) && node != root->rb_node) { if (parent->rb_left == node) { other = parent->rb_right; if (rb_is_red(other)) { rb_set_black(other); rb_set_red(parent); __rb_rotate_left(parent, root); other = parent->rb_right; } if ((!other->rb_left || rb_is_black(other->rb_left)) && (!other->rb_right || rb_is_black(other->rb_right))) { rb_set_red(other); node = parent; parent = rb_parent(node); } else { if (!other->rb_right || rb_is_black(other->rb_right)) { rb_set_black(other->rb_left); rb_set_red(other); __rb_rotate_right(other, root); other = parent->rb_right; } rb_set_color(other, rb_color(parent)); rb_set_black(parent); rb_set_black(other->rb_right); __rb_rotate_left(parent, root); node = root->rb_node; break; } } else { other = parent->rb_left; if (rb_is_red(other)) { rb_set_black(other); rb_set_red(parent); __rb_rotate_right(parent, root); other = parent->rb_left; } if ((!other->rb_left || rb_is_black(other->rb_left)) && (!other->rb_right || rb_is_black(other->rb_right))) { rb_set_red(other); node = parent; parent = rb_parent(node); } else { if (!other->rb_left || rb_is_black(other->rb_left)) { rb_set_black(other->rb_right); rb_set_red(other); __rb_rotate_left(other, root); other = parent->rb_left; } rb_set_color(other, rb_color(parent)); rb_set_black(parent); rb_set_black(other->rb_left); __rb_rotate_right(parent, root); node = root->rb_node; break; } } } if (node) rb_set_black(node);}void rb_erase(struct rb_node *node, struct rb_root *root){ struct rb_node *child, *parent; int color; if (!node->rb_left) child = node->rb_right; else if (!node->rb_right) child = node->rb_left; else { struct rb_node *old = node, *left; node = node->rb_right; while ((left = node->rb_left) != NULL) node = left; if (rb_parent(old)) { if (rb_parent(old)->rb_left == old) rb_parent(old)->rb_left = node; else rb_parent(old)->rb_right = node; } else root->rb_node = node; child = node->rb_right; parent = rb_parent(node); color = rb_color(node); if (parent == old) { parent = node; } else { if (child) rb_set_parent(child, parent); parent->rb_left = child; node->rb_right = old->rb_right; rb_set_parent(old->rb_right, node); } node->rb_parent_color = old->rb_parent_color; node->rb_left = old->rb_left; rb_set_parent(old->rb_left, node); goto color; } parent = rb_parent(node); color = rb_color(node); if (child) rb_set_parent(child, parent); if (parent) { if (parent->rb_left == node) parent->rb_left = child; else parent->rb_right = child; } else root->rb_node = child; color: if (color == RB_BLACK) __rb_erase_color(child, parent, root);}EXPORT_SYMBOL(rb_erase);static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data){ struct rb_node *parent;up: func(node, data); parent = rb_parent(node); if (!parent) return; if (node == parent->rb_left && parent->rb_right) func(parent->rb_right, data); else if (parent->rb_left) func(parent->rb_left, data); node = parent; goto up;}/* * after inserting @node into the tree, update the tree to account for * both the new entry and any damage done by rebalance */void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data){ if (node->rb_left) node = node->rb_left; else if (node->rb_right) node = node->rb_right; rb_augment_path(node, func, data);}EXPORT_SYMBOL(rb_augment_insert);/* * before removing the node, find the deepest node on the rebalance path * that will still be there after @node gets removed */struct rb_node *rb_augment_erase_begin(struct rb_node *node){ struct rb_node *deepest; if (!node->rb_right && !node->rb_left) deepest = rb_parent(node); else if (!node->rb_right) deepest = node->rb_left; else if (!node->rb_left) deepest = node->rb_right; else { deepest = rb_next(node); if (deepest->rb_right) deepest = deepest->rb_right; else if (rb_parent(deepest) != node) deepest = rb_parent(deepest); } return deepest;}EXPORT_SYMBOL(rb_augment_erase_begin);/* * after removal, update the tree to account for the removed entry * and any rebalance damage. */void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data){ if (node) rb_augment_path(node, func, data);}EXPORT_SYMBOL(rb_augment_erase_end);/* * This function returns the first node (in sort order) of the tree. */struct rb_node *rb_first(const struct rb_root *root){ struct rb_node *n; n = root->rb_node; if (!n) return NULL; while (n->rb_left) n = n->rb_left; return n;}EXPORT_SYMBOL(rb_first);struct rb_node *rb_last(const struct rb_root *root){ struct rb_node *n; n = root->rb_node; if (!n) return NULL; while (n->rb_right) n = n->rb_right; return n;}EXPORT_SYMBOL(rb_last);struct rb_node *rb_next(const struct rb_node *node){ struct rb_node *parent; if (rb_parent(node) == node) return NULL; /* If we have a right-hand child, go down and then left as far as we can. */ if (node->rb_right) { node = node->rb_right; while (node->rb_left) node=node->rb_left; return (struct rb_node *)node; } /* No right-hand children. Everything down and left is smaller than us, so any 'next' node must be in the general direction of our parent. Go up the tree; any time the ancestor is a right-hand child of its parent, keep going up. First time it's a left-hand child of its parent, said parent is our 'next' node. */ while ((parent = rb_parent(node)) && node == parent->rb_right) node = parent; return parent;}EXPORT_SYMBOL(rb_next);struct rb_node *rb_prev(const struct rb_node *node){ struct rb_node *parent; if (rb_parent(node) == node) return NULL; /* If we have a left-hand child, go down and then right as far as we can. */ if (node->rb_left) { node = node->rb_left; while (node->rb_right) node=node->rb_right; return (struct rb_node *)node; } /* No left-hand children. Go up till we find an ancestor which is a right-hand child of its parent */ while ((parent = rb_parent(node)) && node == parent->rb_left) node = parent; return parent;}EXPORT_SYMBOL(rb_prev);void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root){ struct rb_node *parent = rb_parent(victim); /* Set the surrounding nodes to point to the replacement */ if (parent) { if (victim == parent->rb_left) parent->rb_left = new; else parent->rb_right = new; } else { root->rb_node = new; } if (victim->rb_left) rb_set_parent(victim->rb_left, new); if (victim->rb_right) rb_set_parent(victim->rb_right, new); /* Copy the pointers/colour from the victim to the replacement */ *new = *victim;}EXPORT_SYMBOL(rb_replace_node); |
레드 블랙 트리 코드를 확인하셨나요? ㅎㄷㄷ
539 라인이나 되는 코드에 아직까지는 먼소린지 감이 안 잡힐 수도 있습니다. 하지만 이 정도에 아직 놀라시면 안됩니다. 이 rbtree 코드 안에는 삽입을 하는 함수가 존재하지 않으니깐요.. 엥?? 그럼 도대체 이 알고리즘을 개발한 작자는 어떻게 삽입하는 함수부를 구현해라는 걸까요? 설마 코드 보고 알아서 분석해서 개발하라는 거는 너무 무책임한 주문을 하는 것을 아닐테고 말이죠. 다행스럽게도 레드 블랙 트리 커널 코드를 개발하신 분은 그렇게 인정이 없지 않았습니다. 'rbtree.h'의 주석을 살펴보시면 Andrea라는 아저씨가 주석에다가 힌트를 남겨놓은 것을 확인할 수 있습니다. 주석을 참고해서 개발해라는 건데 요래서 주석을 잘 달아야 한다는거 아시겠죠?
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | static inline struct page * __rb_insert_page_cache(struct inode * inode, unsigned long offset, struct rb_node * node){ struct rb_node ** p = &inode->i_rb_page_cache.rb_node; struct rb_node * parent = NULL; struct page * page; while (*p) { parent = *p; page = rb_entry(parent, struct page, rb_page_cache); if (offset< page->offset) p = &(*p)->rb_left; else if (offset > page->offset) p = &(*p)->rb_right; else return page; } rb_link_node(node, parent, p); return NULL;}static inline struct page * rb_insert_page_cache(struct inode * inode, unsigned long offset, struct rb_node * node){ struct page * ret; if ((ret = __rb_insert_page_cache(inode, offset, node))) goto out; rb_insert_color(node, &inode->i_rb_page_cache); out: return ret;} |
레드 블랙 트리의 삽입을 설명하기에 앞서 우선 레드 블랙 트리의 구조체부터 살펴보겠습니다. 구조체를 가만히 살펴보니 낮선 코드가 눈에 보이는군요. 바로 구조체 안에 #define구문이 선언되어 있습니다; 이것은 레드 블랙 트리 구조체의 가독성을 높이기 위한 목적으로 사용되었는데 어짜피 매크로 구문은 컴파일시 코드로 변환되기 때문에 상관없는 것이죠.
그럼 아래의 아래 attribute__((aligned(sizeof(long))))는 무엇일까요? 점점 난해해집니다..이것은 Linux gcc 컴파일러에서 확장적으로 지원하는 것으로 윈도우의 #progrma pack과 비슷한 개념입니다. 구조체의 시작 주소를 정렬하라는 것인데 구조체의 전체의 사이즈가 무조건 address의 4 byte alingnment에 맞춰라는 이야기 입니다. 즉 주소가 0, 4, 8, 12... 이렇게 늘어가게 되는 것이죠. 이렇게 하게되면 주소를 2진수로 봤을 때 주소가 4의 배수로 뛰기때문에 마지막 2비트는 0으로 고정되어 있습니다. 즉 최하위 2비트는 비게되므로 레드 블랙 트리에서는 이 공간을 색상을 저장하는 용도로 사용하고 있습니다. 실제로는 그 중에서도 1비트만 사용하고 있지만요 ㅎㅎ 사실 커널 2.4버전에서는 rb_parent와 rb_color가 따로 분리되어 있었지만 2.6 이후로는 하나의 변수로 공유하기 시작했다네요. 대단한 테크닉이죠! 언젠가 제가 rb_tree에 대한 자료를 알아보기 위해 네이버 지식인님들을 순례하고 있었는데 레드 블랙 트리의 약점을 묻는 지식인 질문에 아무개님(?)이 대답한 답글이 생각납니다.
"레드 블랙 트리는 구조체에 색상을 따로 저장해야 하기에 더 많은 용량을 차지하게 되므로 다른 트리에 비해 비효율적이다" 라는 답글이었습니다. 하지만 실제로는 그렇지 않다는 것을 알 수 있겠지요? 하나의 변수를 공유하고 있으니깐요.^^
struct rb_node
{
unsigned long rb_parent_color;
#define RB_RED 0
#define RB_BLACK 1
struct rb_node *rb_right;
struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
/* The alignment might seem pointless, but allegedly CRIS needs it */
아래로 내려가면 단 하나의 rb_node* 변수를 싸고 있는 구조체를 볼 수 있습니다. 구조체로 싸고 있는 놈도 하나인데 이렇게 사용하는 이유는 나중에 구조체의 확장을 위해 사용한 테크닉이라고 합니다. 캡슐화죠ㅎㅎ 역시 고수님들께 참 많은 테크닉을 배울 수 있는 것 같습니다.
{
struct rb_node *rb_node;
};
아래를 보니 비트연산을 매크로 함수로 만들어놓은 구문이 눈에 들어오는군요. 비트 연산이 들어가면 괜히 먼가 복잡해 보입니다..ㅠ_ㅠ 저만 그런가요?ㅎㅎ 우선 rb_parent(r) 를 보면 rb_parent_color 변수에 ~3을 &연산하고 있습니다. 이것은 하위 2비트는 빼고 나머지 비트를 뽑아서 (struct rb_node *)로 강제형변환 해주고 있는 것을 확인 할 수 있습니다. 즉 이것은 부모의 노드를 가르키는 포인터를 뽑아 내는 거라 보심됩니다. 그럼 반대로 하위 2비트를 보는 함수도 봐야겠군요. rb_color(r) 함수를 보면 1을 &연산하고 있는게 보이는데 이를보니 하위 2비트 전부를 사용하지는 않고 1비트만 활용하고 있다는 것을 알 수 있습니다. 그렇다면 나머지 한 비트의 의미는 뭘까요? 백업용일까요? 제 생각에는 나중에 확장성을 고려해서 남겨둔 것 같은데 그 의미는 알 길이 없군요. ㅎㅎ 메일 이라도 보내봐야 할까봅니다.^^; 아무튼 다음 매크로 함수들의 의미를 보면 해석하는데 크게 어려움이 없을 겁니다. rb_is_red는 노드의 색이 빨간색인지 물어보고 있고, rb_is_black은 노드의 색이 검정인지 물어보며, rb_set_red는 노드를 빨간색으로 셋팅, rb_set_black은 검정으로 셋팅하는 매크로 함수들 입니다. 어렵지 않죠??
#define rb_parent(r) ((struct rb_node *)((r)->rb_parent_color & ~3))
#define rb_color(r) ((r)->rb_parent_color & 1)
#define rb_is_red(r) (!rb_color(r))
#define rb_is_black(r) rb_color(r)
#define rb_set_red(r) do { (r)->rb_parent_color &= ~1; } while (0)
#define rb_set_black(r) do { (r)->rb_parent_color |= 1; } while (0)
static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
{
rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
}
static inline void rb_set_color(struct rb_node *rb, int color)
{
rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
}
그런데 애매한 것이 있는데 rb_set_red 매크로에서 do{ ... }while(0)은 왜 저렇게 사용하고 있을까 하시는 분들이 있으실 겁니다. 심심해서 저렇게 해놓은건 아닐테고 말이죠. 사실 저 구문을 사용하는 두 가지 이유가 있는데 첫번째는 블럭을 활용하기 위함이고, 두번째는 매크로 정의 구문에서 여러 문장이 사용되면 발생하는 에러를 막기 위함이라고 합니다. 두번째 이유의 예를 들자면 아래와 같은 경우를 예방하기 위한 것이죠.
1. 정의된 메크로
#define FOO(x) \
printf("arg is %s\n", x); \
do_something_useful(x);
2. 사용 예
if (blah == 2)
FOO(blah);
else
...
3. 실제 내용
if (blah == 2)
printf("arg is %s\n", blah);
do_something_useful(blah);;/* blah blah */ <-- 요 부분 때문에 아래의 else에서 에러
else
...
아래 매크로 함수들도 이해하기기에는 크게 무리 없으실 겁니다. 비교적 코드가 짧죠? 그런데 눈에 익숙한 녀석이 가운데 보이실 겁니다. 바로 rb_entry죠? ㅎㅎㅎ 이 녀석은 저번 시간에 다뤘던 적이 있습니다. container_of(ptr, type, member) 라는 함수도 그 내용을 까보면 결국엔 list_entry(link, type, member)와 같은 넘입니다. 혹시 이 부분에 대한 이해가 없으시다면 직전 포스팅을 읽어보는 것을 추천드립니다.
#define rb_entry(ptr, type, member) container_of(ptr, type, member)
#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL)
#define RB_EMPTY_NODE(node) (rb_parent(node) == node)
#define RB_CLEAR_NODE(node) (rb_set_parent(node, node))
아래는 노드의 초기화 함수입니다. 한마디로 노드의 모든 값을 초기화 하고 있군요. rb->rb_parent_color의 값을 0으로 초기화한다는 것은 가르길 부모노드가 NULL이라는 것과 초기 노드의 컬러가 빨간색임을 의미합니다.
static inline void rb_init_node(struct rb_node *rb)
{
rb->rb_parent_color = 0;
rb->rb_right = NULL;
rb->rb_left = NULL;
RB_CLEAR_NODE(rb);
}
아래는 rb_insert_color와 rb_erase같은 함수들은 삽입과 삭제를 하는데 있어서 중요한 기능(rebalance)을 하고 있지만 외부 파일에 정의되어 있으므로 나중에 다시 나올 때 설명드리겠습니다. 다음으로 넘어가기 전에 typedef void (*rb_augment_f)(struct rb_node *node, void *data); 는 함수포인터를 typedef 지정자로 사용을 함수포인터의 사용을 간소화하기 위해 정의된 것입니다. 주로 바로 아래에 있는 rb_augment_insert 함수에서 매개변수로 던져지고 있다는 걸 알 수 있네요. 흠.. 오늘 다룰 기본적인 삽입, 삭제 함수와 무관하기에 일단은 패스하도록 하겠습니다~ 패스~
extern void rb_erase(struct rb_node *, struct rb_root *);
typedef void (*rb_augment_f)(struct rb_node *node, void *data);
extern void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data);
extern struct rb_node *rb_augment_erase_begin(struct rb_node *node);
extern void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data);
아래의 매크로들은 트리에서 노드를 찾기위한 여러가지 방법과 노드의 교환을 하는 기능을 가지는 함수를 설명하고 있습니다. 코드가 간단하기에 이 부분은 패스 하도록겠습니다. 패스~
/* Find logical next and previous nodes in a tree */
extern struct rb_node *rb_next(const struct rb_node *);
extern struct rb_node *rb_prev(const struct rb_node *);
extern struct rb_node *rb_first(const struct rb_root *);
extern struct rb_node *rb_last(const struct rb_root *);
/* Fast replacement of a single node without remove/rebalance/add/rebalance */
extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root);
두번 이상 패스했더니 이번에는 패스하면 안 될 것 같은 느낌이 드는군요. ㅎㅎ 도둑이 제발 저린다고 하죠.. ^^
그럼 지금부터는 다시 자세하게 분석해보겠습니다. 아래의 함수는 노드를 만들었을 때 가장 처음 호출되는 녀석입니다. 이 함수의 역할은 노드끼리의 연결을 시켜주는 것이죠. 그렇다면 여기서 말하는 노드는 무엇일까요? 여기서 말하는 노드는 아직 트리에 추가되지 않은 노드를 말합니다. rb_link_node(struct rb_node * node, struct rb_node * parent, struct rb_node ** rb_link) 함수를 보면 노드는 3개의 인자 중 첫번째 인자로 들어가게 되는 놈이죠. 두번째 인자는 그 노드의 부모가 될 노드이고, 세번째 인자 rb_link가 삽입할 노드의 루트 또는 아직 연결되지 않은 부모의 left, right 링크를 가지고 있는 녀석입니다. 코드를 보면 rb_parent_color에 부모의 노드를 가르키게 하고 다음 줄에는 노드의 왼쪽과 오른쪽 링크를 NULL로 초기화 하고 있음을 알 수 있습니다. 계속해서 아래 rb_link는 루트나 상위노드의 링크를 연결하는 놈인데 나중에 삽입함수를 설명하면서 그림으로 다시 설명드리겠습니다.
{
node->rb_parent_color = (unsigned long )parent;
node->rb_left = node->rb_right = NULL;
*rb_link = node;
}
아까전에도 말씀드렸던 것과 같이 리눅스 커널에는 삽입을 하는 함수가 없기에 직접 구현해줘야 합니다. 참 귀찮지만 Andrea라는 분이 그렇게 해라고 했었죠? 사실 아래 함수인 __rb_insert_page_cache(...)에서는 offset이라는 키값을 이용하여 삽입할 노드가 offset보다 크면 오른쪽에 삽입하고 작으면 왼쪽에 삽입하는 방식으로 구성되어 있습니다. 하지만 이것은 레드 블랙 트리 구현에 포함되어 질 수 없는 코드입니다. 이유는 리눅스에서 레드 블랙 트리 자료구조를 사용하는 부분은 다양하고 비교하는 알고리즘 자체도 하나가 아니라 수 가지가 될 수 있습니다. 때문에 그 목적에 따라 특정한 알고리즘이 포함되어 있는 삽입과 같은 부분은 사용자의 몫으로 남겨놓은 것이죠. 친절한(?) Andrea씨가 주석으로 제공한 아래의 삽입 코드를 먼저 보도록 하겠습니다.
static inline struct page * __rb_insert_page_cache(struct inode * inode, unsigned long offset, struct rb_node * node)
{
struct rb_node ** p = &inode->i_rb_page_cache.rb_node;
struct rb_node * parent = NULL;
struct page * page;
while (*p)
{
parent = *p;
page = rb_entry(parent, struct page, rb_page_cache);
if (offset< page->offset)
p = &(*p)->rb_left;
else if (offset > page->offset)
p = &(*p)->rb_right;
else
return page;
}
rb_link_node(node, parent, p);
return NULL;
}
static inline struct page * rb_insert_page_cache(struct inode * inode, unsigned long offset, struct rb_node * node)
{
struct page * ret;
if ((ret = __rb_insert_page_cache(inode, offset, node)))
goto out;
rb_insert_color(node, &inode->i_rb_page_cache);
out:
return ret;
}
삽입코드는 아래 그림과 같이 크게 세가지 동작으로 구분 할 수 있습니다.
① 오프셋을 비교하여 노드의 왼쪽, 오른쪽을 구분하는 부분
② 왼쪽 또는 오른쪽에 노드를 연결시키는 부분
③ 연결된 노드들을 레드 블랙 트리의 특성에 맞게 재구성하는 부분
이렇게 세가지 동작으로 구분할 수 있으며, 자세한 동작은 아래 그림과 같습니다. 참고로 그림에서 root는 inode를 말하는 것으로 이해를 돕기 위해 root로 표기하였습니다.
ⓐ inode(root)가 구성되어 있지 않고 가장 처음 삽입 함수가 수행되는 것 부터 보시겠습니다. 삽입할 노드는 offset 값이 2인 노드 입니다. 일단 root는 아무 값도 없기에 0(NULL)이며, 삽입함수의 마지막 매개변수값으로 들어온 structrb_node* node는 삽입할 뉴노드입니다. page 구조체 안에 ?로 채워져 있는 부분은 아직 초기화되지 않은 부분이라 생각하시면 됩니다. 그리고 여기서 p와 node는 struct rb_node의 시작주소를 임시로 저장하고 있습니다. 지금까지 말한 과정이 삽입 함수의 세가지 동작중 첫 번째 단계에 대한 설명입니다.
struct rb_node ** p = &inode->i_rb_page_cache.rb_node;
struct rb_node * parent = NULL;
struct page * page;
ⓑ 노드를 처음으로 삽입하기에 *p 포인터 변수가 비었으므로 아래 whlile 루프는 수행하지 않고 패스하게 됩니다. 그리고 rb_link_node가 수행됩니다. 이 함수의 수행을 통해 parent_color, left, right가 모두 '0'으로 초기화 됩니다. parent_color를 '0'으로 초기화 시킨다함은 가르키는 부모노드가 없고 이 노드의 색상을 빨간색으로 초기화하겠다는 의미입니다. rb_link_node의 수행이 끝나고 균형을 맞추기 위한 rb_insert_color가 수행되지만 아직 균형을 맞출 노드가 없기에 그냥 패스합니다.
while (*p)
{ parent = *p;
page = rb_entry(parent, struct page, rb_page_cache);
if (offset< page->offset)
p = &(*p)->rb_left;
else if (offset > page->offset)
p = &(*p)->rb_right;
else
return page;
}
rb_link_node(node, parent, p);
rb_insert_color(node, &inode->i_rb_page_cache);
ⓒ 그럼 두번째 노드를 삽입해 보도록 하겠습니다. 이번에는 offset 값이 1인 노드를 삽입시켜 보겠습니다. 아래 코드를 거쳐 그림과 같이 구성되는 것을 확인할 수 있습니다.
struct rb_node ** p = &inode->i_rb_page_cache.rb_node;
struct rb_node * parent = NULL;
struct page * page;
ⓓ 아까 한번의 삽입과정을 통해 *p가 비어있지 않으므로 while루프를 수행하게 됩니다. 포인터 변수 parent는 포인터 변수 p와 같이 노드 안에 있는 struct rb_node의 시작지점을 가르킵니다. rb_entry는 struct rb_node의 시작지점을 가르키는 parent를 이용하여 page구조체의 시작주소를 얻어냅니다. 이것은 offset값에 접근하려고 하는거 아시겠죠? 그리고 얻어낸 offset을 이용하여 기존에 있던 노드의 왼쪽 또는 오른쪽에 삽입할지를 결정합니다. 결정되면 포인터 변수 p에 p의 왼쪽 링크와 오른쪽 링크 주소를 저장하게 하는데 이것은 나중에 rb_link_node 함수 수행을 통해 새로 삽입될 노드의 위치를 지정하기 위한 것 입니다. 즉 트리를 순환하기 위한 변수죠. 루프를 한바퀴 돌고나면 두번째 돌때는 (*p)->left가 '0'이므로 루프를 탈출하게 됩니다. 하지만 아직까지는 새로 삽입할 노드가 연결되지 않았습니다.
while (*p)
{
parent = *p;
page = rb_entry(parent, struct page, rb_page_cache);
if (offset< page->offset)
p = &(*p)->rb_left;
else if (offset > page->offset)
p = &(*p)->rb_right;
else
return page;
}
ⓔ 계속해서 아래 두 함수를 수행하게 되는데 rb_link_node함수를 통해서 아래와 같은 트리를 구성할 수 있습니다. 드디어 old 노드와 new 노드가 연결된 것을 확인 할 수 있습니다.
rb_link_node(node, parent, p);
rb_insert_color(node, &inode->i_rb_page_cache);
ⓕ 자~ 노드가 두개밖에 안되지만 그래도 완성된 트리입니다.^^ 오른쪽에 삽입하는 것도 비슷하므로 설명은 생략하도록 하겠습니다.. 사실은 그리기가 빡셨습니다 ㅎㅎㅎ
지금까지 삽입함수를 설명드렸는데 이해가 잘 가셨나요? 저는 설명하면서도 이게 과연 잘 전달이 될지 의문이 들더군요. 혹시 이해가 안가시는 부분이라던가 새로 설명을 원하시는 분은 답글을 달아주시면 친절히 수정하도록 하겠습니다.
마지막으로 아래의 코드가 레드 블랙 트리의 균형을 맞추는 함수 입니다. 벨런스에 맞게 트리를 재구성하는 함수인데, 자세히 보면 아까 예제를 통해서 봤던 개념들이 그대로 들어가 있습니다. 주석만 보셔서 금방 이해가 가실 듯 합니다.^^
void rb_insert_color(struct rb_node *node, struct rb_root *root)
{
struct rb_node *parent, *gparent;
// 부모 노드와 새로 삽입될 노드가 빨강이면 루프를 수행(4번 규칙을 위반함!)
while ((parent = rb_parent(node)) && rb_is_red(parent))
{
gparent = rb_parent(parent);
if (parent == gparent->rb_left) // 부모 노드가 할아버지 노드의 왼쪽자식일 경우
{
{
register struct rb_node *uncle = gparent->rb_right;
if (uncle && rb_is_red(uncle)) // 삼촌이 빨간색인 경우
{
rb_set_black(uncle);
rb_set_black(parent);
rb_set_red(gparent);
node = gparent;
continue;
}
}
// 삼촌이 검정색인 경우
if (parent->rb_right == node) // 삼촌이 검정색이면서 오른쪽 자식일때
{
register struct rb_node *tmp;
__rb_rotate_left(parent, root);
tmp = parent;
parent = node;
node = tmp;
}
rb_set_black(parent);
rb_set_red(gparent);
__rb_rotate_right(gparent, root);
} else { // 부모 노드가 할아버지 노드의 오른쪽 자식일 경우
{
register struct rb_node *uncle = gparent->rb_left;
if (uncle && rb_is_red(uncle)) // 삼촌이 빨간색인 경우
{
rb_set_black(uncle);
rb_set_black(parent);
rb_set_red(gparent);
node = gparent;
continue;
}
}
if (parent->rb_left == node) // 삼촌이 검정색이면서 왼쪽 자식일때
{
register struct rb_node *tmp;
__rb_rotate_right(parent, root);
tmp = parent;
parent = node;
node = tmp;
}
rb_set_black(parent);
rb_set_red(gparent);
__rb_rotate_left(gparent, root);
}
}
rb_set_black(root->rb_node); // 루트 노드는 반드시 검은색이어야 한다.
}
'프로그래밍 > C' 카테고리의 다른 글
| scanf 의 입력개념 (0) | 2013.04.20 |
|---|---|
| Stack 과 heap (메모리구조) (0) | 2013.04.19 |
| Visual studio가 잊어버리게 하는 개념(compile with gcc) (0) | 2013.04.19 |
| Vi 편집기 setting (0) | 2013.04.19 |
| linux kernel에서 쓰이는 자료구조.(double linked list and tree) (0) | 2013.04.19 |
