C언어 기초
균형 이진 탐색 트리(Binary Search Tree)
RB Tree(Red Black Tree) </aside>
C언어 기초
-
포인터
포인터는 어떤 변수가 메모리상에 데이터를 담고 있을때 그 변수의 메모리상의 주소를 나타낸다. 포인터를 통해 여러가지 작업을 할 수 있다. 역참조를 통해 데이터를 바꿔줄 수도 있고 배열을 나타낼 수 있다. 또한 구조체와 함께 사용하여 연결리스트를 표현 할 수도 있다. 연결리스트는 트리와 같은 자료구조에 매우 유용하다. 또한 포인터를 통해 함수를 호출 가능하다. 포인터를 사용하는 몇 가지 예시를 보면 다음과 같다.
#include <stdio.h> int main() { int *numPtr; // 포인터 변수 선언 int num1 = 10; // 정수형 변수를 선언하고 10 저장 numPtr = &num1; // num1의 메모리 주소를 포인터 변수에 저장 *numPtr = 20; // 역참조 연산자로 메모리 주소에 접근하여 20을 저장 printf("%d\\n", *numPtr); // 20: 역참조 연산자로 메모리 주소에 접근하여 값을 가져옴 printf("%d\\n", num1); // 20: 실제 num1의 값도 바뀜 return 0; }위 코드는 아래 이미지를 보면서 이해했다.
포인터는 또한 이중, 삼중으로 사용 가능하다. 이를 통해 2차원 배열이나 3차원 배열을 구현한다.
#include <stdio.h> #include <stdlib.h> // malloc, free 함수가 선언된 헤더 파일 int main() { int **m = malloc(sizeof(int *) * 3); // 이중 포인터에 (int 포인터 크기 * 세로 크기)만큼 // 동적 메모리 할당. 배열의 세로 for (int i = 0; i < 3; i++) // 세로 크기만큼 반복 { m[i] = malloc(sizeof(int) * 4); // (int 크기 * 가로 크기)만큼 동적 메모리 할당. // 배열의 가로 } m[0][0] = 1; // 세로 인덱스 0, 가로 인덱스 0인 요소에 값 할당 m[2][0] = 5; // 세로 인덱스 2, 가로 인덱스 0인 요소에 값 할당 m[2][3] = 2; // 세로 인덱스 2, 가로 인덱스 3인 요소에 값 할당 printf("%d\\n", m[0][0]); // 1: 세로 인덱스 0, 가로 인덱스 0인 요소의 값 출력 printf("%d\\n", m[2][0]); // 5: 세로 인덱스 2, 가로 인덱스 0인 요소의 값 출력 printf("%d\\n", m[2][3]); // 2: 세로 인덱스 2, 가로 인덱스 3인 요소의 값 출력 for (int i = 0; i < 3; i++) // 세로 크기만큼 반복 { free(m[i]); // 2차원 배열의 가로 공간 메모리 해제 } free(m); // 2차원 배열의 세로 공간 메모리 해제 return 0; }2중 포인터를 사용하여 배열을 구현한 코드이다. 이를 그림으로 나타내면 다음과 같다.
우선 int **m은 int의 포인터를 가르키는 포인터이다. 말장난 같지만 위의 그림을 같이 본다면 이해가 갈것이다. malloc으로 int*형 사이즈의 3배 만큼 메모리 할당을 한다. 그리고 각각의 m[i]에 대해 int형 사이즈의 4배남큼 메모리 할당을 한 후 그 위치에 값을 넣으면 배열처럼 사용 할 수 있다. 실제 메모리에서는 진짜 행렬처럼 할당되지는 않고 그저 연결만 되어있다.
1. int *p[13] 2. int *(p[13]) 3. int (*p)[13] 4. int *f()포인터의 표현법은 정말 많지만 간단한 예시는 위와 같다. 연산자의 우선순위를 찾아보면 포인터의 우선순위는 행렬, 함수보다 아래이다. 따라서 위의 예시나 복잡한 표현식을 해석할 때는 변수의 좌우를 살피고 연산자 우선순위가 높은 것부터 할당한다.
왼쪽은 1번과 2번의 경우이고 오른쪽은 3번의 경우이다. 왼쪽의 경우 p는 행렬의 첫번째 원소의 주소(행렬이름)이다. 그래서 행렬 안에는 포인터들이 들어있다. 반면 오른쪽 경우는 포인터 p가 int형 13개를 포함한 행렬의 첫번째 원소를 가르킨다. 괄호 하나로 자료형이 달라지므로 잘 살펴보아야 한다.
-
구조체
구조체는 파이썬에서 클래스와 유사하다. 구조체 안에 어떤 자료형이든 할당 할 수 있다. 포인터로 접근 할 시 →를 사용한다. 아래 예시를 보면 잘 이해할 수 있다.
#include <stdio.h> #include <string.h> // strcpy 함수가 선언된 헤더 파일 #include <stdlib.h> // malloc, free 함수가 선언된 헤더 파일 typedef struct _Person { // 구조체 이름은 _Person char name[20]; // 구조체 멤버 1 int age; // 구조체 멤버 2 char address[100]; // 구조체 멤버 3 } Person; // typedef를 사용하여 구조체 별칭을 Person으로 정의 int main() { Person *p1 = malloc(sizeof(Person)); // 구조체 별칭으로 포인터 선언, 메모리 할당 // 화살표 연산자로 구조체 멤버에 접근하여 값 할당 strcpy(p1->name, "홍길동"); p1->age = 30; strcpy(p1->address, "서울시 용산구 한남동"); // 화살표 연산자로 구조체 멤버에 접근하여 값 출력 printf("이름: %s\\n", p1->name); // 홍길동 printf("나이: %d\\n", p1->age); // 30 printf("주소: %s\\n", p1->address); // 서울시 용산구 한남동 free(p1); // 동적 메모리 해제 return 0; }매번 struct를 기입하기 귀찮아서 별칭을 사용하는 경우가 많다. 또한 구조체의 크기만큼 메모리를 할당하여 새로운 구조체를 만들고 포인터 p1으로 역참조를 통해 값을 넣거나 참조를 통해 값을 불러올 수 있다.
-
연결리스트
위의 포인터와 구조체를 활용하면 연결 리스트를 구현 할 수 있다. 이것은 트리 구조의 자료형에서 많이 사용된다.
#include <stdio.h>
#include <stdlib.h> // malloc, free 함수가 선언된 헤더 파일
struct NODE { // 연결 리스트의 노드 구조체
struct NODE *next; // 다음 노드의 주소를 저장할 포인터
int data; // 데이터를 저장할 멤버
};
void addFirst(struct NODE *target, int data) // 기준 노드 뒤에 노드를 추가하는 함수
{
struct NODE *newNode = malloc(sizeof(struct NODE)); // 새 노드 생성
newNode->next = target->next; // 새 노드의 다음 노드에 기준 노드의 다음 노드를 지정
newNode->data = data; // 데이터 저장
target->next = newNode; // 기준 노드의 다음 노드에 새 노드를 지정
}
void removeFirst(struct NODE *target) // 기준 노드의 다음 노드를 삭제하는 함수
{
struct NODE *removeNode = target->next; // 기준 노드의 다음 노드 주소를 저장
target->next = removeNode->next; // 기준 노드의 다음 노드에 삭제할 노드의 다음 노드를 지정
free(removeNode); // 노드 메모리 해제
}
int main()
{
struct NODE *head = malloc(sizeof(struct NODE)); // 머리 노드 생성
// 머리 노드는 데이터를 저장하지 않음
head->next = NULL;
addFirst(head, 10); // 머리 노드 뒤에 새 노드 추가
addFirst(head, 20); // 머리 노드 뒤에 새 노드 추가
addFirst(head, 30); // 머리 노드 뒤에 새 노드 추가
removeFirst(head); // 머리 노드 뒤에 있는 노드를 삭제
struct NODE *curr = head->next;
// 연결 리스트 순회용 포인터에 첫 번째 노드의 주소 저장
while (curr != NULL) // 포인터가 NULL이 아닐 때 계속 반복
{
printf("%d\\n", curr->data); // 현재 노드의 데이터 출력
curr = curr->next; // 포인터에 다음 노드의 주소 저장
}
curr = head->next; // 연결 리스트 순회용 포인터에 첫 번째 노드의 주소 저장
while (curr != NULL) // 포인터가 NULL이 아닐 때 계속 반복
{
struct NODE *next = curr->next; // 현재 노드의 다음 노드 주소를 임시로 저장
free(curr); // 현재 노드 메모리 해제
curr = next; // 포인터에 다음 노드의 주소 저장
}
free(head); // 머리 노드 메모리 해제
return 0;
}
구조체 Node는 Node의 data(키값)과 다음 Node를 가르키는 next pointer를 가지고 있다. addFirst함수는 target 포인터와 데이터 값을 매개변수로 주어진다. 우선 새로운 노드가 생성되어야 하므로 malloc으로 newNode를 생성하고 newNode의 데이터와 next포인터가 가르켜야 할 곳을 지정해 준다.
반면 removeNode는 우선 target 노드가 없을때의 상황으로 포인터들을 연결해 준다. 그리고 메모리 누수가 일어나지 않도록 삭제한 노드를 free 시켜준다.
이 상황에서 구조체 안에 포인터 left,right가 있으면 트리구조의 구조체가 된다.
위의 코드 및 자료는 아래 사이트의 내용을 참고하였습니다.
균형 이진 탐색 트리
균형 이진 탐색 트리(Binary Search Tree)는 연결리스트에서 next포인터가 left, right로 두개이고 key값에 기반한 규칙 한가지가 추가된다. 가장 상위 부모를 루트노드라 하는데 루트 노드의 왼쪽 자식들은 모두 루트보다 key값이 작다. 반면 오른쪽 자식들은 모드 루트보다 큰 키값을 갖는다. 이런 규칙이 있기 때문에 특정 키값을 갖는 노드를 찾고 추가하는 속도가 매우 빠르다.
#include <stdio.h>
#include <stdlib.h>
typedef char data;
typedef struct _Node
{
int key;
struct _Node *left;
struct _Node *right;
}Node;
Node* searchNode(Node* root, char x)
{
Node* p = root;
while(p != NULL)
{
if(p->key == x)
return p;
else if (p->key > x)
p = p->left;
else
p = p->right;
}
return NULL;
}
Node* addNode(Node* root, char x)
{
Node* p = root;
Node* parent = NULL;
while(p != NULL)
{
parent = p;
if(p->key == x){
printf("이미 존재하는 노드입니다.\\n");
return p;
}
else if (p->key > x)
p = p->left;
else
p = p->right;
}
Node* addnode = (Node*)malloc(sizeof(Node));
addnode -> key = x;
addnode -> left = NULL;
addnode -> right = NULL;
if(parent != NULL)
{
if(parent->key > x)
parent->left = addnode;
else
parent->right = addnode;
}
return addnode;
}
Node* deleteNode(Node* root, int x)
{
Node* p = root;
Node* parent = NULL;
while((p!=NULL)&&(p->key != x))
{
parent = p;
if(p->key > x)
p = p->left;
else
p = p->right;
}
if(p==NULL){
printf("삭제하려는 노드는 존재하지 않습니다.");
return root; //메인에서 루트를 갱신하므로 루트를 반환해 주어야 한다
}
if((p->left == NULL)&&(p->right == NULL)){
if(parent->right == p)
parent->right = NULL;
else
parent->left = NULL;
}
else if ((p->left == NULL)||(p->right == NULL)){
Node* child = (p->right == NULL) ? p->left : p->right;
if(parent==NULL) //x가 root인 경우
root = child;
else{
if(parent->right == p)
parent->right = child;
else
parent->left = child;
}
}
else{
Node* succ = p->left;
Node* succ_parent = p;
while(succ->right != NULL){
succ_parent = succ;
succ = succ ->right;
}
p->key = succ->key;
if(succ_parent->right == succ)
succ_parent->right = succ->left;
else
succ_parent->left = succ->left;
p = succ;
}
free(p);
return root;
}
void inorder(Node* root)
{
if(root == NULL)
return;
inorder(root->left);
printf("%d ",root->key);
inorder(root->right);
}
int main(void)
{
Node* root = addNode(NULL,8);
addNode(root,2);
addNode(root,5);
addNode(root,9);
addNode(root,10);
addNode(root,7);
addNode(root,4);
addNode(root,12);
addNode(root,3);
addNode(root,6);
addNode(root,11);
addNode(root,13);
root = deleteNode(root,8);
inorder(root);
return 0;
}
세부 함수들을 살펴보면 다음과 같다.
-
searchNode
루트부터 시작하여 아래로 내려가며 키값을 탐색한다. 만약 찾고자 하는 값이 현재 노드의 키값보다 작으면 왼쪽으로 내려가고 반대의 경우에는 오른쪽으로 내려간다. 만약 키값이 같으면 목표를 달성했으므로 p를 반환하여 함수를 종료한다. 하지만 끝까지 내려가도 못찾은 경우에는 NULL을 반환한다.
-
addNode
추가는 트리의 맨 아래에 추가한다. 하지만 맨 아래 중 어느곳에 추가해야할지 결정해야한다. 우선 추가하려는 키값으로 기존 트리를 탐색한다. 만약 탐색중 키값이 일치하는 노드가 있다면 추가할 필요가 없으므로 함수를 종료시킨다.
-
deleteNode
삭제의 경우는 약간 복잡하다. 모든 노드는 3가지로 분류할 수 있다.
-
자식이 없는 경우(리프노드인 경우)
이 경우는 그냥 삭제해도 이진 트리구조를 해치지 않으므로 맘편히 삭제 한다.
-
자식이 1개인 경우
이 경우는 연결 리스트와 같이 삭제하려는 노드의 자식노드와 부모 노드를 이어주고 삭제한다.
-
자식이 2개인 경우
이 경우는 약간 복잡하다. 자식이 2개라는 것은 삭제하려는 노드가 루트인 이진트리(서브트리)를 이루고 있다는 것이다. 이진 트리 구조를 유지하기 위해 새로운 루트를 설정해 주어야 한다. 이때 계승자를 찾는다. 계승자는 보통 오른쪽 자식들 중 가장 작은 값을 찾는다. 이 계승자가 서브트리의 루트가 된다면 서브트리는 이진 트리 구조를 유지한다. 계승자는 삭제하려는 노드의 오른쪽 서브트리에 위치 하므로 왼쪽 서브트리보다 무조건 큰값이다. 그리고 오른쪽 서브트리의 최소값이므로 계승자가 루트가 되더라도 오른쪽 서브트리 값들보다 작다. 이때 삭제하려는 노드를 직접삭제하지 않고 계승자의 키값을 넣고 삭제는 계승자를 삭제한다. 이렇게 하면 연결관계를 덜 바꿔도 되서 간편하다.
-
-
inorder
이러한 이진 트리를 중위 순회하면 오름차순의 수열을 얻을 수 있다.
이러한 이진 검색 트리는 검색 및 삭제의 시간복잡도가 낮은 편이다. 하지만 최악의 케이스가 존재한다. 키값을 오름차순으로 추가하면 트리의 오른쪽에만 노드가 쌓여 시간 복잡도가 완전탐색과 다를바가 없다. 이러한 단점을 보완한 것이 Red Black Tree이다.
Red-Black Tree
RB 트리(Red-Black Tree)는 기본적으로 이진 검색 트리이다. 여기에 색 속성과 색에 대한 규칙을 추가하여 트리의 높이를 조절한다. 이진 검색 트리에 오름차순 값의 키를 추가하면 트리 높이가 계속 커지는데 RB 트리는 색 속성으로 인해 높이가 계속 커지지 않고 차곡차곡 쌓인다. 색 속성에 대한 규칙은 아래와 같다.
<aside> ❗ 새로운 규칙
-
모든 노드는 적색 혹은 흑색이다.
-
루트 노드는 흑색이다.
-
모든 리프(Nil)노드는 흑색이다.
-
적색 노드의 자식 노드는 모두 흑색이다. → 적색 노드는 연속할 수 없다.
-
각 노드에 대하여 해당 노드부터 리프노드까지의 최단경로에 속하는 흑색 노드 수는 일정하다.
</aside>
코드의 길이가 너무 길어서 아래 링크로 대신한다. 나는 경계노드(Nil)가 있는 방식으로 구현하였다.
https://github.com/Gn0lee/rbtree-lab.git
-
삽입 메커니즘
일단 RB트리도 이진검색 트리이므로 추가할 위치를 찾는다. 그리고 해당 위치에 노드를 추가하는데 일단 적색 노드로 추가한다. 만약 추가한 노드의 부모노드가 흑색이면 상관 없지만 적색일 경우 전체 트리의 색을 조정해 준다.
위의 경우 4와 5가 규칙 4에 위반한다. 규칙 4에 위반할 경우 삼촌노드(y)의 색에 따라 처리방법이 다르다. 위와 같이 삼촌이 적색일때는 부모 및 할아버지의 색을 바꾼다. 이것을 R-R을 위로 올린다고 표현한다. R-R을 위로 올렸지만 여전히 규칙 4에 위반한다. 이때 7의 삼촌 노드는 흑색이다. 이런 경우는 왼쪽으로 1회 회전 후 오른쪽으로 1회 회전한다. 회전하며 색 규칙에 맞게끔 색을 바꿔준다.
이런 식으로 R-R을 올리다 부모가 흑색이면 종료한다. 만약 루트까지 갔다면 루트를 흑색으로 바꾸고 종료한다.
-
삭제 메커니즘
느낀점 및 더 보아야 할 것