리 눅 스 커 널 의 레 드 블랙 트 리 알고리즘 구현 에 대한 상세 한 설명

프로필
밸 런 스 이 진 트 리(Balanced Binary Tree 또는 Height-Balanced Tree)
AVL 트 리 라 고도 합 니 다.그것 은 빈 나무 나 다음 과 같은 성질 을 가 진 이 진 트 리 입 니 다.왼쪽 나무 와 오른쪽 나 무 는 모두 균형 이 잡 힌 이 진 트 리 이 고 왼쪽 나무 와 오른쪽 나무의 깊이 차 이 는 절대 1 을 초과 하지 않 습 니 다.이 진 트 리 에 있 는 노드 의 균형 인자 BF(Balance Factor)를 이 노드 의 왼쪽 트 리 깊이 에서 오른쪽 트 리 의 깊이 를 빼 면 균형 이 진 트 리 에 있 는 모든 노드 의 균형 인 자 는-1,0,1 일 수 있 습 니 다.(이 단락 은 엄 울 민의 데이터 구조(C 언어 판)에서 정의 합 니 다.
검 붉 은 나무
R-B Tree 는 모두 Red-Black Tree 라 고도 부 르 며'붉 은 검 은 나무'라 고도 부 르 는데 특수 한 이 진 트 리 입 니 다.빨간색 과 검은색 나무의 모든 노드 에 노드 의 색 을 나타 내 는 저장 위치 가 있 는데 빨간색(빨간색)이나 검은색(Black)일 수 있다.
빨간색 과 검은색 나 무 는 노드 를 삽입 하거나 삭제 할 때 균형 을 유지 해 야 하 는 이 진 트 리 이 고 모든 노드 는 색상 속성 을 가지 고 있 습 니 다.
(1)결점 하나 가 빨간색 이거 나 검은색 이다.
(2)뿌리 결산 점 은 검은색 입 니 다.
(3)만약 에 하나의 결점 이 빨간색 이 라면 그의 자 결점 은 반드시 검은색 이 어야 한다.즉,뿌리 결점 에서 출발 하 는 어떠한 경 로 를 따라 도 두 개의 연속 적 인 빨간색 결점 이 나타 나 지 않 는 다 는 것 이다.
(4)하나의 노드 에서 하나의 NULL 포인터 까지 의 모든 경로 에 같은 수량의 검은색 노드 가 포함 되 어야 합 니 다.
 
Linux 커 널 레 드 블랙 트 리 의 알고리즘 은 모두 Liux-2.6.38.8/include/linux/rbtree.h 와 Liux-2.6.38.8/lib/rbtree.c 두 파일 에 정의 되 어 있 습 니 다.
구조 체

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

이곳 의 교묘 한 점 은 구성원rb_parent_color을 사용 하여 두 가지 데 이 터 를 동시에 저장 하 는 것 이다.하 나 는 부모 노드 의 주소 이 고 다른 하 나 는 이 노드 의 착색 이다.  __attribute__((aligned(sizeof(long))))속성 은 빨 간 검 은 나무 에 있 는 모든 노드 의 첫 번 째 주 소 는 32 비트 정렬(32 비트 기기 에서)을 보장 한다.즉,모든 노드 의 첫 번 째 주소bit[1]와bit[0]가 0 이기 때문에 bit[0]를 사용 하여 노드 의 색상 속성 을 저장 하고 부모 노드 의 첫 번 째 주소 의 저장 에 방해 가 되 지 않 는 다 는 것 이다.
조작rb_parent_color의 함수:

#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; 
} 

새 노드 초기 화:

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;  //           (         NULL),          
  node->rb_left = node->rb_right = NULL;  //            
 
  *rb_link = node; //      
} 

검 붉 은 나무 뿌리 에 맺 힌 점 을 가리 키 는 지침:

struct rb_root 
{ 
  struct rb_node *rb_node; 
}; 
 
 
#define RB_ROOT (struct rb_root) { NULL, } //               
#define rb_entry(ptr, type, member) container_of(ptr, type, member) //      struct rb_node         
 
#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL) //        
#define RB_EMPTY_NODE(node) (rb_parent(node) == node) //  node           
#define RB_CLEAR_NODE(node) (rb_set_parent(node, node)) //          

