티스토리 뷰
주의 사항!
- 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
- 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
- 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.
이진 트리의 구조를 보면, 트리는 탐색에 효율적이라는 사실을 쉽게 알 수 있습니다. 이진 트리에 저장된 데이터의 수가 10억 개 수준에 이른다 해도 트리의 높이는 30을 넘지 않기 때문입니다.
예를 들어서 연결 리스트에 10억 개의 데이터가 저장되어 있다고 가정해 보겠습니다. 그리고 찾고자 하는 데이터가 이 리스트의 정중앙에 위치한다는 정보를 얻었다고 가정해 보겠습니다. 이는 분명 유용한 정보입니다. 하지만 이러한 정보를 가지고 있음에도 불구하고 데이터에 이르기 위해서는 약 5억 개의 노드를 지나야 합니다. 반면 이진 트리의 경우에는 해당 노드에 이르는 길을 알고 있다면 루트 노드에서부터 단말 노드에 이르기까지 총 30개의 노드를 지나는 과정에서 원하는 데이터를 찾을 수 있습니다.
이진 탐색 트리에서 중요한 것은 찾고자 하는 데이터를 가지는 노드에 이르는 경로를 찾는 것입니다. 따라서 이 경로를 쉽게 찾기 위해 이진 탐색 트리는 데이터를 저장하는 규칙을 가지고 있습니다. 쉽게 말해서 이진 트리에 데이터의 저장 규칙을 더한 것이 이진 탐색 트리입니다. 이진 탐색 트리의 특징은 다음과 같습니다.
- 이진 탐색 트리의 노드에 저장된 키는 유일하다
- 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다.
- 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다.
- 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.
위의 조건에 따라 이진 탐색 트리를 다음과 같이 표현할 수 있습니다.
노드 12를 기준으로 왼쪽 자식의 노드는 모두 보모 노드보다 작고, 오른쪽 자식 노드의 값은 모두 부모 노드의 값보다 큽니다. 여기에 15를 저장해 보겠습니다.
우선은 15와 루트 노드를 비교합니다. 비교하면 루트 노드인 12보다 15가 더 크므로 오른쪽 자식 노드로 이동합니다.
이번에는 15가 17보다 작습니다. 따라서 왼쪽 자식 노드로 이동합니다.
이번에는 13보다 15가 큽니다. 따라서 오른쪽 자식 노드로 이동합니다.
이동한 자식 노드가 비어 있으므로 해당 노드에 15를 저장하게 됩니다.
이렇듯 이진 탐색 트리는 '작으면 왼쪽, 크면 오른쪽으로'라는 원칙을 기준으로 데이터를 삽입합니다. 따라서 탐색의 과정에도 이를 그대로 따르면 됩니다.
이제 이진 탐색 트리를 직접 구현해 보겠습니다. 이진 탐색 트리는 이진 트리의 일종이므로 이진 트리를 이용해서 구현하게 됩니다. 따라서 우리는 이진 트리를 구현한 헤더 파일이 필요합니다. 이진 탐색 트리의 구현을 위해 사용할 이진 트리 헤더 파일과 소스 파일은 다음과 같습니다.
//BinaryTree.h 헤더 파일로 저장
#ifndef BINARYTREE_H
#define BINARYTREE_H
typedef int BTData;
typedef struct BTreeNode
{
BTData data;
struct BTreeNode* left;
struct BTreeNode* right;
} BTreeNode;
BTreeNode* MakeBTreeNode(void); //노드를 생성하고 그 주소 반환
BTData GetData(BTreeNode* bt); //노드의 데이터 반환
void SetData(BTreeNode* bt, BTData data); //노드에 데이터 저장
BTreeNode* GetLeftSubTree(BTreeNode* bt); //왼쪽 자식 노드의 데이터 반환
BTreeNode* GetRightSubTree(BTreeNode* bt); //오른쪽 자식 노드의 데이터 반환
void MakeLeftSubTree(BTreeNode* main, BTreeNode* sub); //왼쪽 자식 노드에 서브 트리 삽입
void MakeRightSubTree(BTreeNode* main, BTreeNode* sub); //오른족 자식 노드에 서브 트리 삽입
void DeleteTree(BTreeNode* bt); //해당 노드를 루트 노드로 가지는 트리 삭제
#endif//BinaryTree.c 소스 파일로 저장
#include "BinaryTree.h"
#include <stdlib.h>
#include <stdio.h>
BTreeNode* MakeBTreeNode(void)
{
BTreeNode* newNode = (BTreeNode*)malloc(sizeof(BTreeNode));
if (newNode == NULL)
{
printf("메모리 공간이 부족합니다.\n");
exit(1);
}
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
BTData GetData(BTreeNode* bt)
{
return bt->data;
}
void SetData(BTreeNode* bt, BTData data)
{
bt->data = data;
}
BTreeNode* GetLeftSubTree(BTreeNode* bt)
{
return bt->left;
}
BTreeNode* GetRightSubTree(BTreeNode* bt)
{
return bt->right;
}
void MakeLeftSubTree(BTreeNode* main, BTreeNode* sub)
{
DeleteTree(main->left);
main->left = sub;
}
void MakeRightSubTree(BTreeNode* main, BTreeNode* sub)
{
DeleteTree(main->right);
main->right = sub;
}
void DeleteTree(BTreeNode* bt)
{
if (bt != NULL)
{
if (bt->left != NULL)
{
DeleteTree(bt->left);
}
if (bt->right != NULL)
{
DeleteTree(bt->right);
}
free(bt);
}
}이제 이진 트리의 헤더 파일을 이용해서 이진 탐색 트리의 헤더 파일을 다음과 같이 정의합니다.
//BinarySearchTree.h 헤더 파일로 저장
#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H
#include "BinaryTree.h"
typedef BTData BSTData;
void BSTMakeAndInit(BTreeNode** pRoot); //BST의 생성 및 초기화
BSTData BSTGetNodeData(BTreeNode* bst); //노드에 저장된 데이터 반환
void BSTInsert(BTreeNode** pRoot, BSTData data); //BST를 대상으로 데이터 저장(노드의 생성 과정 포함)
BTreeNode* BSTSearch(BTreeNode* bst, BSTData target); //BST를 대상으로 데이터 탐색
#endif위 헤더 파일의 함수들을 구현하기 전에 다음과 같이 정의된 main 함수를 보고, 각 함수들이 어떻게 동작할지 예상해 봅니다.
//main.c 소스 파일로 저장
#include <stdio.h>
#include "BinarySearchTree.h"
int main(void)
{
BTreeNode* bstRoot;
BTreeNode* sNode;
BSTMakeAndInit(&bstRoot);
BSTInsert(&bstRoot, 1);
BSTInsert(&bstRoot, 2);
BSTInsert(&bstRoot, 3);
sNode = BSTSearch(bstRoot, 1);
if (sNode == NULL)
{
printf("탐색 실패!\n");
}
else
{
printf("탐색에 성공한 키의 값 : %d\n", BSTGetNodeData(sNode));
}
return 0;
}이제 이진 탐색 트리의 헤더 파일의 각 함수들을 구현해 보겠습니다.
//BinarySearchTree.c 소스 파일로 저장
#include "BinarySearchTree.h"
#include <stdio.h>
void BSTMakeAndInit(BTreeNode** pRoot)
{
*pRoot = NULL;
}
BSTData BSTGetNodeData(BTreeNode* bst)
{
return GetData(bst);
}
void BSTInsert(BTreeNode** pRoot, BSTData data)
{
BTreeNode* parentNode = NULL; //currentNode의 부모 노드를 저장할 변수
BTreeNode* currentNode = *pRoot;
while (currentNode != NULL)
{
if (GetData(currentNode) == data) //같은 키 값이 저장되는 것을 방지
{
return;
}
parentNode = currentNode;
if (data < GetData(currentNode))
{
currentNode = GetLeftSubTree(currentNode); //currentNode 값을 왼쪽 자식 노드의 주소로 변경
}
else
{
currentNode = GetRightSubTree(currentNode); //currentNode 값을 오른쪽 자식 노드의 주소로 변경
}
}
BTreeNode* newNode = MakeBTreeNode();
SetData(newNode, data);
if (parentNode == NULL) //parentNode가 NULL이라는 것은 currentNode가 루트 노드라는 의미
{
*pRoot = newNode;
}
else
{
if (data < GetData(parentNode))
{
MakeLeftSubTree(parentNode, newNode);
}
else
{
MakeRightSubTree(parentNode, newNode);
}
}
}
BTreeNode* BSTSearch(BTreeNode* bst, BSTData target)
{
BTreeNode* currentNode = bst;
while (GetData(currentNode) != target)
{
if (target < currentNode->data)
{
currentNode = GetLeftSubTree(currentNode);
}
else
{
currentNode = GetRightSubTree(currentNode);
}
if (currentNode == NULL)
{
return NULL;
}
}
return currentNode;
}위와 같이 구현한 이진 탐색 트리를 이용해 다음과 같은 main함수의 실행결과를 확인해 보겠습니다.
//main.c 소스 파일로 저장
#include <stdio.h>
#include "BinarySearchTree.h"
int main(void)
{
BTreeNode* bstRoot;
BTreeNode* sNode;
BSTMakeAndInit(&bstRoot);
BSTInsert(&bstRoot, 10);
BSTInsert(&bstRoot, 22);
BSTInsert(&bstRoot, 8);
BSTInsert(&bstRoot, 4);
BSTInsert(&bstRoot, 5);
BSTInsert(&bstRoot, 33);
sNode = BSTSearch(bstRoot, 4);
if (sNode == NULL)
{
printf("탐색 실패!\n");
}
else
{
printf("탐색에 성공한 키의 값 : %d\n", BSTGetNodeData(sNode));
}
return 0;
}
/*
실행결과
탐색에 성공한 키의 값 : 4
*/이진 탐색 트리의 구현이 이로써 끝난 것 같지만 아직 할 게 남아 있습니다. 잠시 후에는 트리의 '순회'를 통해서 트리에 저장된 값을 전반적으로 확인해볼 것입니다.
이진 탐색 트리에서 데이터를 삭제하는 과정은 쉽지만은 않습니다. 다음과 같은 이진 탐색 트리에서,
8을 데이터로 가지는 노드를 어떻게 삭제하면 좋을지 생각해 봅니다. 노드를 삭제하는 것 자체는 어려운 일은 아닙니다. 이진 탐색 트리에서 노드의 삭제가 어려운 이유는 노드 삭제 이후 빈자리를 어떻게 채워야 할지 고민해야 하기 때문입니다. 다음과 같이 빈 노드로 놔둘 수는 없기 때문에 다른 누군가가 해당 노드를 채워야 합니다.
이런 경우에는 삭제 대상 노드의 왼쪽 서브트리나 오른쪽 서브 트리에서 대체노드를 찾아야 합니다. 왼쪽 서브 트리에서 가장 값이 높은 노드를 찾거나, 오른쪽 서브 트리에서 가장 값이 작은 노드를 찾아야 합니다. 따라서 왼쪽 서브 트리에서 가장 값이 큰 노드를 찾으면 7이 될 것이고, 오른쪽 서브 트리에서 가장 값이 작은 노드를 찾으면 9가 될 것입니다.
각각의 서브 트리에서 가장 크거나 가장 작은 값을 찾는 것은 쉽습니다. 가장 큰 값을 찾고 싶으면 서브 트리의 루트 노드로부터 오른쪽 자식 노드만 타고 내려가면 마지막에 가장 큰 값을 찾을 수 있고, 왼쪽 자식 노드만 타고 내려가면 마지막에 가장 작은 값을 찾을 수 있습니다. 7을 대체 노드로 삼으면 다음과 같이 될 것이고,
9를 대체 노드로 삼으면 다음과 같이 될 것입니다.
두 경우 모두 노드의 삭제 후에도 이진 탐색 트리의 구조를 유지하고 있습니다. 그런데 이 과정에서도 우리는 새로운 고민을 해야 합니다. 만약 7을 대체 노드로 삼는다면 삭제하고자 하는 노드를 잠시 제쳐두고,
삭제할 노드의 부모 노드가 왼쪽 자식 노드로서 노드 7을 가리키게 해야 하고,
노드 7이 왼쪽 자식 노드로서 노드 4, 오른쪽 자식 노드로서 노드 10을 가리키게 해야 하고,
노드 4는 오른쪽 자식 노드가 사라졌으므로 오른쪽 자식 노드로서 NULL을 가리키게 해야 합니다.
그리고 삭제 대상 노드를 삭제합니다.
그런데 만약 7의 왼쪽 자식 노드가 다음과 같이 존재할 경우에는 어떨까요?
이 상태에서 노드 8을 삭제하려고 합니다.
노드 8의 왼쪽 자식 노드로부터, 오른쪽 자식 노드만 타고 내려가면 노드 7이 나옵니다. 따라서 이를 대체 노드로 삼습니다.
그런데 노드 7만 대체 노드로 삼는 것이 아니라 노드 7을 루트 노드로 하는 서브 트리 자체가 올라왔습니다. 이것이 핵심입니다. 다른 노드를 대체 노드로 삼을 때는 대체 노드를 루트 노드로 하는 서브 트리 전체로 대체해야 합니다. 이제 노드 8의 부모 노드인 노드 12가 왼쪽 자식 노드로서 노드 7을 가리키게 하고,
노드 7로부터 왼쪽 자식 노드만 타고 내려가서 마지막 왼쪽 자식 노드의 왼쪽 자식 노드로서 노드 4를 가리키게 합니다.
그리고 노드 7로부터 오른쪽 자식 노드만 타고 내려가서 마지막 오른쪽 자식 노드의 오른쪽 자식 노드로서 노드 9를 가리키게 합니다.
그리고 노드 4의 오른쪽 자식 노드는 사라졌으므로, 노드 4의 오른쪽 자식 노드로서 NULL을 가리키게 합니다.
그리고 노드 8을 삭제합니다.
이진 탐색 트리의 삭제 과정이 워낙 특이해서 저도 제대로 이해하기 위해 이렇게 설명을 해봤습니다. 구체적인 순서는 조금 변해도 됩니다. 중요한 것은 어떤 과정들을 거쳐야 하는지 맥락을 이해하는 것입니다.
그런데 위 과정들에는 예외상황도 있을 수 있습니다. 삭제하고자 하는 노드의 부모 노드가 없다면? 즉, 삭제하고자 하는 노드가 루트 노드라면? 그리고 삭제하고자 하는 노드가 아무런 자식 노드도 가지지 않는다면? 즉, 대체 노드를 구할 수 없는 단말 노드라면?
단말 노드라면 비교적 간단합니다. 해당 노드를 삭제하고 해당 노드를 가리키고 있던 부모 노드가 대신 NULL을 가리키게 해야 합니다.
삭제하고자 하는 노드가 루트 노드일 경우에는 고려할 사항이 하나 줄어드는 대신 하나 늘어납니다. 무슨 말이냐. 루트 노드는 부모 노드가 없기 때문에 부모 노드가 자식 노드로서 대체 노드를 가리키게 하는 작업은 하지 않아도 됩니다. 하지만 루트 노드는 루트 노드의 주소를 가지고 있는 변수가 있기 때문에 이 변수가 대체 노드의 주소를 저장하도록 변경해줘야 합니다.
'공부 일지 > 자료구조 공부 일지' 카테고리의 다른 글
| Chapter 12. 균형 잡힌 이진 탐색 트리: AVL 트리의 이해 (0) | 2021.03.23 |
|---|---|
| Chapter 11. 이진 탐색 트리 (2) (0) | 2021.03.22 |
| Chapter 11. 탐색의 이해와 보간 탐색 (2) | 2021.03.20 |
| Chapter 10. 복잡하지만 효율적인 정렬 알고리즘 (0) | 2021.03.20 |
| Chapter 10. 단순한 정렬 알고리즘 (3) | 2021.03.18 |