Chater 6-2 이진 탐색 트리(Binary Search Tree)
카테고리: DataStructure2
태그: C Data Structure Algorithm
홍정모 교수님의 강의 홍정모의 따라하며 배우는 C언어(부록) 를 듣고 정리한 필기입니다. 😀
ppt 캡처는 모두 교수님 강의에서 캡처한 것임을 밝힙니다.
Chapter 6. Binary Search
🚀 이진 탐색 트리란?
🔥 삭제
삭제의 경우 내가 기존에 알고 있던 이진 탐색 트리의 삭제 방식과 강의에서 소개한 삭제 방식과 달랐다. 아래는 강의에서 소개한 삭제 방식이다.
- 삭제한 노드의 왼쪽 자식 을
- 삭제한 노드의 부모와 연결
- 삭제한 노드의 오른쪽 자식 을
- 삭제한 노드의 왼쪽 자식 서브르티 에서 오른쪽 자식이 없는 노드의 오른쪽 자식으로서 가장 끝에 연결
🚀 이진 탐색 트리 구현 코드
📜 tree.h
#define TMAX 40
typedef struct {
char character[TMAX];
char name[TMAX];
}Item;
#define MAXITEMS 20
typedef struct node{
Item item;
struct node* left;
struct node* right;
}Node;
typedef struct tree {
Node* root;
int size;
}Tree;
void InitializeTree(Tree* ptree, int(comp_func)(const Item item1, const Item item2));
bool TreeIsEmpty(const Tree* ptree);
bool TreeIsFull(const Tree* ptree);
int TreeItemCount(const Tree* ptree);
bool AddItem(const Item* pi, Tree* ptree);
bool InTree(const Item* pi, const Tree* ptree);
bool DeleteItem(const Item* pi, Tree* ptree);
void Traverse(const Tree* ptree, void (*pfun)(Item item));
void DeleteAll(Tree* ptree);
Item* TreeSearch(Tree* tree, const Item key);
📜 tree.c
typedef struct pair {
Node* parent;
Node* child;
} Pair;
/* tree.c 안에서만 사용할 수 잇는 static 함수 및 변수들 */
static int(*compare_func)(const Item item1, const Item item2) = NULL;
// Item으로 노드 생성
static Node* MakeNode(const Item* pi)
{
Node* new_node;
new_node = (Node*)malloc(sizeof(Node));
if (new_node != NULL) {
new_node->item = *pi;
new_node->left = NULL;
new_node->right = NULL;
}
else {
printf("Malloc() failed.\n");
exit(1);
}
return new_node;
}
// root 를 루트로 하는 서브트리에 new_node 를 자식으로 추가
static void AddNode(Node* new_node, Node* root)
{
int comp = compare_func(new_node->item, root->item);
if (comp == 0) {
printf("Cannot add a duplicated item.\n");
free(new_node);
return;
}
else if (comp < 0) {
if (root->left == NULL)
root->left = new_node;
else
AddNode(new_node, root->left); // recursion
}
else {
if (root->right == NULL)
root->right = new_node;
else
AddNode(new_node, root->right); // recursion
}
}
// root 를 루트로 하는 서브트리를 중위 순회
static void InOrder(const Node* root, void (*pfun)(Item item))
{
if (root == NULL)
return;
InOrder(root->left, pfun); // recursion
(*pfun)(root->item); // 출력 (pfun 함수 실행)
InOrder(root->right, pfun); // recursion
}
// 찾고자 하는 아이템의 부모와 자식노드 리턴
static Pair SeekItem(const Item* pi, const Tree* ptree)
{
Pair look;
look.parent = NULL;
look.child = ptree->root;
if (look.child == NULL)
return look;
while (look.child != NULL) {
int comp = compare_func(*pi, look.child->item);
if (comp < 0) {
look.parent = look.child;
look.child = look.child->left;
}
else if (comp > 0) {
look.parent = look.child;
look.child = look.child->right;
}
else if (comp == 0)
break;
}
return look;
}
// 노드 삭제 (3가지 케이스)
static void DeleteNode(Node** ptr)
{
Node* temp;
if ((*ptr)->left == NULL) {
temp = *ptr;
*ptr = (*ptr)->right;
free(temp);
}
else if ((*ptr)->right == NULL) {
temp = *ptr;
*ptr = (*ptr)->left;
free(temp);
}
else { // 자식이 왼쪽 오른쪽 둘 다 있는 노드의 삭제
// find where to reattach right subtree
for (temp = (*ptr)->left; temp->right != NULL; temp = temp->right)
continue;
temp->right = (*ptr)->right;
temp = *ptr;
*ptr = (*ptr)->left;
free(temp);
}
}
// root 를 루트로 하는 서브트리의 모든 노드 삭제
static void DeleteAllNodes(Node* root)
{
if (root == NULL)
return;
// 중위 순회
Node* pright = root->right;
DeleteAllNodes(root->left); // recursion
free(root);
DeleteAllNodes(pright); // recursion
}
// root 를 루트로 하는 서브트리에서 key 아이템을 가진 노드 찾기 (이진 탐색)
static Item* Search(Node* root, const Item key)
{
if (root == NULL)
return NULL;
int comp = compare_func(key, root->item);
if (comp == 0)
return &root->item;
else if (comp < 0)
return Search(root->left, key); // recursion
else if (comp > 0)
return Search(root->right, key); // recursion
}
/* tree.h 함수들 정의 */
// ptree 트리 초기화
void InitializeTree(Tree* ptree, int(comp_func)(const Item item1, const Item item2))
{
ptree->root = NULL;
ptree->size = 0;
compare_func = comp_func; // 트리에 적용할 비교 함수
}
// ptree 트리가 비었는지
bool TreeIsEmpty(const Tree* ptree)
{
if (ptree->root == NULL)
return true;
else
return false;
}
// ptree 트리가 꽉 찼는지
bool TreeIsFull(const Tree* ptree)
{
if (ptree->size == MAXITEMS)
return true;
else
return false;
}
// ptree 트리에 몇 개 노드가 있는지
int TreeItemCount(const Tree* ptree)
{
return ptree->size;
}
// ptree 트리에 아이템 추가 (노드 생성, 노드 추가)
bool AddItem(const Item* pi, Tree* ptree)
{
if (TreeIsFull(ptree)) {
printf("Cannot add more items.\n");
return false;
}
Node* new_node = MakeNode(pi);
ptree->size++;
if (ptree->root == NULL)
ptree->root = new_node;
else
AddNode(new_node, ptree->root);
return true;
}
// ptree 트리 중위에 해당 아이템이 있는지 확인
bool InTree(const Item* pi, const Tree* ptree)
{
return (SeekItem(pi, ptree).child == NULL) ? false : true;
}
// ptree 트리의 해당 아이템 삭제 (찾고 노드 삭제)
bool DeleteItem(const Item* pi, Tree* ptree)
{
Pair look;
look = SeekItem(pi, ptree);
if (look.child == NULL)
return false;
if (look.parent == NULL)
DeleteNode(&ptree->root);
else if (look.parent->left == look.child)
DeleteNode(&look.parent->left);
else
DeleteNode(&look.parent->right);
ptree->size--;
return true;
}
// 중위 순회하며 노드마다 pfun 함수 적용
void Traverse(const Tree* ptree, void (*pfun)(Item item))
{
if (ptree != NULL)
InOrder(ptree->root, pfun);
}
// ptree 트리의 모든 노드 삭제
void DeleteAll(Tree* ptree)
{
if (ptree == NULL)
return;
DeleteAllNodes(ptree->root);
ptree->root = NULL;
ptree->size = 0;
}
// ptree 에서 key 아이템 가진 노드 찾기
Item* TreeSearch(Tree* tree, const Item key)
{
return Search(tree->root, key);
}
📜 main.c
#include <stdio.h>
#include <string.h>
#include "tree.h"
#define SPACING 30
// 비교 함수
int compare(const Item first, const Item second)
{
return strcmp(first.character, second.character);
}
// 아이템의 캐릭터 + 이름 출력 (어벤저스 캐릭터명 + 실명)
void print_item(Item item)
{
printf("%s (%s)\n", item.character, item.name);
}
// 트리 모양으로 출력
void print2DUtil(Node* root, int space)
{
space += SPACING;
if (root == NULL) {
for (int i = SPACING; i < space; ++i)
printf(" ");
printf("NULL");
return;
}
print2DUtil(root->right, space); // recursion
printf("\n");
for(int i = SPACING; i < space; ++i)
printf(" ");
print_item(root->item);
print2DUtil(root->left, space); // recursion
}
// "전위 순회" 방식으로 root 트리의 노드들 출력
void print_node(Node* root, int level)
{
if (root == NULL)
return;
printf("%s (%s) -> ", root->item.character, root->item.name);
if (root->left == NULL)
printf("NULL, ");
else
printf("%s (%s), ", root->left->item.character, root->left->item.name);
if (root->right == NULL)
printf("NULL, ");
else
printf("%s (%s), ", root->right->item.character, root->right->item.name);
printf("\n");
print_node(root->left, level + 1); // recursion
print_node(root->right, level + 1); // recursion
}
void print_tree(Tree* ptree)
{
printf("\n----------------------\n");
Traverse(ptree, print_item);
printf("\n----------------------\n");
print2DUtil(ptree->root, 0);
printf("\n----------------------\n");
print_node(ptree->root, 0);
}
int main()
{
Item items[] = {
{"Iron Man", "Tony Stark"},
{"Thor", "Thor Odinson"},
{"Ant-Man", "Hank Pym"},
{"Wasp", "Janet van Dyne"},
{"Hulk", "Bruce Banner"},
{"Captain America", "Steve Rogers"},
{"Scarlet Witch", "Wanda Maximoff"},
{"Black Widow", "Natacha Romanoff"},
{"Dr. Strange", "Stephen Strange"},
{"Daredevil", "Matthew Murdock"},
{"Punisher", "Frank Castle"},
{"Batman", "Bruce Wayne"}
};
int n = sizeof(items) / sizeof(items[0]);
Tree tree;
InitializeTree(&tree, &compare);
for (int i = 0; i < n; ++i)
AddItem(&items[i], &tree);
AddItem(&items[2], &tree);
print_tree(&tree);
Item key = { "Punisher", "" };
Item* result = TreeSearch(&tree, key);
if (result == NULL)
printf("\nSearch failed.\n");
else
printf("\n%s is the %s\n", result->name, result->character);
/* Deleting tests */
{
Item key = { "Iron Man", "" };
DeleteItem(&key, &tree);
print_tree(&tree);
}
}
💎출력💎
Cannot add a duplicated item.
----------------------
Ant-Man (Hank Pym)
Batman (Bruce Wayne)
Black Widow (Natacha Romanoff)
Captain America (Steve Rogers)
Daredevil (Matthew Murdock)
Dr. Strange (Stephen Strange)
Hulk (Bruce Banner)
Iron Man (Tony Stark)
Punisher (Frank Castle)
Scarlet Witch (Wanda Maximoff)
Thor (Thor Odinson)
Wasp (Janet van Dyne)
----------------------
NULL
Wasp (Janet van Dyne)
NULL
Thor (Thor Odinson)
NULL
Scarlet Witch (Wanda Maximoff)
NULL
Punisher (Frank Castle)
NULL
Iron Man (Tony Stark)
NULL
Hulk (Bruce Banner)
NULL
Dr. Strange (Stephen Strange)
NULL
Daredevil (Matthew Murdock)
NULL
Captain America (Steve Rogers)
NULL
Black Widow (Natacha Romanoff)
NULL
Batman (Bruce Wayne)
NULL
Ant-Man (Hank Pym)
NULL
----------------------
Iron Man (Tony Stark) -> Ant-Man (Hank Pym), Thor (Thor Odinson),
Ant-Man (Hank Pym) -> NULL, Hulk (Bruce Banner),
Hulk (Bruce Banner) -> Captain America (Steve Rogers), NULL,
Captain America (Steve Rogers) -> Black Widow (Natacha Romanoff), Dr. Strange (Stephen Strange),
Black Widow (Natacha Romanoff) -> Batman (Bruce Wayne), NULL,
Batman (Bruce Wayne) -> NULL, NULL,
Dr. Strange (Stephen Strange) -> Daredevil (Matthew Murdock), NULL,
Daredevil (Matthew Murdock) -> NULL, NULL,
Thor (Thor Odinson) -> Scarlet Witch (Wanda Maximoff), Wasp (Janet van Dyne),
Scarlet Witch (Wanda Maximoff) -> Punisher (Frank Castle), NULL,
Punisher (Frank Castle) -> NULL, NULL,
Wasp (Janet van Dyne) -> NULL, NULL,
Frank Castle is the Punisher
----------------------
Ant-Man (Hank Pym)
Batman (Bruce Wayne)
Black Widow (Natacha Romanoff)
Captain America (Steve Rogers)
Daredevil (Matthew Murdock)
Dr. Strange (Stephen Strange)
Hulk (Bruce Banner)
Punisher (Frank Castle)
Scarlet Witch (Wanda Maximoff)
Thor (Thor Odinson)
Wasp (Janet van Dyne)
----------------------
NULL
Wasp (Janet van Dyne)
NULL
Thor (Thor Odinson)
NULL
Scarlet Witch (Wanda Maximoff)
NULL
Punisher (Frank Castle)
NULL
Hulk (Bruce Banner)
NULL
Dr. Strange (Stephen Strange)
NULL
Daredevil (Matthew Murdock)
NULL
Captain America (Steve Rogers)
NULL
Black Widow (Natacha Romanoff)
NULL
Batman (Bruce Wayne)
NULL
Ant-Man (Hank Pym)
NULL
----------------------
Ant-Man (Hank Pym) -> NULL, Hulk (Bruce Banner),
Hulk (Bruce Banner) -> Captain America (Steve Rogers), Thor (Thor Odinson),
Captain America (Steve Rogers) -> Black Widow (Natacha Romanoff), Dr. Strange (Stephen Strange),
Black Widow (Natacha Romanoff) -> Batman (Bruce Wayne), NULL,
Batman (Bruce Wayne) -> NULL, NULL,
Dr. Strange (Stephen Strange) -> Daredevil (Matthew Murdock), NULL,
Daredevil (Matthew Murdock) -> NULL, NULL,
Thor (Thor Odinson) -> Scarlet Witch (Wanda Maximoff), Wasp (Janet van Dyne),
Scarlet Witch (Wanda Maximoff) -> Punisher (Frank Castle), NULL,
Punisher (Frank Castle) -> NULL, NULL,
Wasp (Janet van Dyne) -> NULL, NULL,
D:\aaaaastudy\CStudy\Debug\onlyc.exe(프로세스 10764개)이(가) 종료되었습니다(코드: 0개).
이 창을 닫으려면 아무 키나 누르세요...
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글 남기기