C 언어 구현 레 드 블랙 트 리

           ，       ，    2lg(n+1)。

 붉 은 검 은 나 무 는 다음 조건 을 충족 시 키 는 이 진 트 리 입 니 다.
4. 567917. 각 노드 또는 빨간색 또는 검은색..
4. 567917. 뿌리 노드 는 검은색 이다
4. 567917. 잎 노드 는 검은색 이다
4. 567917. 한 노드 가 빨간색 이 라면 두 아 이 는 검은색 이다
4. 567917. 모든 노드 에 대해 이 노드 (이 노드 를 포함 하지 않 음) 부터 모든 후대 잎 노드 의 간단 한 경로 까지 똑 같은 수량의 검은색 노드 를 포함한다
이 방안 은 보초병 Nil 을 사용 하여 모든 NULL 을 대표 합 니 다. 뿌리 노드 는 T 이 고 뿌리 노드 의 부모 노드 는 Nil 이 며 모든 잎 노드 는 Nil 입 니 다.
붉 은 검 은 나무의 한 노드 는 다음 과 같은 속성 을 포함 합 니 다.

typedef struct NODE
{
	struct NODE      *left;  //    
	struct NODE      *right; //    
	struct NODE      *p;     //    
	TREE_TYPE        value;  //  
	COLOUR           colour; //   
} Tree, Node;

이 프로그램 을 쓰 는 과정 에서 많은 문제점 을 발 견 했 고 버그 의 고통 을 겪 었 습 니 다. 제 가 기억 할 수 있 기 를 바 랍 니 다.
1. 함 수 를 정의 한다 면

Node *Left(Node *x)
{
	return x->left;
}

그럼 이렇게 호출 해도 될까요?（C89）
답 은 안 됩 니 다.
만약 파일 이. cpp 로 저 장 된 것 이 가능 하 다 면, C + + 는 이러한 쓰 기 를 지원 합 니 다.
우 리 는 Left (Left (node) 를 끼 워 넣 을 수 있 습 니 다. 왼쪽 값 으로 할 수 없습니다.2. C89 에서 모든 변 수 는 구문 블록 맨 앞 에 정의 되 어야 한다. 그렇지 않 으 면 오 류 를 보고 할 수 있다. 그 전에 사 용 했 던 경량급 Dev C + 개발 환경 컴 파일 러 GCC 4.8.1 은 좀 더 시원 하 게 쓰 여 있 지만 디 버 거 는 너무 간단 하고 VS 디 버 거 는 매우 강력 하 다. 이 는 프로그램의 구 조 를 이해 하 는 데 유리 하 다.비록 그것 의 오래된 문법 은 그다지 인성 적 이지 않 지만.뭐 공부 해요?
KEIL 4 로 끼 워 넣 는 프로그램 을 쓸 때. 예 를 들 어 int config lcd (); 이러한 성명 은 경고 가 있 을 것 입 니 다. 이것 은 더욱 엄격 합 니 다.
int config lcd (void) 는 경고 하지 않 았 습 니 다. int main () {}, void main () {} 은 안 됩 니 다. int main (void) 이 표준 입 니 다.
3. 가끔 이렇게 쓴다 
GCC 는 통과 할 수 있 지만 약간 급진 적 이다.
      물론 이런 것들 은 많은 책 에서 말 할 수 있 지만, 이 일 을 몸소 해 야 자신 이 이런 문제 에 부 딪 혀 야 더욱 깊이 이해 할 수 있다 는 것 을 절대 알 고 있다.
다음은 빨 간 검 은 나무의 코드 입 니 다.
red black tree. h 파일

Left( node )->left = Nil;

red black tree. c 파일

void counting_sort(char *source , char * des, int k )
{
    char c[k];
    .....  ....
}

테스트 코드 main. c
4. 567913. 디 버 깅 상태 에서 우 리 는 빨 간 검 은 나무의 구 조 를 볼 수 있다.
1 ~ 9 붉 은 검 은 나무 한 그루 삽입
                     4b
                   /     \
               2r         6r
            /    \       /     \          1b   3b    5b     8b
                               /     \
                             7r       9r
검 붉 은 나무의 성질 에 맞다.
기타 함수 도 기능 을 실현 하 였 다.