자료구조, Binary Search Tree
Binary Search Tree
📌 BST란?
트리 자료구조의 한 종류
부모노드보다 작은 값은 왼쪽 자식 노드에, 부모노드보다 큰 값은 오른쪽 자식 노드에 저장하는 방식으로 데이터 저장
📌 장점
- 탐색, 삽입, 삭제 연산 시 시간복잡도 O(log n)
- 최대 2개의 자식 노드를 가지므로 이진 탐색 트리에서 데이터를 탐색할 때 절반 이하의 노드를 탐색한다.
- 데이터가 정렬된 상태를 유지하므로 중위순회(왼쪽서브노드 → 루트 → 오른쪽서브노드)하면 오름차순으로 정렬된 값을 얻을 수 있다.
📌 단점
- 이상적인 BST 모양이 아닐 경우(균형잡힌 이진 탐색트리) 경우, 시간 복잡도가 O(n)에 수렴한다.
이러한 최악의 경우를 피하기 위해,
데이터를 삽입할 때마다 트리의 균형을 잡기 위해 균형 조절 알고리즘(AVL, Red-Black 등)을 사용해 이를 개선할 수 있다.
✏️ 노드 생성
왼쪽 서브트리를 가르키는 포인터부 left, 오른쪽 서브트리를 가르키는 포인터부 right, 그리고 int형 데이터를 가지는 노드 구조체(붕어빵틀)를 만든다.
typeof를 이용해 struct node를 Node라는 별칭으로 간단히 사용할 수 있다.
새로운 노드를 생성하는 함수를 만든다.
동적메모리에 integer(4byte) + pointer(4byte)*2 = 12byte를 할당해 노드를 생성한다.
생성된 노드는 자식노드가 있을지 없을지 모르므로 초기값은 NULL을 할당해 준다.
✏️ BST에 노드를 삽입하는 함수
삽입은 간단하다.
그냥 root노드보다 작으면 왼쪽 서브노드와 이어지도록 재귀적으로 타고타고 들어간다.
root노드보다 크면 오른쪽 서브노드와 이어지도록 재귀적으로 타고타고 들어간다.
✏️ BST에서 노드를 삭제하는 함수
일단 삭제하려는 노드를 재귀적으로 탐색해 해당 노드 삭제해준다.
그리고 3가지 케이스로 나뉜다.
- Case1. 삭제 하려는 노드의 자식노드가 없는 경우
- Case2. 삭제 하려는 노드의 자식노드가 1개인 경우
- Case3. 삭제 하려는 노드의 자식노드가 2개인 경우
✏️ Case1. 삭제 하려는 노드의 자식노드가 없는 경우
삭제 하려는 노드의 자식 노드가 없을 경우에는 그 노드의 메모리 할당을 해제해 삭제해주고 NULL 반환해주면 된다.
BST :
1
3
4
6
7
8
10
13
14
BST after node 1 deletion(Case1) :
3
4
6
7
8
10
13
14
✏️ Case2. 삭제 하려는 노드의 자식노드가 1개인 경우
삭제하려는 노드의 자식이 1개인 경우, 자식노드를 가리키는 포인터값을 temp에 저장해주고 해당 노드를 삭제한다.
그후 temp를 반환해주면 조상노드와 자식노드가 연결되어 BST규칙에 어긋나지 않게 노드를 삭제할 수 있다.
BST :
1
3
4
6
7
8
10
13
14
BST after node 1 deletion(Case1) :
3
4
6
7
8
10
13
14
BST after node 14 deletion(Case2) :
3
4
6
7
8
10
13
✏️ Case3. 삭제 하려는 노드의 자식노드가 2개인 경우
삭제하려는 노드의 자식 노드가 2개인 경우, 조금 복잡하다
왼쪽 서브트리의 가장 큰 값 또는 오른쪽 서브트리의 가장 작은값와 교체해주면 BST 규칙에 어긋나지 않고 최소한의 이동으로 노드를 교체할 수 있다.
해당 코드는 오른쪽 서브트리의 가장 큰값과 루트 노드를 교체한 코드이다.
루트의 오른쪽서브트리의 왼쪽서브트리가 NULL값이 아닐 때 까지(끝까지) 탐색한다.
탐색이 끝나면, 그 값이 오른쪽 서브트리 전체의 최솟값(min_right)이 될 것이다.
그럼 그 값을 root로 설정해주고
오른쪽 서브트르에서 min_right 데이터를 삭제해주면 된다.
BST :
1
3
4
6
7
8
10
13
14
BST after node 1 deletion(Case1) :
3
4
6
7
8
10
13
14
BST after node 14 deletion(Case2) :
3
4
6
7
8
10
13
BST after node 8 deletion(Case3) :
3
4
6
7
10
13
기존 루트 8이 오른쪽 서브노드의 가장 작은값 10와 교체된 걸 확인할 수 있다.
📄 BST.c
#include <stdio.h>
#include <stdlib.h>
// typeof 자료형에 새로운 이름을 부여하는 키워드
// sturct node를 'Node' 라는 새로운 자료형으로 정의 함
typedef struct node
{
int data;
struct node *left; // 왼쪽 서브트리를 가리키는 포인터
struct node *right; // 오른쪽 서브트리를 가리키는 포인터
} Node;
// 새로운 노드 생성 함수
Node* createNode(int data)
{
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// BST에 노드 삽입하는 함수
Node *insert(Node *root, int data)
{
// BST가 비어있으면 삽입하는 노드가 root 노드가 됨.
if (root == NULL)
{
root = (Node*)malloc(sizeof(Node));
root->data = data;
root->left = NULL;
root->right = NULL;
return root;
}
// BST가 비어 있지 않다면, 크기를 비교해 재귀적으로 삽입
// 루트노드보다 작다면, 왼쪽 서브트리쪽으로 노드 연결됨.
if (data < root->data)
{
root->left = insert(root->left, data);
}
// 루트노드보다 크다면, 오른쪽 서브트리쪽으로 노드가 연결됨.
else{
root->right = insert(root->right, data);
}
return root; // root 노드가 반환되면 BST 전체 구조가 반환됨.
}
// BST에서 노드 삭제하는 함수
Node *delete(Node *root, int data)
{
// 삭제하려는 데이터가 BST에 없는 경우, NULL값 반환
if (root == NULL)
{
return NULL;
}
// 삭제하려는 데이터가 root보다 작으면
// 왼쪽 서브트리가 root값이 되면서 재귀적 탐색
if (data < root->data)
{
root->left = delete(root->left, data);
}
// 삭제하려는 데이터가 root보다 크면
// 오른쪽 서브트리가 root값이 되면서 재귀적 탐색
else if (data > root->data)
{
root->right = delete(root->right, data);
}
else {
// Case1. 삭제 하려는 데이터의 자식 노드가 없는 경우
if (root->left == NULL && root->right == NULL)
{
free(root); // 삭제하려는 데이터의 메모리 할당을 해제해 그냥 삭제
return NULL; // NULL값을 리턴해준다.
}
// Case2. 삭제 하려는 데이터의 자식 노드가 1개인 경우
else if (root->left == NULL)
{
Node *temp = root->right; // 삭제하려는 노드의 오른쪽 자식을 가리키는 주소값을 temp에 저장
free(root); // 삭제하려는 노드의 메모리 할당 해제
return temp; // 자식노드의 메모리 주소값을 return함으로 써 연결을 변경해준다.
}
else if (root->right == NULL)
{
Node *temp = root->left; // 삭제하려는 노드의 오른쪽 자식을 가리키는 주소값을 temp에 저장
free(root); // 삭제하려는 노드의 메모리 할당 해제
return temp; // 자식노드의 메모리 주소값을 return함으로 써 연결을 변경해준다.
}
// Case3. 삭제하려는 데이터의 자식 노드가 2개인 경우
else
{
// 오른쪽 서브트리의 가장 작은 값을 탐색
Node *min_right = root->right;
while (min_right->left != NULL)
{
min_right = min_right->left;
}
// 그 값을 root값으로 설정!
root->data = min_right->data;
// 오른쪽 서브트리에서 min_right(가장 작은 값) 삭제
root->right = delete(root->right, min_right->data);
}
}
return root;
}
// BST 를 중위 순회하며 값을 출력하는 함수
void print(Node *node, int level)
{
if (node == NULL)
{
return;
}
print(node->left, level + 1);
for(int i = 0; i < level; i++)
{
printf(" ");
}
printf("%d\n", node->data);
print(node->right, level + 1);
}
int main()
{
Node *root = NULL;
// BST에 값을 삽입
root = insert(root, 8);
root = insert(root, 3);
root = insert(root, 10);
root = insert(root, 1);
root = insert(root, 6);
root = insert(root, 4);
root = insert(root, 7);
root = insert(root, 14);
root = insert(root, 13);
// BST 출력
printf("BST : \n");
print(root, 0);
printf("\n");
// BST에서 5, 15, 18 삭제
root = delete(root, 1);
// BST 출력
printf("BST after node 1 deletion(Case1) : \n");
print(root, 0);
printf("\n");
root = delete(root, 14);
// BST 출력
printf("BST after node 14 deletion(Case2) : \n");
print(root, 0);
printf("\n");
root = delete(root, 8);
// BST 출력
printf("BST after node 8 deletion(Case3) : \n");
print(root, 0);
printf("\n");
}
'알고리즘' 카테고리의 다른 글
자료구조, rbtree insert (0) | 2023.04.06 |
---|---|
자료구조, AVL Left-Rotate & Right-Rotate 구현 (0) | 2023.04.04 |
자료 구조, Linked List (0) | 2023.04.02 |
재귀함수, 하노이의 탑 (0) | 2023.03.07 |
DFS 관련 연산 문제 (0) | 2023.03.07 |