Red-Black Tree 개선된 구조

Red-Black Tree – 삽입 글에서 설명한 것 처럼, RB tree에서 사용하는 구조체의 그림과 코드는 다음과 같다.

struct rb_node                                                                                                                              
{
        struct rb_node * rb_parent;
        int rb_color;
#define RB_RED          0
#define RB_BLACK        1
        struct rb_node * rb_right;
        struct rb_node * rb_left;
};

위 그림에서 rb_color는 단순하게 color값을 나타내는 값인데, 4 bytes를 가지는 int 타입이다. 따라서 parent의 주소값을 가지는 rb_parent의 하위 1bit를 color 값으로 사용한다.

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

만약 color 값이 1이 될 때, parent의 주소값에 영향을 미칠 수 있기 때문에, attribute((aligned(sizeof(long)))) 를 통해 long 타입에 맞는 address alignment 맞추게 된다.