📌레드블랙 트리의 다섯가지 속성
1.모든 노드는 red 혹은 black
2.루트 노드는 black
3.모든 nil노드는 black
4.red의 자녀들은 반드시 black == red가 연속적으로 존재할 수 없다.
5.임의의 노드에서 자손 nii 노드들까지 가는 경로들의 black 수는 같다 (자기 자신은 카운트에서 제외)
📌rotatiom/recolor
Rotation 을 통해 이진 탐색트리의 특성을 보전하면서 트리의 구조를 수정해 나갈 수 있고, 각각의 경우에 알맞게 Recolor 해주어 레드-블랙 트리의 특성을 만족시키도록 트리를 구성할 수 있다.
RB tree 의 삭제 과정과, 삭제 후에 delete_fix_up 과정을 거치면서 RB tree의 특성을 만족시키도록 수정하는 과정들을 확인하려고 한다.
📌삭제
- 삭제 과정에서는 이진 탐색트리의 특성을 만족하면서 노드를 삭제할 것이다. 이후에 delete_fixup 과정에서 이진탐색트리의 특성과 RB 트리의 특성을 모두 만족시키기 위해 트리의 구조를 변형한다.
- 삭제 과정에서 2가지 상황이 빈번하게 일어난다.
이를 함수화 시켜 놓은 것이 있는데, 슈도코드를 통해 그것을 먼저 검토하고, 삭제 과정을 살펴보자.
📌delete 슈도코드
📌이식
- 삭제될 노드를 target 노드라고 하자, target 노드는 루트노드가 아니라면 parent 노드의 왼쪽 자식 혹은 오른쪽 자식일 것이다.
- 각각의 노드들은 parent, left, right, key, color 필드를 갖고있다. 이식 (transplant) 과정에서는, target 노드와 그 노드의 parent 노드의 연결관계만을 처리하는 과정이다.
- target 노드를 대체할 노드를 구했다고 가정하고, target의 parent 입장에서 왼쪽 자식이었는지, 오른쪽 자식이었는지 파악한 후에 그 자식을 대체할 노드로 지정하고 대체할 노드 또한 target의 parent를 부모노드로 지정하여 두 노드를 연결한다.
u : 삭제할 노드, v : 대체할 노드
- line 1 : if 삭제할 노드(u)의 부모노드가 nil 일 때,
-> 삭제할 노드가 루트노드라면, - line 2 : 트리의 루트노드를 대체할 노드(v)로 설정.
- line 3 : else if 삭제할 노드(u)가 부모노드의 왼쪽 자식일 때,
- line 4 : 삭제할 노드(u)의 왼쪽 자식을 대체할 노드(v)로 설정.
- line 5 : else (삭제할 노드(u)가 부모노드의 오른쪽 자식일 때)
-> 삭제할 노드(u)의 오른쪽 자식을 대체할 노드(v)로 설정. - line 6 : 삭제할 노드(u)의 부모노드를 대체할 노드(v)의 부모노드로 설정.
📌최소값의 노드 산출
- tree_minimum 함수는 삭제할 노드의 위치를 대체할 노드를 산출한다.
- 키값이 10인 노드를 삭제할 때,
이진검색트리의 특성을 유지하면서 10을 대체할 수 있는 노드는 5, 14 다. - 대체할 노드는 삭제될 노드10의 오른쪽 서브트리에서 가장 작은 값 또는 왼쪽 서브트리에서 가장 큰 값이다.
- 오른쪽 서브트리에서 가장 작은 값은 오른쪽 서브트리의 루트노드(16)에서 리프노드(nil)을 만나기 직전 노드인 14 이고,
- 왼쪽 서브트리에서 가장 큰 값은 왼쪽 서브트리의 루트노드(13)에서 리프노드(nil)을 만나기 직전 노드인 5이다.
- 둘중에 아무거나 써도 되는데, 오른쪽 서브트리의 minimum 값을 대체할 노드로 설정하였기 때문에, minimum 함수를 사용할 것이다.
👉🏻step1 : target, target color 저장
- target = 35
- target_original_color = target -> color
- 지워질 노드의 색을 변수에 저장
👉🏻step2 : target의 자식 정보확인
- 삭제할 노드를 y에 복사하여 포인터처럼 활용
- 대체할 노드를 x에 따로 저장
👉🏻step3 :
- case는 3가지 case로 나뉜다.
- 예시는 case 1에 해당한다.
✏️case.1 : 왼쪽 자식이 없을때 ( 자식이 둘다 없을 때도 해당)
- target의 오른쪽 자식을 x로 설정
- 오른쪽 자식을 target 노드에 이식한다.
✏️case.2 : 오른쪽 자식이 없을때
- target의 왼쪽 자식을 x로 설정
- 왼쪽 자식을 target 노드에 이식
✏️case.3 : 자식이 둘다 있을때
📌delete_fix_up
- when : y-original color is black
- while문 조건 : x 노드의 색이 블랙 또는 x가 루트가 아닐때.
- while문 종료 후 : x 의 컬러를 블랙으로 칠함.
💡35를 삭제할때
y-original color = black, x = y-> right이므로 x = nil이며, x - color = black
delete_fix_up 에 들어간다.
📌delete_fix_up 슈도코드
📌case.1
📌case.2
- case.1 이후 왼쪽자식이 red이면 case2는 수행하지 않는다.
📌case.3
- case 3의 경우 항상 case 4로 경유한다.
📌case.4
- case.3을 거치면 case 4의 형태로 바뀐다.
- case.4를 거치면 fix_up 과정이 종료된다. (case2를 거치고 종료되는 경우도 있다.)
📌delete_fix_up 과정에서 탈출하는 경우
1. while -> case
- case 1 :
-> case 2 -> ? (END or continue while)
-> case 3 -> case 4 (END) - case 2 :
-> END
-> ?(while) - case 3 :
-> case 4 -> END - case 4 :
-> END
2. while 해당안됨
- x 의 color 를 검정색으로 칠하고 종료.
/*
#레드-블랙 트리 조건
1.모든 노드는 red 혹은 black
2.루트 노드는 black
3.모든 nil노드는 black
4.red의 자녀들은 반드시 black == red가 연속적으로 존재할 수 없다.
5.임의의 노드에서 자손 nii 노드들까지 가는 경로들의 black 수는 같다 (자기 자신은 카운트에서 제외)
#Rotation
Rotation을 통해 이진 탐색트리의 특성을 보전하면서 트리의 구조를 수정해 나갈 수 있다.
#Recolor
각각의 경우에 알맞게 recolor 해주어 레드-블랙 트리의 특성을 만족시키도록 트리를 구성할 수 있다.
2
*/
#include "rbtree.h"
#include <stdlib.h>
rbtree *new_rbtree(void){
rbtree *p = (rbtree *)calloc(1, sizeof(rbtree));
node_t *NIL = (node_t *)calloc(1, sizeof(node_t));
p -> nil = NIL;
p -> root = NIL;
NIL -> color = RBTREE_BLACK;
return p;
}
// void DeleteByPostOrder(node_t *root, rbtree *t){
// if (root == t -> nil)
// {
// return;
// }
// DeleteByPostOrder(root -> left, t);
// DeleteByPostOrder(root -> right, t);
// free(root);
// }
// 노드 메모리 해제
void delete_node(node_t *node, rbtree *t) {
// 현재 노드가 nil이면 return : 아무 값이 없어서 할당될 것도 없음
if (node == t -> nil) { return; }
// 재귀호출로 끝까지 간 후 해제
delete_node(node -> left, t);
delete_node(node -> right, t);
free(node);
node = NULL; //할당 해제 후 현재 노드 값을 null로 초기화함
return;
}
// 트리 메모리 해제
void delete_rbtree(rbtree *t) {
// TODO: reclaim the tree nodes's memory
// 트리 없으면 return
if (t == NULL) { return; }
delete_node(t ->root, t); //생성된 노드들의 공간 해제
free(t->nil); //nil 노드 해제
t->nil = NULL; //할당 해제 후 nil 값 NULL 값으로 초기화 : 예기치않은 오류와 안정성 확보를 위함
free(t);
t = NULL;
return;
}
// x가 부모이고 y가 오른쪽 노드일때 y를 부모로 바꾸고 x를 왼쪽 노드로 회전 시키는 함수
void left_rotation(rbtree *t, node_t *x)
{
node_t *y = x->right; // x의 오른쪽 노드의 주소를 선언함
x->right = y->left; // y의 왼쪽 노드를 x의 오른쪽으로 옮김
if (y->left != t->nil)
{ // 만약 y의 왼쪽 노드가 NIL이 아니라면,
y->left->parent = x; // 기존 y의 왼쪽에 있던 노드의 parent 노드를 x로 맞추어준다.
}
y->parent = x->parent; // x의 자리에 y가 올라왔으므로, 기존 x의 부모를 y의 부모로 바꾸어준다.
if (x->parent == t->nil)
{ // 만약 x의 부모가 NIL 이라면, root 노드라는 의미이므로,
t->root = y; // y를 트리의 root로 선언한다.
}
else if (x == x->parent->left)
{ // 만약 x가 회전 되기 전에 부모의 왼쪽에 위치한 노드였다면,
x->parent->left = y; // x부모의 왼쪽을 y로 바꾸어준다.
}
else
{ // 아니라면, x가 회전 되기 전에 부모의 오른쪽에 위치했다는 의미이므로,
x->parent->right = y; // x부모의 오른쪽을 y로 바꾸어준다.
}
y->left = x; // y의 왼쪽을 x로 바꾸어준다.
x->parent = y; // x의 부모를 y로 바꾸어준다.
}
// y가 부모이고 x가 왼쪽 노드일때 x를 부모로 바꾸고 y를 오른쪽 노드로 회전 시키는 함수
void right_rotation(rbtree *t, node_t *y)
{
node_t *x = y->left; // y의 왼쪽 노드를 선언함
y->left = x->right; // x의 오른쪽 노드를 y의 왼쪽으로 옮겨줌
if (x->right != t->nil)
{ // x의 오른쪽이 NIL이 아니라면,
x->right->parent = y; // 기존 x의 오른쪽에 있었던 노드의 parent 노드를 y로 맞추어준다.
}
x->parent = y->parent; // y의 자리에 x가 올라왔으므로, 기존 y의 부모를 x의 부모로 바꾸어준다.
if (y->parent == t->nil)
{ // 만약 y의 부모가 NIL 이라면, root 노드라는 의미이므로,
t->root = x; // x를 트리의 root로 선언한다.
}
else if (y == y->parent->left)
{ // 만약 y가 회전 되기 전에 부모의 왼쪽에 위치한 노드였다면,
y->parent->left = x; // y부모의 왼쪽을 x로 바꾸어준다.
}
else
{ // 아니라면, y가 회전 되기 전에 부모의 오른쪽에 위치했다는 의미이므로,
y->parent->right = x; // y부모의 오른쪽을 x로 바꾸어준다.
}
x->right = y; // x의 오른쪽을 y로 바꾸어준다.
y->parent = x; // y의 부모를 x로 바꾸어준다.
}
// 색 변경 함수
void rbtree_insert_fixup(rbtree *t, node_t *z) {
while (z -> parent -> color == RBTREE_RED) { //z의 부모가 red일때
// Case # 1 현재 노드의 삼촌, 부모가 red, 할아범이 black : !회전 안 함!
if (z -> parent == z -> parent -> parent -> left) { //z의 부모가 z의 조상의 왼쪽 자식이면
node_t *uncle = z -> parent ->parent -> right; //z의 부모의 형제노드 = 삼촌
if (uncle -> color == RBTREE_RED) { // 삼촌이 red라면
z -> parent -> color = RBTREE_BLACK; // 부모 red > black
uncle -> color = RBTREE_BLACK; // 삼촌 red > black
z -> parent -> parent -> color = RBTREE_RED; // 할아범 black > red
z = z -> parent -> parent; // 할아버지 가리켜야 다시 while문을 돈다!
} else { // 삼촌이 black Case 2, 3
if (z == z -> parent ->right) { //꺾새 모양
z = z -> parent;
left_rotation(t, z); // 좌회전
} // Case 3이 됨 > 색 바꿔주고 우회전하면 끝남
z -> parent -> color = RBTREE_BLACK;
z -> parent -> parent -> color = RBTREE_RED;
right_rotation(t, z -> parent -> parent); // 조상 기준으로 우회전해야함
}
} else { //z의 부모가 z의 조상의 오른쪽이면 위의 과정을 반대로
node_t *uncle = z -> parent -> parent -> left;
if (uncle -> color == RBTREE_RED) {
z -> parent -> color = RBTREE_BLACK;
uncle -> color = RBTREE_BLACK;
z -> parent -> parent -> color = RBTREE_RED;
z = z -> parent -> parent;
} else {
if (z == z -> parent -> left) {
z = z -> parent;
right_rotation(t, z);
}
z -> parent -> color = RBTREE_BLACK;
z -> parent -> parent -> color = RBTREE_RED;
left_rotation(t, z -> parent ->parent);
}
}
} //While문 끝
t -> root -> color = RBTREE_BLACK; // 규칙 2를 위해서 root는 항상 black
return; //void형
}
// 데이터 삽입
node_t *rbtree_insert(rbtree *t, const key_t key) {
// TODO: implement insert
node_t *y = t -> nil; // y = 트리의 nil 노드
node_t *x = t -> root; // x = 트리의 root
while (x != t -> nil) { //x가 nil에 도달할때까지 반복
y = x;
if (key < x->key) { //만약 x의 key값보다 삽입할 key의 값이 작으면
x = x -> left; //x를 x의 왼쪽으로 변경
} else { //만약 x의 key값보다 삽입할 key값이 크거나 같으면
x = x -> right; // x를 x의 오른쪽으로 변경
}
}
//x가 nil을 가리킴 > z를 삽입할 시기
node_t *z = (node_t *)calloc(1, sizeof(node_t)); // z 노드 생성
z -> key = key; // z의 key값 넣어줌
z -> parent = y; // z의 부모는 y
if (y == t -> nil) { //y가 트리의 nil일때, 비어있던 애(첫 노드)
t -> root = z; // Case 1 (고려할 필요 없는 경우임 걍 들어감)
} else if (z -> key < y -> key) { // y의 key값이 삽입할 key값보다 작을 때
y -> left = z; // y의 왼쪽 자식으로 감
} else {
y -> right = z;
}
z -> left = t -> nil; // z 왼쪽 자식 nil
z -> right = t -> nil; // z 오른쪽 자식 nil
z -> color = RBTREE_RED; // 삽입은 늘 red
// left_rotation(t,z);
// if (z->parent->parent != NULL) {
// right_rotation(t,z);
// }
rbtree_insert_fixup(t, z);
return t->root;
}
// 데이터 검색
node_t *rbtree_find(const rbtree *t, const key_t key) {
// TODO: implement find
node_t *x = t -> root; //x는 root, root에서부터 검색 시작
while (x != t -> nil && key != x -> key) { //x가 nil노드가 아니거나 찾는 key값이 x가 아닐때
if (x -> key < key) { // 찾는 key값보다 key가 클때
x = x -> right; //x의 오른쪽 자식으로 이동
} else { //찾는 key값이 더 작을 때
x = x -> left; //x의 왼쪽 자식으로 이동
}
}
if (x == t -> nil) { // x가 nil 노드 = key값을 찾지 못했을때
return NULL; // NULL 반환
}
return x;
// return t->root;
}
// 트리의 최소값 = BST특성
node_t *rbtree_min(const rbtree *t) {
// TODO: implement find
node_t *x = t -> root; //x는 트리의 루트
while (x -> left != t -> nil) { //x의 왼쪽 자식이 nil이 아닐때
x = x -> left; // 왼쪽이 제일 작은 값임
}
return x;
}
// 트리의 최대값 = BST특성
node_t *rbtree_max(const rbtree *t) {
// TODO: implement find
node_t *x = t -> root; //x는 트리의 루트
while (x -> right != t -> nil) { //x의 왼쪽 자식이 nil이 아닐때
x = x -> right; // 오른쪽이 제일 큰 값임
}
return x;
}
// 삭제될 노드를 떼어내기 위해 대체노드를 붙이는 함수
void rbtree_transplant(rbtree *t, node_t *u, node_t *v) {
// u는 삭제될 노드, v는 대체될 노드 u를 지우고 v를 u.p에 연결시킬거임
// u가 있던 자리에 걍 v 집어넣는 식 = u에 이어진 노드가 없어 고립되어 자동으로 떨어짐
// 삭제 연산할때 default로 실행됨
if (u -> parent == t -> nil) { // u의 부모가 nil = u가 root라는 소리
t -> root = v; // 트리의 root 자리에 v를 집어넣음
} else if (u == u -> parent -> left) { // 삭제될 노드가 왼쪽 자식일때
u -> parent -> left = v; // u는 버려지고, v가 붙음
} else { // 삭제될 노드가 오른쪽 자식
u -> parent -> right = v; //오른쪽 자식은 이제 v가 됨
}
v -> parent = u -> parent; // v의 부모는 u의 부모
return; //void형
}
void rbtree_erase_fixup(rbtree *t, node_t *x)
{
node_t *w;
while (x != t->root && x->color == RBTREE_BLACK) // x가 root가 아니고, x의 색이 BLACK일 동안
{
if (x == x->parent->left) // doubly black인 x가 왼쪽 자식일 경우
{
w = x->parent->right; // w는 x의 형제 노드
if (w->color == RBTREE_RED)
{ // x의 오른쪽 형제 w가 RED인 경우 -> case 1) doubly black의 형제가 RED인 경우에 해당
w->color = RBTREE_BLACK; // 형제의 색을 BLACK으로 변경하고
x->parent->color = RBTREE_RED; // 형제의 부모의 색을 RED로 변경한다.
left_rotation(t, x->parent); // 부모를 기준으로 왼쪽 회전 수행
w = x->parent->right; // x의 위치가 바뀌었으므로, x의 형제인 w의 위치 또한 갱신해줌
} // 이후 경우1은 경우 2,3,4 중 하나로 변환 되었음
if (w->left->color == RBTREE_BLACK && w->right->color == RBTREE_BLACK) // 형제의 자식이 모두 BLACK일 경우 case 2) doubly black의 형제의 자식이 모두 BLACK일 경우에 해당
{
w->color = RBTREE_RED; // 형제의 검은색을 부모에게 주므로 기존 BLACK에서, RED로 변함
x = x->parent; // x의 부모가 x의 extra black을 물려받아, 새로운 red and black 또는 doubly black이 됨
}
else // 형제의 자식 중 RED인 자식이 있을 경우 case 3)에 해당, 회전을 통해 case 4)로 변경해주어야함
{
if (w->right->color == RBTREE_BLACK) // 형제 자식의 오른쪽 노드가 BLACK이고, 왼쪽 노드가 RED일 경우
{
w->left->color = RBTREE_BLACK; // 형제의 왼쪽 노드를 RED -> BLACK으로 변경
w->color = RBTREE_RED; // 형제의 색깔을 BLACK -> RED로 변경
right_rotation(t, w); // 오른쪽 회전 시켜서 꺾이지 않도록 함
w = x->parent->right; // x의 위치가 바뀌었으므로, x의 형제인 w의 위치 또한 갱신해줌
}
// case 4)에 해당
w->color = x->parent->color; // 형제의 색을 부모의 색으로 변경
x->parent->color = RBTREE_BLACK; // 부모의 색을 BLACK으로 변경
w->right->color = RBTREE_BLACK; // 형제의 오른쪽 자식의 색을 BLACK으로 변경
left_rotation(t, x->parent); // 왼쪽 회전 시킴
x = t->root;
}
}
else // doubly black인 x가 오른쪽 자식일 경우
{
w = x->parent->left; // w는 x의 형제 노드
if (w->color == RBTREE_RED)
{ // 형제의 색깔이 RED인 경우 -> case 1)에 해당
w->color = RBTREE_BLACK; // 형제의 색을 BLACK으로 변경한다.
w->parent->color = RBTREE_RED; // 형제의 부모의 색을 RED로 변경한다.
right_rotation(t, x->parent); // 부모를 기준으로 오른쪽 회전 수행
w = x->parent->left; // x의 위치가 바뀌었으므로, x의 형제인 w의 위치 또한 갱신해준다.
} // 이후 경우1은 경우 2,3,4 중 하나로 변환 되었음
if (w->left->color == RBTREE_BLACK && w->right->color == RBTREE_BLACK) // case 2)에 해당
{
w->color = RBTREE_RED; // 형제의 검은색을 부모에게 주므로 기존 BLACK에서, RED로 변함
x = x->parent; // x의 부모가 x의 extra black을 물려받아, 새로운 red and black 또는 doubly black이 됨
}
else // 형제의 자식 중 RED인 자식이 있을 경우 case 3)에 해당, 회전을 통해 case 4)로 변경해주어야함
{
if (w->left->color == RBTREE_BLACK) // 형제의 자식의 오른쪽 자식 색깔이 RED인 경우 -> 오른쪽 자식이 red인 상태에서 왼쪽 자식이 red인 상태로 바꾸어 준다.
{
w->right->color = RBTREE_BLACK; // 형제 오른쪽 노드를 RED -> BLACK
w->color = RBTREE_RED; // 형제 색깔을 BLACK -> RED
left_rotation(t, w); // 왼쪽으로 회전
w = x->parent->left; // x의 위치가 바뀌었으므로, x의 형제인 w의 위치 또한 갱신해줌
}
// 형제의 자식의 왼쪽 노드의 자식 색깔이 RED인 경우 case 4)에 해당
w->color = x->parent->color; // 형제의 색을 부모의 색으로 변경
x->parent->color = RBTREE_BLACK; // 부모의 색을 BLACK으로 변경
w->left->color = RBTREE_BLACK; // 형제의 왼쪽 자식의 색을 BLACK으로 변경
right_rotation(t, x->parent); // 오른쪽 회전 시킴
x = t->root;
}
}
}
x->color = RBTREE_BLACK;
}
// 직후 원소 찾기, 오른쪽 서브트리의 min값 = 제일 오른쪽 값
node_t *rbtree_successor(rbtree *t, node_t *x) {
node_t *y = x; // y는 직후 원소
while (y -> left != t -> nil) { //y의 왼쪽 자식이 nil일때까지 반복
y = y -> left; //y는 y의 왼쪽 자식이 됨
}
return y;
}
/*
보통의 bst처럼 delete한다.
실제로 삭제된 노드 y가 red였으면 종료
y가 black이었을 겨우 rb-delete-fixup을 호출한다.
*/
int rbtree_erase(rbtree *t, node_t *z)
{
node_t *y = z; // z는 삭제 대상의 주소 값, y는 자식 갯수에 따라서 그대로 z가 될 수도 있고, z의 successor의 주소가 될 수도 있다.
node_t *x; // y의 원래 위치로 이동시키는 용도의 노드 x. y의 오른쪽 자식 또는 자식이 없을 경우 t->nil 로 설정된다.
color_t y_original_color = y->color; // y의 색깔은 변경될 가능성이 존재하므로, 미리 새로운 변수에 y의 원래 색깔을 저장해둔다.
if (z->left == t->nil)
{ // z의 왼쪽 노드가 없다면
x = z->right; // z의 오른쪽 노드를 x로 선언한다.
rbtree_transplant(t, z, z->right); // z의 오른쪽 노드를 z의 자리에 교체한다.
}
else if (z->right == t->nil)
{ // z의 오른쪽 노드가 없다면
x = z->left;
rbtree_transplant(t, z, z->left); // z의 왼쪽 노드를 z의 자리에 교체한다.
}
else // z의 자식 노드가 둘 다 있을 경우
{
y = rbtree_successor(t, z->right); // z의 오른쪽 서브트리의 successor를 찾는다.
y_original_color = y->color; //짝대기 떄고 갈아 끼운다
x = y->right;
if (y->parent == z)
{ // 만약 z의 오른쪽 서브트리의 successor가 z의 오른쪽 노드라면
x->parent = y; // x의 부모를 y로 선언
}
else
{
rbtree_transplant(t, y, y->right); // z에 z의 successor인 y를 이식하기 전에, y의 자리에 y의 자식을 이식 시켜둔다
y->right = z->right; // z 자리에 y를 이식하기 전, y의 오른쪽 자식을 z의 오른쪽 자식으로 교체
y->right->parent = y; // z자리에 y를 이식하기 전, y의 오른쪽 자식의 부모 노드를 y로 교체
}
rbtree_transplant(t, z, y); // z의 자리에 y를 이식한다.
y->left = z->left; // z의 왼쪽 자식이 y의 왼쪽 자식이 된다.
y->left->parent = y; // z의 왼쪽 자식의 부모가 곧, y가 된다.
y->color = z->color; // y가 z의 자리에 이식되고, y는 z의 색깔만 물려 받는다(값은 본래 y의 값 유지)
}
// 만약 삭제 대상의 색깔이 BLACK이라면, 각 경로의 BLACK 노드의 갯수의 균형이 깨지게 되므로, 균형을 맞춰 주어야 한다.
if (y_original_color == RBTREE_BLACK)
{
rbtree_erase_fixup(t, x);
}
free(z); // z가 삭제 되었으므로, z의 메모리 주소를 비워준다.
return 0;
}
//트리 중위순회하는 함수, 재귀
int rbtree_inorder(node_t *nil, node_t *root, key_t *arr, const size_t n, int index) {
if (root == nil) { //root가 nil이면
return index; //index 반환
}
// 재귀 종료 조건
if (index == n) {
return index;
}
index = rbtree_inorder(nil, root->left, arr, n, index); //root의 왼쪽 자식으로 재귀
if (index < n) { //index가 n보다 작을때만 arr에 값을 추가함
arr[index++] = root -> key; //arr[현재 index] = 현재 노드의 key 값
}
index = rbtree_inorder(nil, root->right, arr, n, index); //root의 오른쪽 자식으로 재귀
return index;
}
// 트리를 이용한 오름차순 arr 구현
int rbtree_to_array(const rbtree *t, key_t *arr, const size_t n) {
// TODO: implement to_array
if (t -> root == t -> nil) { //트리의 루트가 nil이면 반환
return 0;
}
rbtree_inorder(t->nil, t -> root, arr, n, 0); //중위 순회
return 0;
}
'SWjungle > #레드블랙트리' 카테고리의 다른 글
[Red-Black 트리]삽입- 구현 (0) | 2023.09.05 |
---|---|
[Red-Black 트리]삭제 (0) | 2023.09.04 |
[Red-Black 트리]삽입 (2) | 2023.09.04 |
[Red-Black 트리] 소개 (2) | 2023.09.03 |