붉 은 검 은 나무의 사용 에 대한 상세 한 설명
우선 붉 은 검 은 나무의 성질 이다.두 갈래 로 나 무 를 찾 아 아래 의 붉 고 검 은 성질 을 만족 시 키 면 붉 은 검 은 나무 이다.
1)각 결점 이나 빨간색,검은색.
2)뿌리 결점 은 검다.
3)각 잎의 결점(NIL)은 검다.
4)붉 은 점 의 두 아 이 는 모두 검다.
5)임의의 결점 에 대해 서 는 자손 결점 까지 모든 경로 에 같은 수의 검 은 결점 을 포함한다.
초학 때 는 개의 치 않 았 지만 관련 알고리즘 을 자세히 연구 해 보면 알고리즘 은 모두 이러한 성질 을 유지 하 는 것 을 중심 으로 진행 되 었 다 는 것 을 알 수 있다.성질 5)붉 은 검 은 나 무 를 사용 할 때의 효율 을 확보한다.정 리 는 n 개 내 결점 의 붉 은 검 은 나무의 높이 가 기껏해야 2lg(n+1)임 을 증명 했다.
일반적인 두 갈래 로 나 무 를 찾 는 것 과 달리 붉 은 검 은 나 무 는 보통 보초병 노드 를 사용 하여 NIL 을 대표 합 니 다.이 알고리즘 은 사용 하기에 많은 편 의 를 제공 합 니 다.구체 적 으로 작성 할 때 느 낄 수 있 습 니 다.보초병 은 검은색 으로 설치 되 어 있 으 며,뿌리의 부 결점 이자 모든 잎 결점 이다.다른 도 메 인 은 임의의 값 으로 설정 할 수 있 습 니 다.나 는 키워드 로 그것 과 일반적인 결점 을 구분 했다.
회전 은 붉 은 검 은 나무의 특유 한 조작 이다.예전 에는 좌선 과 우회전 이 어떻게 진행 되 었 는 지 잘 몰 랐 는데 지금 은 잘 알 고 있 습 니 다.이렇게 요약 할 수 있 습 니 다.x 결점 좌선 즉,x 를 한 그루 의 나무의 뿌리 에서 이 나무의 왼쪽 아이 로 만 드 는 것 입 니 다.대칭 적회전 은 빨 간 검 은 나무 가 삽입 되 고 삭 제 될 때 빨 간 검 은 성질 을 유지 하기 위해 가능 한 작업 입 니 다.
삽입 의 원리:
빈 포인터 처 리 를 제외 하고 삽입 하 는 과정 은 이 진 트 리 와 같 지만 삽입 후 에는 빨간색 과 검은색 의 성질 을 확보 하기 위해 독특한 조정 알고리즘 이 필요 합 니 다.아래 의 설명 은 제 개인 적 인 요약 입 니 다.혼 란 스 러 워 보이 고 알고리즘 과 사례 가 상대 적 으로 이해 하기 쉬 울 것 입 니 다.
새로 삽 입 된 점 z 는 빨간색 으로 직접 염색 한 다음 에 아버지 결점 이 빨간색 인지(성질 4 와 충돌)와 삽 입 된 결점 이 뿌리 인지(성질 2 와 충돌)에 따라 조정 합 니 다.후 자 는 직접 뿌리 를 검 게 물 들 이면 된다.
전자 에 대해 z 의 삼촌 y(삼촌 y 를 찾 으 려 면 상황 에 따라 처리 해 야 하지만 비교적 간단 하고 상세 하 게 쓰 지 않 는 다)를 찾 아 y 가 빨간색 인지 검은색 인지 에 따라 상황 을 더욱 분명하게 구분 한다.z 의 아버지 가 왼쪽 아이 일 때 전 자 는 z 의 아버지 와 삼촌 을 동시에 검 게 만 들 고 z 의 아버지 결점 의 아버지 결점 을 붉 게 만 들 며 z 가 z 의 아버지 결점 을 가리 키 는 아버지 결점 을 교체 처리 하면 된다.후 자 는 z 가 왼쪽 아이 인지 오른쪽 아이 인지 나 누 어 처리한다.z 는 왼쪽 아이 일 때 z 의 아버지 결점 으로 직접 회전 시 켜 z 의 아버 지 를 좌회전 시 키 고 새로운 z 가 되 는 것 이 바로 뒤의 상황 이다.뒤의 상황 에서 z 의 아버 지 를 검 게 물 들 이 고 할 아버 지 는 붉 게 물 들 이 며 z 의 할아버지 가 우회전 하면 얻 을 수 있다.
삭제 의 원리:
알고리즘 서론 에서 의 삭제 알고리즘 은 두 가지 상황 을 동시에 처리 하 는 것 이 확실히 기교 가 있다.붉 은 검 은 나무의 삭 제 는 마지막 으로 결점 을 삭제 하 는 색상 에 따라 조정 이 필요 한 지 여 부 를 판단 해 야 하 는 것 을 제외 하고 일반적인 이 진 트 리 와 다 르 지 않 으 므 로 여기 서 조금 분석 해 보 자.
RB-DELETE(T, z) // 1 || 2
if left[z] = nil[T] or right[z] = nil[T] // z || z
then y ← z // y=z || y z ( y z )
else y ← TREE-SUCCESSOR(z) //===============================================================================
if left[y] ≠ nil[T] // x y || x y (x ， y z )
then x ← left[y] // || x y
else x ← right[y] //================================================================================
p[x] ← p[y] //
if p[y] = nil[T] //
then root[T] ← x // x x
else if y = left[p[y]] //
then left[p[y]] ← x //
else right[p[y]] ← x //=================================================================================
if y !≠ z // ||
then key[z] ← key[y] // || ，
copy y's satellite data into z // ||
if color[y] = BLACK // ||
then RB-DELETE-FIXUP(T, x) // ||
return y
w 로 x 의 형 제 를 표시 하 다.
상황 1 은 w 홍 이다.이때 w 를 검은색 으로 조정 하고 p[x]를 빨간색 으로 하 며 p[x]로 좌회전 하고 w 는 x 의 새로운 형 제 를 가리 키 며 이때 상황 2 또는 3 또는 4 가 된다.
상황 2 는 w 흑 이 고 w 의 두 아 이 는 모두 어둡다.이때 w 를 빨간색 으로 염색 하여 p[x]를 새로운 x 로 만 듭 니 다.이것 은 x 를 검은색 에서 벗 겨 이 검은색 을 위로 옮 기 는 것 과 같다.
상황 3 은 w 검은색,w 의 왼쪽 아 이 는 빨간색,오른쪽 아 이 는 검은색 이다.이때 w 와 왼쪽 아이의 색깔 을 교환 하고 w 를 우회전 하면 상황 이 된다.
상황 4 는 w 흑,w 는 아이 가 있 으 면 빨간색 이다.이때 w 를 p[x]의 색 으로 만 들 고 p[x]는 검은색 으로,w 의 오른쪽 아 이 는 검은색 으로,p[x]를 왼쪽으로 돌 립 니 다.x 를 뿌리 로 하 다.이 때 는 원래 x 의 검은색 을 아버지 에 게 전달 하고 함께 아래로 이동 하 는 것 과 같 으 며 w 는 아버지의 원래 색깔 과 위 치 를 대체 하 는 것 과 같다.이것 은 붉 은 점 이나 이중 검 은 점 이 존재 하지 않 는 다.
매번 처리 할 때마다 x 가 뿌리 이 고 x 가 검은색 인지 아 닌 지 를 판단 합 니 다.x.뿌리 가 아니 라 검은색 일 때 만 빨간색 과 검은색 의 결점 이나 이중 검은색 의 결점 이 있 음 을 나타 내 고 새로운 순환 이 필요 합 니 다.순환 이 끝 난 후 뿌리 를 검 게 물 들 이면 끝난다.
마지막 으로 제 가 C 로 쓴 빨 간 검 은 나무 조작 을 동봉 합 니 다.삽입 작업 검증 이 잘못 되 지 않 았 습 니 다.삭제 작업 검증 횟수 가 제한 되 어 bug 가 존재 할 수 있 습 니 다.
#include <stdlib.h>
#include <stdio.h>
#define T_nil -1
//T_nil is a key of nil[T] in the book.
#define RED 1
#define BLACK 0//T_nil is BLACK
//T_nil's p is itself. need to set.
struct rb_tree {
int color;
int key; //normally a positive number.
struct rb_tree *left;
struct rb_tree *right;
struct rb_tree *p;
};
int rb_walk(struct rb_tree *node) {
if (node->key != T_nil) {
rb_walk(node->left);
printf("%d, color is %s
",node->key,(node->color?"RED":"BLACK"));
rb_walk(node->right);
}
return 1;
}
struct rb_tree* rb_search(struct rb_tree *node, int k) {
if ((node->key == T_nil) || (node->key == k))
return node;
if ( k < node->key )
return rb_search(node->left,k);
else
return rb_search(node->right,k);
}
struct rb_tree* tree_minimum(struct rb_tree *node) {
if (node->key == T_nil)
return node;
while (node->left->key != T_nil)
node = node->left;
return node;
}
struct rb_tree* tree_maximum(struct rb_tree *node) {
if (node->key == T_nil)
return node;
while (node->right->key != T_nil)
node = node->right;
return node;
}
struct rb_tree* tree_successor(struct rb_tree *node) {
struct rb_tree *y;
if (node->right->key != T_nil)
return tree_minimum(node->right);
y = node->p;
while ((y->key != T_nil) && (node == y->right)) {
node = y;
y = y->p;
}
return y;
}
//3 function of below is copy from tree.
struct rb_tree * left_rotate(struct rb_tree *rb, struct rb_tree *x) {
struct rb_tree *y;
//if (x->right->key == T_nil) {
// printf("have no right child,rotation cancel.
");
// return rb;
//}
y = x->right;
x->right = y->left;
if (y->left->key != T_nil)
y->left->p = x;
y->p = x->p;
if (x->p->key == T_nil)
rb = y;
else if (x == x->p->left)
x->p->left = y;
else
x->p->right = y;
y->left = x;
x->p = y;
return rb;
}
struct rb_tree *right_rotate(struct rb_tree *rb, struct rb_tree *x) {
struct rb_tree *y;
//if (x->left->key == T_nil ) {
// printf("have no left child,rotation cancel.
");
// return rb;
//}
y = x->left;
x->left = y->right;
if (y->right->key != T_nil )
y->right->p = x;
y->p = x->p;
if (x->p->key == T_nil)
rb = y;
else if (x == x->p->left)
x->p->left = y;
else
x->p->right = y;
y->right = x;
x->p = y;
return rb;
}
struct rb_tree* rb_insert_fixup(struct rb_tree *rb, struct rb_tree *z) {
struct rb_tree *y;
while (z->p->color == RED) {
if (z->p == z->p->p->left) {
y = z->p->p->right;
if (y->color == RED) {
z->p->color = BLACK;
y->color = BLACK;
z->p->p->color = RED;
z = z->p->p;
}
else {
if (z == z->p->right) {
z= z->p;
rb = left_rotate(rb,z);
}
z->p->color = BLACK;
z->p->p->color = RED;
rb = right_rotate(rb,z->p->p);
}
}
else {//same as right and left exchanged
y = z->p->p->left;
if (y->color == RED) {
z->p->color = BLACK;
y->color = BLACK;
z->p->p->color = RED;
z = z->p->p;
}
else {
if (z == z->p->left) {
z= z->p;
rb = right_rotate(rb,z);
}
z->p->color = BLACK;
z->p->p->color = RED;
rb = left_rotate(rb,z->p->p);
}
}
}
rb->color = BLACK;
return rb;
}
struct rb_tree* rb_insert(struct rb_tree *rb, int k) {
struct rb_tree *y = rb->p;
struct rb_tree *x = rb;
struct rb_tree *z;
z= (struct rb_tree *)malloc(sizeof(struct rb_tree));
z->key = k;
while (x->key != T_nil) {
y = x;
if (k< x->key)
x = x->left;
else
x = x->right;
}
z->p = y;
if (y->key == T_nil)
rb = z;
else if (z->key <y->key)
y->left = z;
else
y->right =z;
z->left = rb->p;
z->right = rb->p;
z->color = RED;
return rb_insert_fixup(rb,z);
}
struct rb_tree* rb_delete_fixup(struct rb_tree *rb, struct rb_tree *x) {
struct rb_tree *w;
while ((x !=rb)&&(x->color == BLACK)) {
if (x == x->p->left) {
w = x->p->right;
if (w->color == RED) {
w->color = BLACK;
x->p->color = RED;
left_rotate(rb,x->p);
w = x->p->right;
}
if ((w->left->color == BLACK)&&(w->right->color == BLACK)) {
w->color = RED;
x = x->p;
}
else if (w->right->color == BLACK) {
w->left->color = BLACK;
w->color = RED;
right_rotate(rb,w);
w = x->p->right;
}
w->color = x->p->color;
x->p->color = BLACK;
w->right->color = BLACK;
left_rotate(rb,x->p);
x = rb;
}
else { //same as right and left exchanged
w = x->p->left;
if (w->color == RED) {
w->color = BLACK;
x->p->color = RED;
right_rotate(rb,x->p);
w = x->p->right;
}
if ((w->right->color == BLACK)&&(w->left->color == BLACK)) {
w->color = RED;
x = x->p;
}
else if (w->left->color == BLACK) {
w->right->color = BLACK;
w->color = RED;
left_rotate(rb,w);
w = x->p->left;
}
w->color = x->p->color;
x->p->color = BLACK;
w->left->color = BLACK;
right_rotate(rb,x->p);
x = rb;
}
}
x->color = BLACK;
}
struct rb_tree* rb_delete(struct rb_tree *rb, struct rb_tree *z) {
struct rb_tree *x,*y;
if ((z->left->key == T_nil) || (z->right->key == T_nil))
y = z;
else y = tree_successor(z);
if (y->left->key != T_nil)
x = y->left;
else
x = y->right;
x->p = y->p;
if (y->p->key == T_nil)
rb = x;
else if (y==x->p->left)
y->p->left = x;
else
y->p->right = x;
if (y!=x) //copy y's data to z
z->key = y->key;
if (y->color == BLACK)
rb_delete_fixup(rb,x);
free(y);
return rb;
}
int main () {
struct rb_tree *p,*root;
struct rb_tree tree_nil = {BLACK,T_nil,&tree_nil,&tree_nil,&tree_nil};
root = &tree_nil;
root = rb_insert(root,15);
root = rb_insert(root,5);
root = rb_insert(root,16);
root = rb_insert(root,3);
root = rb_insert(root,12);
root = rb_insert(root,20);
root = rb_insert(root,10);
root = rb_insert(root,13);
root = rb_insert(root,6);
root = rb_insert(root,7);
root = rb_insert(root,18);
root = rb_insert(root,23);
rb_walk(root);
p = rb_search(root,18);
root = rb_delete(root,p);
rb_walk(root);
return 1;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
붉 은 검 은 나무의 독서 노트이 진 트 리 는 동적 정렬 된 데이터 구조 로 삽입, 삭제, 찾기 등 을 지원 하 며 평균 시간 복잡 도 는 O (log (N) 이지 만 일반 이 진 트 리 는 나무 가 한 가지 로 퇴화 하 는 것 을 보장 하지 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