삽입
먼저 두 갈래 로 나 무 를 찾 는 것 처럼 새로운 결점 을 삽입 한 다음 에 상황 에 따라 상응하는 조정 을 해서 붉 은 검 은 나무의 색깔 속성 을 만족 시 키 도록 한다(실질 은 붉 은 검 은 나무의 균형 을 유지 하 는 것 이다).
함수rb_insert_color는 while 순환 을 사용 하여 부모 노드 가 존재 하 는 지 여 부 를 계속 판단 하고 색상 속성 은 빨간색 입 니 다.
판단 조건 이 진실 이 라면 두 부분 으로 나 누 어 후속 작업 을 수행 합 니 다.
    （1)부모 의 결산 점 이 할아버지 가 왼쪽 나무의 뿌리 를 맺 었 을 때:
           a.숙부 결점 이 존재 하고 색상 속성 은 빨간색 입 니 다.
 
           b.node 가 부모 가 오른쪽 나무 뿌리 를 맺 었 을 때 좌회전 한 다음 에 c 단 계 를 수행 합 니 다.
 
            c.node 가 부모 가 왼쪽 나무의 뿌리 를 맺 었 을 때.
 
    （2)부모 의 결점 이 할아버지 가 오른쪽 자수의 뿌리 를 맺 었 을 때의 조작 은 제(1)단계 와 대체적으로 같 아서 여 기 는 생략 합 니 다.
         가짜 라면 루트 노드 의 색상 속성 을 검은색 으로 설정 합 니 다.

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)) //      NULL，         
  { 
    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; //node        
          continue; //     while   
        } 
      } 
 
      if (parent->rb_right == node) // node             
      { 
        register struct rb_node *tmp; 
        __rb_rotate_left(parent, root); //   
        tmp = parent; //  parent node      
        parent = node; 
        node = tmp; 
      } 
 
      rb_set_black(parent); //          
      rb_set_red(gparent); //          
      __rb_rotate_right(gparent, root); //   
    } else { // !(parent == gparent->rb_left) 
      { 
        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); 
    } //end if (parent == gparent->rb_left) 
  } //end while ((parent = rb_parent(node)) && rb_is_red(parent)) 
 
  rb_set_black(root->rb_node); 
} 

삭제
이 진 트 리 의 삭제 작업 을 찾 는 것 처럼 먼저 삭제 해 야 할 결점 을 찾 은 다음 이 결점 에 따라 좌우 하위 트 리 의 유 무 에 따라 세 가지 상황 으로 나 눌 수 있 습 니 다.
 node결점 의 색상 속성 이 검은색 이면__rb_erase_color함수 로 조정 해 야 합 니 다.

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; 
  } //end else 
 
  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        
    __rb_erase_color(child, parent, root); 
} 

두루rb_first와rb_next함 수 는 중간 순 서 를 구성 할 수 있 습 니 다.즉,빨 간 검 은 나무 에 있 는 모든 결점 을 오름차 로 옮 길 수 있 습 니 다.

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

6.응용 프로그램 에서 사용
리 눅 스 커 널 에 있 는 레 드 블랙 트 리 알고리즘 의 실현 은 매우 통용 되 고 교묘 하 며 무료 로 오픈 소스 이기 때문에 자신의 응용 프로그램 에 충분히 활용 할 수 있다.
    （1)커 널 에서 원본 파일 복사:

$ mkdir redblack 
$ cd redblack/ 
$ cp ../linux-2.6.38.8/lib/rbtree.c . 
$ cp ../linux-2.6.38.8/include/linux/rbtree.h . 

    （2)원본 파일 수정:
          a,C 파일 rbtree.c
            헤더 파일 을 포함 하 는 코드 수정

//         
#include <linux/rbtree.h> 
#include <linux/module.h> 
//      ，            rbtree.h 
#include "rbtree.h" 

           모든 EXPORT 삭제SYMBOL 매크로

EXPORT_SYMBOL(rb_insert_color); 
EXPORT_SYMBOL(rb_erase); 
EXPORT_SYMBOL(rb_augment_insert); 
EXPORT_SYMBOL(rb_augment_erase_begin); 
EXPORT_SYMBOL(rb_augment_erase_end); 
EXPORT_SYMBOL(rb_first); 
EXPORT_SYMBOL(rb_last); 
EXPORT_SYMBOL(rb_next); 
EXPORT_SYMBOL(rb_prev); 
EXPORT_SYMBOL(rb_replace_node); 

          b.헤더 파일 rbtree.h
             헤더 파일 을 포함 하 는 코드 를 삭제 하고 세 개의 매크로 정 의 를 추가 합 니 다.

//         
#include <linux/kernel.h> 
#include <linux/stddef.h> 
 
