7시에 일어났는데 조금만 더 자야히지 하다가 50분 더 잠.
08:07 입실
오늘은 RB Tree C코드 전반적으로 다시 쳐 보고, 코드 개선!
C
typedef
타입을 재정의하는 명령어
변수 타입 재정의하기
typedef int score_t; // 원래 int 타입을 score_t로 별명 생성
tptedef char answer_t; // 원래 char 타입을 answer_t로 별명 생성
int score; // 원래 버전
score_t score; // 재정의
char answer; // 원래 버전
answer_t answer // 재정의구조체 재정의하기
// 1. 구조체 선언 후 재정의
struct student {
char name[10];
char phone[11];
int score;
};
typedef struct student student
// 2. 선언과 동시에 재정의
typedef struct student {
char name[10];
char phone[11];
int score;
} student;
//타입 재정의 전 구조체 변수 선언
struct student s1;
// 타입 재정의 후 구조체 변수 선언
student s1;
헤더 파일
#include <stdio.h>이 하는 역할이 뭘까?
헤더 파일은 함수와 FILE 데이터 형식 관련된 매크로 상수(#define), 기호를 정의한다.
함수의 경우 함수가 직접 정의되어 있는 것이 아니라, 해당 함수의 프로토타입(선언)만 포함되어 있고,
함수의 이름, 매개변수 목록, 반환 값 같은 선언이 있다.
실제 구현은 헤더파일이 아닌 라이브러리 파일에 있다.
즉, 표준 함수를 사용할 때 해당 헤더파일을 적어주어야,
전처리기가 해당 함수 프로토타입을 본문에 추가하고,
링커가 라이브러리와 코드를 연결시켜 준다.
매크로 상수
#define MAXSCORE 100;
매크로 상수는 변수가 아니다.
컴파일 시 단순히 코드 내 해당 텍스트를 치환해 주는 역할만 한다!
랜덤
rand()는 씨드 값을 기준으로 랜덤값을 생성한다.
씨드값을 변경하기 위해서는 srand()로 씨드값을 변경해야 한다.
srand()가 없으면 씨드는 1이 되어 매번 똑같은 값을 출력한다.
하지만 씨드가 같으면 의미가 없다.
그래서 씨드를 자체를 랜덤하게 넣어주는데 그때 자주 사용하는 게 시간이다.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main() {
int rad;
srand((unsigned int)time(NULL));
rad = rand();
printf("%d", rad);
}파일 입출력
파일과 시스템과의 스트림을 생성하면 됨!
FILE 구조체는 표준 라이브러리에 정의되어 있음.
- FILE 구조체 포인터 변수 선언
- 파일 스트림 생성(파일 구조체 생성 및 포인터 저장)
#include <stdio.h>
int main()
{
#include <stdio.h>
int main()
{
FILE *fp;
fp = fopen("파일명", "모드(r, w, a)");
char ch;
if (fp == NULL)
{
return 0;
}
fprintf(fp, "%s", "HelloWorld"); // 파일에 출력
// 파일을 끝까지 읽어오는 코드
while (1)
{
ch = fgetc(fp); // 파일에서 한 글자 읽어 옴(r모드로 열어야 됨))
if (ch == EOF)
{
break;
}
printf("%c", ch);
}
fclose(fp);
return 0;
}리눅스
명령어 파이프
명령어1 | 명령어2
명령어1의 결과를 명령어 2로 넘겨서 실행
단순히 명령어를 이어서 실행하는 개념이 아니라,
명령어1의 출력을 명령어2의 입력으로 넣어주는 개념!
// mytest.txt 파일을 읽어서 "keyword"를 찾는다.
cat mytext.txt | grep "keyword"RB Tree
동적 할당
트리 삭제 시 사용할 스택을 1024로 정적 할당했는데,
동적 할당으로 도전해 봄!
트리의 높이를 계산하는 함수
// 트리의 높이를 반환하는 함수입니다.
int rbtree_height(rbtree *tree, node_t *root)
{
if (!root) {
print_message(NODE_LOAD_FAILED);
return -1;
}
if (root == tree->nil) {
return 0;
}
int left_height = rbtree_height(tree, root->left);
int right_height = rbtree_height(tree, root->right);
int max_height = left_height > right_height ? left_height : right_height;
return 1 + max_height;
}트리 삭제 시 스택 동적 할당
// 트리의 높이를 계산합니다.
int height = rbtree_height(tree, tree->root);
// int height = 2; // 테스트용 임시 높이
// 트리 안의 노드를 삭제하기 위한 스택을 생성합니다.
node_t **stack = (node_t **)calloc(height, sizeof(node_t *));
int stack_top = 0;메모리가 부족하면 정말 문제가 생길까?
메모리가 부족하면 정말 문제가 생길지 궁금해서 실험을 해 보았다.
스택의 크기를 정상적으로 계산해서 실행했을 때는 pass
그럼, height를 강제로 2로 고정하고 돌리면?
// 트리의 높이를 계산합니다.
// int height = rbtree_height(tree, tree->root);
int height = 2;
// 트리 안의 노드를 삭제하기 위한 스택을 생성합니다.
node_t **stack = (node_t **)calloc(height, sizeof(node_t *));
int stack_top = 0;
오호, 메모리가 부족하면 정말 문제가 생긴다!
정적 할당 vs 동적 할당
그럼 [1024]를 정적으로 할당할 때와 calloc으로 동적 할당하면
실제로 메모리 사용에서 어떤 차이가 날까?
정적 할당 했을 때
힙 사용량: 20,123
동적 할당 했을 때
힙 사용량: 20,135
동적 할당을 하면 힙 영역이 더 쓰이니까, 힙 영역이 더 늘어난 것을 볼 수 있다.
최종 버전(이기를..)
처음부터 따라치면서 연습해 봄.
중간 중간 누락된 부분이 많아서 생각보다 오래 걸림.
변수명을 직관적으로 바꿔보고, 예외 처리 메시지도 따로 뺌.
예외 처리를 해 놓으니까 디버깅 시 훨씬 편했음!
트리 삭제 시 노드를 담을 스택도 동적 할당해 보았다!
#include "rbtree.h"
#include <stdio.h>
#include <stdlib.h>
// 예외 메시지 타입을 정의합니다.
typedef enum
{
MALLOC_FAILED,
TREE_GENERATE_FAILED,
NODE_GENERATE_FAILED,
TREE_LOAD_FAILED,
NODE_LOAD_FAILED,
ETC
} message_t;
// 타입에 맞는 예외 메시지를 출력하는 함수입니다.
void print_message(message_t type)
{
switch (type) {
case MALLOC_FAILED:
printf("메모리 할당에 실패하였습니다.\n");
break;
case TREE_LOAD_FAILED:
printf("트리를 불러올 수 없습니다.\n");
break;
case NODE_LOAD_FAILED:
printf("노드를 불러올 수 없습니다.\n");
break;
case TREE_GENERATE_FAILED:
printf("트리 생성에 실패하였습니다.\n");
break;
case NODE_GENERATE_FAILED:
printf("노드 생성에 실패하였습니다.\n");
break;
case ETC:
printf("기타 예외가 발생하였습니다.\n");
break;
default:
printf("알 수 없는 메시지 타입입니다.\n");
break;
}
}
// 새로운 트리를 생성하는 함수입니다.
rbtree *new_rbtree(void)
{
// 트리를 생성합니다.
rbtree *tree = (rbtree *)calloc(1, sizeof(rbtree));
if (!tree) {
print_message(TREE_GENERATE_FAILED);
return NULL;
}
// nil노드를 생성합니다.
node_t *nil_node = (node_t *)calloc(1, sizeof(node_t));
if (!nil_node) {
print_message(NODE_GENERATE_FAILED);
free(tree);
return NULL;
}
// nil노드 초기 멤버를 설정합니다.
nil_node->color = RBTREE_BLACK;
nil_node->parent = nil_node;
nil_node->left = nil_node;
nil_node->right = nil_node;
// 트리의 초기 멤버를 설정합니다.
tree->root = nil_node;
tree->nil = nil_node;
return tree;
}
// 트리의 높이를 반환하는 함수입니다.
int rbtree_height(rbtree *tree, node_t *root)
{
if (!root) {
print_message(NODE_LOAD_FAILED);
return -1;
}
if (root == tree->nil) {
return 0;
}
int left_height = rbtree_height(tree, root->left);
int right_height = rbtree_height(tree, root->right);
int max_height = left_height > right_height ? left_height : right_height;
return 1 + max_height;
}
// 생성된 트리를 삭제하는 함수입니다.
void delete_rbtree(rbtree *tree)
{
if (!tree) {
print_message(TREE_LOAD_FAILED);
return;
}
// 트리의 높이를 계산합니다.
int height = rbtree_height(tree, tree->root);
// int height = 2; // 메모리 동적 할당 실험용 임시 코드입니다.
// 트리 안의 노드를 삭제하기 위한 스택을 생성합니다.
node_t **stack = (node_t **)calloc(height, sizeof(node_t *));
// node_t *stack[1024]; // 메모리 정적 할당 실험용 임시 코드입니다.
int stack_top = 0;
// 루트 노드가 존재하면 노드 탐색을 시작합니다.
if (tree->root != tree->nil) {
stack[stack_top++] = tree->root;
}
// 스택에 오른쪽 노드를 먼저 넣어 전위 순회합니다.
while (stack_top > 0) {
node_t *node = stack[--stack_top];
if (node->right != tree->nil) {
stack[stack_top++] = node->right;
}
if (node->left != tree->nil) {
stack[stack_top++] = node->left;
}
// 자식 삽입이 끝난 노드는 메모리 반납(노드 삭제)합니다.
free(node);
node = NULL;
}
// 트리 내의 모든 노드를 삭제 후 최종적으로 nil노드와 트리, 스택을 삭제합니다.
free(tree->nil);
free(tree);
free(stack);
}
// 좌회전 함수입니다.
void left_rotate(rbtree *tree, node_t *x)
{
// 중심 노드 또는 오른쪽 자식이 nil이면 좌회전을 하지 않습니다.
if (x == tree->nil || x->right == tree->nil) {
return;
}
// y를 설정합니다.(좌회전 대기)
node_t *y = x->right;
// y의 왼쪽 서브트리를 x의 오른쪽 서브트리로 옮깁니다.
x->right = y->left;
if (y->left != tree->nil) { // nil 노드의 부모는 변경할 수 없습니다.
y->left->parent = x;
}
// y를 부모 자리(현 x)로 좌회전합니다.
y->parent = x->parent;
if (x->parent == tree->nil) { // x가 루트 노드였다면 좌회전된 y노드를 루트 노드로 설정합니다.
tree->root = y;
} else if (x == x->parent->left) { // x가 부모의 왼쪽 자식이었다면 좌회전된 y를 원부모의 왼쪽 자식으로 설정합니다.
x->parent->left = y;
} else if (x == x->parent->right) { // x가 부모의 오른쪽 자식이었다면 좌회전된 y를 원부모의 오른쪽 자식으로 설정합니다.
x->parent->right = y;
}
// x를 y의 왼쪽 자식으로 좌회전합니다.
y->left = x;
x->parent = y;
}
// 우회전 함수입니다.
void right_rotate(rbtree *tree, node_t *x)
{
// 중심 노드 또는 왼쪽 자식이 nil이면 우회전이 하지 않습니다.
if (x == tree->nil || x->left == tree->nil) {
return;
}
// y를 설정합니다.(우회전 대기)
node_t *y = x->left;
// y의 오른쪽 서브트리를 x의 왼쪽 서브트리로 옮깁니다.
x->left = y->right;
if (y->right != tree->nil) { // nil 노드의 부모는 변경할 수 없습니다.
y->right->parent = x;
}
// y를 부모 자리(현 x)로 우회전합니다.
y->parent = x->parent;
if (x->parent == tree->nil) { // x가 루트 노드였다면 우회전된 y노드를 루트 노드로 설정합니다.
tree->root = y;
} else if (x == x->parent->left) { // x가 부모의 왼쪽 자식이었다면 우회전된 y를 원부모의 왼쪽 자식으로 설정합니다.
x->parent->left = y;
} else if (x == x->parent->right) { // x가 부모의 오른쪽 자식이었다면 우회전된 y를 원부모의 오른쪽 자식으로 설정합니다.
x->parent->right = y;
}
// x를 y의 오른쪽 자식으로 우회전합니다.
y->right = x;
x->parent = y;
}
// 트리에 노드를 삽입한 후 레드블랙트리의 특성을 복구하는 함수입니다.
void rbtree_insert_fixup(rbtree *tree, node_t *new_node)
{
// 주목 노드가 레드인 경우에는 트리 재조정을 진행합니다.
while (new_node != tree->root && new_node->parent->color == RBTREE_RED) {
// case A. 현재 노드가 왼쪽 서브트리에 속한 경우입니다.(최종적으로 우회전 필요)
if (new_node->parent == new_node->parent->parent->left) {
node_t *uncle = new_node->parent->parent->right;
if (uncle->color == RBTREE_RED) { // case1: 삼촌이 레드인 경우
new_node->parent->color = RBTREE_BLACK; // 부모 노드를 블랙으로 설정합니다.
uncle->color = RBTREE_BLACK; // 삼촌 노드를 블랙으로 설정합니다.
new_node->parent->parent->color = RBTREE_RED; // 조부모를 레드로 설정합니다.(조부모가 부모, 삼촌에게 블랙을 물려줍니다.)
new_node = new_node->parent->parent; // 블랙을 물려준 조부모를 신규 노드로 재설정합니다.
} else { // case 2 & 3: 삼촌이 블랙인 경우
if (new_node == new_node->parent->right) { // case2: 삼촌이 블랙이고, 주목 노드가 오른쪽 자식인 경우(노드 꺾임)
new_node = new_node->parent; // 부모 노드를 기준으로 설정하고,
left_rotate(tree, new_node); // 좌회전 해서 case3로 전환합니다.
}
// case3: 삼촌이 블랙이고, 신규 노드가 왼쪽 자식인 경우(노드 직선)
new_node->parent->color = RBTREE_BLACK;
new_node->parent->parent->color = RBTREE_RED;
right_rotate(tree, new_node->parent->parent); // 조부모를 기준으로 우회전해서 전체 트리의 균형을 맞춥니다.
}
// case B. 현재 노드가 오른쪽 서브트리에 속한 경우입니다.(최종적으로 좌회전 필요)
} else if (new_node->parent == new_node->parent->parent->right) {
node_t *uncle = new_node->parent->parent->left;
if (uncle->color == RBTREE_RED) {
new_node->parent->color = RBTREE_BLACK;
uncle->color = RBTREE_BLACK;
new_node->parent->parent->color = RBTREE_RED;
new_node = new_node->parent->parent;
} else {
if (new_node == new_node->parent->left) {
new_node = new_node->parent;
right_rotate(tree, new_node);
}
new_node->parent->color = RBTREE_BLACK;
new_node->parent->parent->color = RBTREE_RED;
left_rotate(tree, new_node->parent->parent);
}
}
}
// 루트 노드를 항상 블랙으로 설정합니다.
tree->root->color = RBTREE_BLACK;
}
// 트리에 새로운 노드를 삽입하는 함수입니다.
node_t *rbtree_insert(rbtree *tree, const key_t key)
{
// 신규 노드를 생성합니다.
node_t *new_node = (node_t *)malloc(sizeof(node_t));
if (!new_node) {
print_message(NODE_GENERATE_FAILED);
return tree->root;
}
// 노드의 초기 멤버를 설정합니다.
new_node->color = RBTREE_RED;
new_node->key = key;
new_node->parent = tree->nil;
new_node->left = tree->nil;
new_node->right = tree->nil;
// 신규 노드가 삽입될 위치를 찾습니다.
node_t *current = tree->root; // 주목 노드를 설정합니다.
node_t *parent = tree->nil; // 초기 부모를 nil노드로 설정합니다.
while (current != tree->nil) {
parent = current; // 신규 노드의 부모가 될 노드입니다.
if (key < current->key) { // 주목 노드보다 키가 작으면 왼쪽 서브트리를 탐색합니다.
current = current->left;
} else if (key > current->key) { // 주목 노드보다 키가 크면 오른쪽 서브트리를 탐색합니다.
current = current->right;
} else if (key == current->key) { // 중복된 값인 경우 오른쪽 서브트리를 탐색합니다.
current = current->right;
}
}
// while문 종료 시 신규 노드의 부모 노드가 결정되었습니다.
new_node->parent = parent;
if (parent == tree->nil) { // 트리가 비어있으면 신규 노드를 루트 노드로 설정합니다.
tree->root = new_node;
} else if (key < parent->key) { // 부모 노드보다 신규 노드의 값이 작으면 왼쪽 자식으로 설정합니다.
parent->left = new_node;
} else if (key > parent->key) { // 부모 노드보다 신규 노드의 값이 크면 오른쪽 자식으로 설정합니다.
parent->right = new_node;
} else if (key == parent->key) { // 중복된 값일 경우 오른쪽 자식으로 설정합니다.
parent->right = new_node;
}
// 레드블랙트리의 특성을 복구합니다.
rbtree_insert_fixup(tree, new_node);
return new_node;
}
node_t *rbtree_find(const rbtree *tree, const key_t key)
{
node_t *current = tree->root;
while (current != tree->nil) {
if (key == current->key) {
return current;
}
if (key < current->key) {
current = current->left;
} else {
current = current->right;
}
}
return NULL;
}
// 전체 트리에서 최솟값 노드를 반환하는 함수입니다.
node_t *rbtree_min(const rbtree *tree)
{
if (!tree) {
return NULL;
}
node_t *current = tree->root;
while (current->left != tree->nil) {
current = current->left;
}
return current;
}
// 전체 트리에서 최댓값 노드를 반환하는 함수입니다.
node_t *rbtree_max(const rbtree *tree)
{
if (!tree) {
return NULL;
}
node_t *current = tree->root;
while (current->right != tree->nil) {
current = current->right;
}
return current;
}
// 특정 노드를 기준으로 최솟값 노드를 반환하는 함수입니다.
node_t *rbtree_min_in_subtree(rbtree *tree, node_t *node)
{
if (!tree) {
print_message(TREE_LOAD_FAILED);
return NULL;
}
if (!node) {
print_message(NODE_LOAD_FAILED);
return NULL;
}
node_t *current = node;
while (current->left != tree->nil) {
current = current->left;
}
return current;
}
// 특정 노드를 기준으로 최댓값 노드를 반환하는 함수입니다.
node_t *rbtree_max_in_subtree(rbtree *tree, node_t *node)
{
if (!tree) {
print_message(TREE_LOAD_FAILED);
return NULL;
}
if (!node) {
print_message(NODE_LOAD_FAILED);
return NULL;
}
node_t *current = node;
while (current->right != tree->nil) {
current = current->right;
}
return current;
}
// 삭제할 노드의 서브트리를 삭제할 부모에 연결하는 함수입니다.(노드 삭제가 진행됩니다.)
void rbtree_transplant(rbtree *tree, node_t *target_node, node_t *replaced_node)
{
if (!tree) {
print_message(TREE_LOAD_FAILED);
return;
}
if (!target_node || !replaced_node) {
print_message(NODE_LOAD_FAILED);
return;
}
if (target_node->parent == tree->nil) {
tree->root = replaced_node;
} else if (target_node == target_node->parent->left) {
target_node->parent->left = replaced_node;
} else {
target_node->parent->right = replaced_node;
}
replaced_node->parent = target_node->parent;
}
// 트리에서 노드를 삭제한 후 레드블랙트리의 특성을 복구하는 함수입니다.
void rbtree_erase_fixup(rbtree *tree, node_t *replaced_node)
{
node_t *sibling;
while (replaced_node != tree->root && replaced_node->color == RBTREE_BLACK) {
if (replaced_node == replaced_node->parent->left) { // case A. 주목 노드가 왼쪽 자식인 경우
sibling = replaced_node->parent->right;
// case 1. 형제 노드가 레드인 경우
if (sibling->color == RBTREE_RED) {
sibling->color = RBTREE_BLACK; // 좌회전을 대비해서 형제 노드와 부모 노드의 색을 교환합니다.
replaced_node->parent->color = RBTREE_RED;
left_rotate(tree, replaced_node->parent);
sibling = replaced_node->parent->right; // 새로운 형제노드를 설정해서 case 2~4로 변환합니다.
}
// case 2. (형제 노드는 블랙) 형제 노드의 두 자식이 모두 블랙인 경우
if (sibling->left->color == RBTREE_BLACK && sibling->right->color == RBTREE_BLACK) {
sibling->color = RBTREE_RED;
replaced_node = replaced_node->parent; // 만약 주목 노드가 루트 노드이거나, 블랙이면 조정이 완료됩니다.
} else if (sibling->left->color == RBTREE_RED && sibling->right->color == RBTREE_BLACK) { // case 3. (형제 노드는 블랙) 형제 노드의 왼쪽 자식은 레드, 오른쪽 자식은 블랙인 경우
sibling->left->color = RBTREE_BLACK;
sibling->color = RBTREE_RED;
right_rotate(tree, sibling);
sibling = replaced_node->parent->right; // 새로운 형제가 설정되고, case 4로 변환됩니다.
}
// case 4. case2의 일부를 제외하고 모든 case는 case4로 귀결됩니다.
sibling->color = replaced_node->parent->color;
replaced_node->parent->color = RBTREE_BLACK;
sibling->right->color = RBTREE_BLACK;
left_rotate(tree, replaced_node->parent);
replaced_node = tree->root;
} else { // case B. 주목 노드가 오른쪽 자식인 경우
sibling = replaced_node->parent->left;
// case 1. 형제 노드가 레드인 경우
if (sibling->color == RBTREE_RED) {
sibling->color = RBTREE_BLACK; // 좌회전을 대비해서 형제 노드와 부모 노드의 색을 교환합니다.
replaced_node->parent->color = RBTREE_RED;
right_rotate(tree, replaced_node->parent);
sibling = replaced_node->parent->left; // 새로운 형제노드를 설정해서 case 2~4로 변환합니다.
}
// case 2. (형제 노드는 블랙) 형제 노드의 두 자식이 모두 블랙인 경우
if (sibling->right->color == RBTREE_BLACK && sibling->left->color == RBTREE_BLACK) {
sibling->color = RBTREE_RED;
replaced_node = replaced_node->parent; // 만약 주목 노드가 루트 노드이거나, 블랙이면 조정이 완료됩니다.
} else if (sibling->left->color == RBTREE_BLACK && sibling->right->color == RBTREE_BLACK) { // case 3. (형제 노드는 블랙) 형제 노드의 왼쪽 자식은 레드, 오른쪽 자식은 블랙인 경우
sibling->left->color = RBTREE_BLACK;
sibling->color = RBTREE_RED;
left_rotate(tree, sibling);
sibling = replaced_node->parent->left; // 새로운 형제가 설정되고, case 4로 변환됩니다.
}
// case 4. case2의 일부를 제외하고 모든 case는 case4로 귀결됩니다.
sibling->color = replaced_node->parent->color;
replaced_node->parent->color = RBTREE_BLACK;
sibling->left->color = RBTREE_BLACK;
right_rotate(tree, replaced_node->parent);
replaced_node = tree->root;
}
}
replaced_node->color = RBTREE_BLACK;
}
// 트리에서 특정 노드를 삭제하는 함수입니다.
int rbtree_erase(rbtree *tree, node_t *target_node)
{
if (!tree) {
print_message(TREE_LOAD_FAILED);
return -1;
}
if (!target_node) {
print_message(NODE_LOAD_FAILED);
return -1;
}
node_t *successor = target_node;
node_t *replaced_node;
color_t successor_original_color = successor->color;
if (target_node->left == tree->nil) { // 삭제할 노드의 왼쪽 자식이 nil이면
replaced_node = target_node->right; // 오른쪽 자식을 대체 노드로 설정합니다.
rbtree_transplant(tree, target_node, target_node->right); // 노드를 삭제하고 부모-자식 관계를 재설정합니다.
} else if (target_node->right == tree->nil) { // 삭제할 노드의 오른쪽 자식이 nil이면
replaced_node = target_node->left; // 왼쪽 자식을 대체 노드로 설정합니다.
rbtree_transplant(tree, target_node, target_node->left); // 노드를 삭제하고 부모-자식 관계를 재설정합니다.
} else { // 삭제할 노드에 모두 자녀가 있으면
successor = rbtree_min_in_subtree(tree, target_node->right); // 후계자를 선정합니다.
successor_original_color = successor->color; // 후계자의 색상을 저장합니다.
replaced_node = successor->right; // 후계자가 기존 노드를 올라간 후 후계자의 자식을 저장합니다.
if (successor->parent == target_node) {
replaced_node->parent = successor;
} else { // 후계자가 바로 삭제할 노드를 대체하지 못하는 경우
rbtree_transplant(tree, successor, replaced_node); // 후계자의 위치를 대체 노드가 차지하게 됩니다.
successor->right = target_node->right;
successor->right->parent = successor;
}
// 삭제할 노드의 위치에 후계자를 배치합니다.
rbtree_transplant(tree, target_node, successor);
successor->left = target_node->left;
successor->left->parent = successor;
successor->color = target_node->color;
}
free(target_node);
target_node = NULL;
if (successor_original_color == RBTREE_BLACK) {
rbtree_erase_fixup(tree, replaced_node);
}
return 1;
}
// 트리를 전위 순회하는 재귀 함수입니다.
void inorder_recursion(const node_t *node, key_t *arr, size_t *index, const node_t *nil)
{
if (node == nil) {
return;
}
inorder_recursion(node->left, arr, index, nil);
arr[(*index)++] = node->key;
inorder_recursion(node->right, arr, index, nil);
}
// 트리를 전위 순회하여 배열에 삽입하는 함수입니다.
int rbtree_to_array(const rbtree *tree, key_t *arr, const size_t n)
{
if (!tree || !arr) {
return -1;
}
size_t index = 0;
inorder_recursion(tree->root, arr, &index, tree->nil);
if (index != n) {
return -1;
}
return 0;
}CSAPP 6. 메모리 계층구조
RB Tree 제출할 정도로 구현 끝.
나태해질 것 같으니까.. 자투리 시간에 CSAPP 6장 빠르게 훑어보기!
레지스터는 0 사이클로 접근 가능
캐시는 4~75 사이클
메인 메모리는 수 백 사이클
디스크는 수 천만 사이클
6.1 저장장치 기술
초기 컴퓨터의 램은 겨우 몇 킬로바이트
최초의 PC는 하드 디스크도 없었음.
1982년 10메가 바이트 디스크(하드디스크)
6.1.1 랜덤 접근 메모리
1. 정적 램(SRAM)
- 동적램보다 훨씬 빠르고 더 비쌈.
- 캐시 메모리로 사용
- 일반적인 데스트톱에서 수십 메가
- 이중안정 메모리 셀에 비트를 저장
- 각 셀은 여섯 개의 트랜지스터 회로로 구성
- 전원 공급되는 한 무한히 유지, 외란(외부환경 방해요인: 빛, 전기적 잡음)에도 안정적임
- 트랜지스터를 더 많이 사용하므로 집적도가 낮고, 비싸고, 전력 소모가 많음.
2. 동적 램(DRAM)
- 메인메모리
- 그래픽 시스템 프레임 버퍼
- 일반적인 데스트톱에서 수천 메가
- 비트를 전하로 캐패시터에 저장
- 각 셀은 캐패시티 하나, 접근 트랜지스터 하나로 구성
- 외란(외부환경 방해요인)에 민감
- 햇볕에 노출되면 캐패시터 전압이 변함 -> 회복 불가
- 디카, 캠코더 센서는 실질적으로 DRAM 셀 배열임.
- 시간이 지나면 전하가 누수되며, 주기적으로 메모리의 모든 비트를 읽었다가 다시 써 주는 방식으로 리프레시 해야 한다.
- 트랜지스터를 더 적게 사용하므로 집적도가 높고, 싸고, 전력 소모가 적음.
3. 일반 DRAM
램은 2차원 배열 형태로 되어 있다.(행, 열)
그래서 비트를 전송할 때 행 주소와 열 주소를 차례로 보낸다.
2차원 배열 형태로 구성하는 이유는 핀 주소를 절반으로 줄일 수 있음.
(선형 배열 형태로 구성했다면 핀 수가 2배로 늘어 남.)
