rb 트리

부모가 빨강일 때, 새로운 자식노드가 빨강이면 다음과 같은 상황이다.

1) 삼촌이 없고, 새노드가 부모의 왼쪽 자식인 경우

2) 삼촌이 없고, 새노드가 부모의 오른쪽 자식인 경우

3) 삼촌이 있고, 삼촌 빨간색일 경우

4) 삼촌이 있고, 삼촌이 검은색이며, 새노드가 부모의 왼쪽 자식인 경우

5) 삼촌이 있고, 삼촌이 검은색이며, 새노드가 부모의 오른쪽 자식인 경우

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))));

엄청난 자료구조!!

__attribute__((aligned(sizeof(long)))); 4byte로 정렬

이제 이 구조체의 시작주소는 0,4,8,... 4의 배수일 것이다.

unsigned long rb_parent_color;

부모의 시작주소를 가짐과 동시에, 자신의 색상을 표시한다.

rb_parent_and_color라고 했으면 더 직관적이었을텐데...

왜? 가능한가?

부모 구조체는 어차피 4의 배수로 정렬되어 있다.

그러므로, 하위 2비트는 00으로 고정되어 있다. 이 하위 2비트를 RED, BLACK으로 사용하겠다는 것이다.

따라서 다음과 같이 함수를 작성할 수 있다.

set_parent(struct rb_node *node, struct rb_node *p)

{

node->rb_parent_color = (node->rb_parent_color & 3) | (unsigned long) p;

}