/* linux-2.6.38.8/include/linux/stddef.h */ 
#undef NULL 
#if defined(__cplusplus) 
#define NULL 0 
#else 
#define NULL ((void *)0) 
#endif 
 
/* linux-2.6.38.8/include/linux/stddef.h */ 
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) 
 
/* linux-2.6.38.8/include/linux/kernel.h */ 
#define container_of(ptr, type, member) ({     \ 
  const typeof( ((type *)0)->member ) *__mptr = (ptr); \ 
  (type *)( (char *)__mptr - offsetof(type,member) );}) 

    （3)예시 코드
    Linux 커 널 레 드 블랙 트 리 의 사용 방법 은 linux-2.6.38.8/Documentation/rbtree.txt 파일 을 참고 하 십시오.

/* test.c */ 
#include <stdio.h> 
#include <stdlib.h> 
#include "rbtree.h" 
 
struct mytype { 
  struct rb_node my_node; 
  int num; 
}; 
 
struct mytype *my_search(struct rb_root *root, int num) 
{ 
  struct rb_node *node = root->rb_node; 
 
  while (node) { 
  struct mytype *data = container_of(node, struct mytype, my_node); 
 
  if (num < data->num) 
    node = node->rb_left; 
  else if (num > data->num) 
    node = node->rb_right; 
  else 
    return data; 
  } 
   
  return NULL; 
} 
 
int my_insert(struct rb_root *root, struct mytype *data) 
{ 
  struct rb_node **tmp = &(root->rb_node), *parent = NULL; 
 
  /* Figure out where to put new node */ 
  while (*tmp) { 
  struct mytype *this = container_of(*tmp, struct mytype, my_node); 
 
  parent = *tmp; 
  if (data->num < this->num) 
    tmp = &((*tmp)->rb_left); 
  else if (data->num > this->num) 
    tmp = &((*tmp)->rb_right); 
  else  
    return -1; 
  } 
   
  /* Add new node and rebalance tree. */ 
  rb_link_node(&data->my_node, parent, tmp); 
  rb_insert_color(&data->my_node, root); 
   
  return 0; 
} 
 
void my_delete(struct rb_root *root, int num) 
{ 
  struct mytype *data = my_search(root, num); 
  if (!data) {  
  fprintf(stderr, "Not found %d.
", num); 
  return; 
  } 
   
  rb_erase(&data->my_node, root); 
  free(data); 
} 
 
void print_rbtree(struct rb_root *tree) 
{ 
  struct rb_node *node; 
   
  for (node = rb_first(tree); node; node = rb_next(node)) 
  printf("%d ", rb_entry(node, struct mytype, my_node)->num); 
   
  printf("
"); 
} 
 
int main(int argc, char *argv[]) 
{ 
  struct rb_root mytree = RB_ROOT; 
  int i, ret, num; 
  struct mytype *tmp; 
 
  if (argc < 2) { 
  fprintf(stderr, "Usage: %s num
", argv[0]); 
  exit(-1); 
  } 
 
  num = atoi(argv[1]); 
 
  printf("Please enter %d integers:
", num); 
  for (i = 0; i < num; i++) { 
  tmp = malloc(sizeof(struct mytype)); 
  if (!tmp) 
    perror("Allocate dynamic memory"); 
 
  scanf("%d", &tmp->num); 
   
  ret = my_insert(&mytree, tmp); 
  if (ret < 0) { 
    fprintf(stderr, "The %d already exists.
", tmp->num); 
    free(tmp); 
  } 
  } 
 
  printf("
the first test
"); 
  print_rbtree(&mytree); 
 
  my_delete(&mytree, 21); 
 
  printf("
the second test
"); 
  print_rbtree(&mytree); 
 
  return 0; 
} 

컴 파일 및 실행:

$ gcc rbtree.c test.c -o test 
richard@tanglinux:~/algorithm/redblack$ ./test 10 
Please enter 10 integers: 
23 
4 
56 
32 
89 
122 
12 
21 
45 
23 
The 23 already exists. 
 
the first test 
4 12 21 23 32 45 56 89 122  
 
the second test 
4 12 23 32 45 56 89 122  

7.총화
이상 은 리 눅 스 커 널 에서 레 드 블랙 트 리 알고리즘 이 실 현 된 모든 내용 입 니 다.글 은 상세 하 게 소개 되 어 있 습 니 다.여러분 의 업무 와 학습 에 도움 이 되 기 를 바 랍 니 다.궁금 한 점 이 있 으 면 메 시 지 를 남 겨 주 십시오.