티스토리 뷰
주의 사항!
- 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
- 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
- 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.
이진 탐색 트리의 삭제 과정이 복잡하게 느껴지는 이유는 고려해야 할 예외상황이 많고, 따라서 일관적인 삭제 과정을 구현하지 못한다는 데에 있을지도 모릅니다. 그래서 이진 탐색 트리의 삭제 과정은 어떤 과정들을 거쳐야 하는지 정리해놓고 구현하는 것이 편합니다.
앞서 이진 탐색 트리의 삭제 과정을 열심히 설명했었는데 이진 탐색 트리의 삭제 과정은 크게 세 가지의 경우에 따라 달라짐을 알 수 있었습니다.
- 삭제 노드에 서브 트리가 없는 경우
- 삭제 노드에 서브 트리가 하나 이상 있는 경우
- 삭제 노드가 루트 노드인 경우
이진 탐색 트리의 삭제 알고리즘을 다음과 같이 정해봤습니다.
- 삭제할 노드의 부모 노드를 저장할 변수를 선언하고, 삭제할 노드의 부모 노드 주소를 저장한다. 만약 삭제할 노드가 루트 노드라면 NULL을 저장한다.
- 대체 노드를 저장할 변수를 선언하고, 삭제할 노드의 서브 트리에서 대체 노드를 찾아 저장한다. 대체 노드를 찾으면, 대체 노드의 부모 노드가 대체 노드 대신 NULL을 가리키도록 한다. 만약 서브 트리가 없다면 NULL을 저장한다.
- 부모 노드 변수가 NULL이 아니라면, 삭제할 노드의 부모 노드가, 삭제할 노드 대신 대체 노드 변수에 저장된 주소를 가리키도록 한다.
- 부모 노드 변수가 NULL이라면, 루트 노드의 주소를 저장하는 이진 탐색 트리 구조체 변수에 대체 노드 변수에 저장된 주소를 저장한다.
- 대체 노드 변수가 NULL이라면, 삭제할 노드를 삭제하고 알고리즘을 종료한다.
- 삭제할 노드가 가지는 왼쪽 자식 노드와 오른쪽 자식 노드를, 대체 노드를 루트 노드로 하는 서브 트리의 마지막 왼쪽 자식 노드와 마지막 오른쪽 자식 노드가 각각 가리키도록 한다.
- 삭제할 노드를 삭제한다.
위 알고리즘을 직접 구현해 봤습니다.
BSTData RemoveBSTNode(BTreeNode** pRoot, BTreeNode* removeNode); //노드를 삭제하고, 해당 노드의 데이터를 반환
BSTData RemoveData(BTreeNode** pRoot, BSTData data); //인자로 주는 데이터를 저장하고 있는 노드를 삭제하고, 데이터 반환 함수위의 두 함수가 이진 탐색 트리의 헤더 파일에 새로 추가되었습니다.
BSTData RemoveData(BTreeNode** pRoot, BSTData data)
{
BTreeNode* removeNode = BSTSearch(*pRoot, data);
if (removeNode == NULL)
{
printf("삭제하고자 하는 데이터가 존재하지 않습니다. -1을 반환합니다.\n");
return -1;
}
return RemoveBSTNode(pRoot, removeNode);
}먼저 RemoveData 함수입니다. 해당 함수는 인자로 주는 데이터를 저장하고 있는 노드를 찾습니다. 그리고 해당 노드의 주소를 인자로 주어 RemoveBSTNode 함수를 호출하고 있습니다.
다음은 RemoveBSTNode 함수입니다.
BSTData RemoveBSTNode(BTreeNode** pRoot, BTreeNode* removeNode)
{
BTreeNode* parentNode = NULL; //삭제할 노드의 부모 노드를 저장할 변수
BTreeNode* delNode = *pRoot; //삭제할 노드를 저장할 변수
BSTData delData = GetData(removeNode); //삭제할 데이터 저장
while (GetData(delNode) != delData) //delNode의 데이터와 삭제할 데이터가 다르다면
{
parentNode = delNode; //현재 delNode를 부모 노드로 저장
if (GetData(delNode) < delData) //삭제할 데이터가 delNode의 데이터보다 크다면
{
delNode = delNode->right; //delNode의 오른쪽 자식 노드를 새로운 delNode로 설정
}
else //삭제할 데이터가 delNode의 데이터보다 작다면
{
delNode = delNode->left; //delNode의 왼쪽 자식 노드를 새로운 delNode로 설정
}
}
BTreeNode* alternateNode = GetAlternateNode(removeNode); //대체 노드를 찾고 대체 노드의 부모 노드가 대체 노드 대신 NULL을 가리키도록 함
if (parentNode != NULL) //부모 노드가 존재한다면
{
if (GetLeftSubTree(parentNode) == removeNode) //삭제할 노드가 부모 노드의 왼쪽 자식 노드라면
{
parentNode->left = alternateNode; //부모 노드가 삭제할 노드 대신 대체 노드를 가리키도록 함
}
else //삭제할 노드가 부모 노드의 오른쪽 자식 노드라면
{
parentNode->right = alternateNode; //부모 노드가 삭제할 노드 대신 대체 노드를 가리키도록 함
}
}
else //부모 노드가 존재하지 않는다면, 즉, 삭제할 노드가 루트 노드라면
{
*pRoot = alternateNode; //루트 노드의 주소를 대체 노드의 주소로 바꿈
}
if (alternateNode == NULL) //대체 노드가 존재하지 않는다면
{
free(removeNode); //삭제할 노드 삭제
return delData; //삭제된 데이터 반환
}
BTreeNode* lastNode = alternateNode; //대체 노드를 루트 노드로 하는 서브 트리에서 가장 왼쪽, 또는 가장 오른쪽의 자식 노드를 저장하는 변수
while (GetLeftSubTree(lastNode) != NULL) //lastNode의 왼쪽 자식 노드가 존재하면
{
lastNode = GetLeftSubTree(lastNode); //왼쪽 자식 노드를 lastNode로 설정
}
lastNode->left = removeNode->left; //lastNode가 왼쪽 자식 노드로서 삭제할 노드의 왼쪽 자식 노드를 가리키게 함
lastNode = alternateNode; //lastNode를 다시 대체 노드로 초기화
while (GetRightSubTree(lastNode) != NULL) //lastNode의 오른쪽 자식 노드가 존재하면
{
lastNode = GetRightSubTree(lastNode); //오른쪽 자식 노드를 lastNode로 설정
}
lastNode->right = removeNode->right; //lastNode가 오른쪽 자식 노드로서 삭제할 노드의 오른쪽 자식 노드를 가리키게 함
return delData; //삭제된 데이터 반환
}주석을 달아서 세세하게 설명을 해보려고 했습니다. 위 코드를 보면,
BTreeNode* alternateNode = GetAlternateNode(removeNode); //대체 노드를 찾고 대체 노드의 부모 노드가 대체 노드 대신 NULL을 가리키도록 함여기서 새로운 함수가 사용되었습니다. GetAlternateNode 함수는 삭제될 노드의 자리를 대체할 대체 노드를 찾아내고, 대체 노드의 부모 노드가 대체 노드 대신 NULL을 가리키도록 한 후, 대체 노드의 주소를 반환합니다. 해당 함수는 헤더 파일에는 선언되어 있지 않고 소스 파일에 다음과 같이 정의되어 있습니다.
BTreeNode* GetAlternateNode(BTreeNode* delNode)
{
BTreeNode* alternateNode; //대체 노드를 저장할 변수
int leftOrRight; //왼쪽 서브 트리에서 대체 노드를 찾으면 LEFT, 오른쪽 서브 트리에서 찾으면 RIGHT
if (GetLeftSubTree(delNode) != NULL) //삭제할 노드의 왼쪽 자식 노드가 존재하면
{
alternateNode = GetLeftSubTree(delNode); //삭제할 노드의 왼쪽 자식 노드를 대체 노드로 설정
leftOrRight = LEFT;
}
else if (GetRightSubTree(delNode) != NULL) //삭제할 노드의 오른쪽 자식 노드가 존재하면
{
alternateNode = GetRightSubTree(delNode); //삭제할 노드의 오른쪽 자식 노드를 대체 노드로 설정
leftOrRight = RIGHT;
}
else //자식 노드가 존재하지 않으면
{
return NULL; //대체 노드는 NULL 반환
}
BTreeNode* parentNode = delNode; //대체 노드의 부모 노드를 저장할 변수
switch (leftOrRight)
{
case LEFT: //왼쪽 서브 트리에서 대체 노드를 찾는 경우
while (GetRightSubTree(alternateNode) != NULL) //대체 노드의 오른쪽 자식 노드가 존재한다면
{
parentNode = alternateNode;
alternateNode = GetRightSubTree(alternateNode); //오른쪽 자식 노드를 새로운 대체 노드로 설정
}
if (parentNode == delNode) //만약 대체 노드의 부모 노드가 삭제할 노드라면
{
parentNode->left = NULL; //대체 노드는 부모 노드의 왼쪽 자식일 것이므로 NULL로 바꿈
}
else //대체 노드의 부모 노드가 삭제할 노드가 아니라면
{
parentNode->right = NULL; //대체 노드는 부모 노드의 오른쪽 자식일 것으므로 NULL로 바꿈
}
break;
case RIGHT: //오른쪽 서브 트리에서 대체 노드를 찾는 경우
while (GetLeftSubTree(alternateNode) != NULL) //대체 노드의 왼쪽 자식 노드가 존재한다면
{
parentNode = alternateNode;
alternateNode = GetLeftSubTree(alternateNode); //왼쪽 자식 노드를 새로운 대체 노드로 설정
}
if (parentNode == delNode) //만약 대체 노드의 부모 노드가 삭제할 노드라면
{
parentNode->right = NULL; //대체 노드는 부모 노드의 오른쪽 자식일 것이므로 NULL로 바꿈
}
else //대체 노드의 부모 노드가 삭제할 노드가 아니라면
{
parentNode->left = NULL; //대체 노드는 부모 노드의 왼쪽 자식일 것이므로 NULL로 바꿈
}
break;
}
return alternateNode;
}이 함수 역시 주석을 세세하게 달아서 설명을 해보려고 했습니다.
이진 탐색 트리의 삭제 과정을 구현하는 것은 책에서도 소개하고 있습니다. 그런데 제가 보기에는 책에서 구현하는 방식이 조금 맘에 들지 않아서 직접 구현해 보고자 했습니다. 그래서 이진 탐색 트리의 삭제 과정 하나 구현하는 데에도 머리를 좀 부여잡았습니다.
전체 파일을 보이고, main 함수와 그 실행결과도 보이겠습니다.
//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)
{
BTreeNode* delNodeRight = bt->right;
DeleteTree(bt->left);
printf("%d 을(를) 삭제합니다.\n", GetData(bt));
free(bt);
DeleteTree(delNodeRight);
}
}//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를 대상으로 데이터 탐색
BSTData RemoveBSTNode(BTreeNode** pRoot, BTreeNode* removeNode);
BSTData RemoveData(BTreeNode** pRoot, BSTData data);
#endif//BinarySearchTree.c 소스 파일로 저장
#include "BinarySearchTree.h"
#include <stdio.h>
#include <stdlib.h>
#define LEFT -1
#define RIGHT 1
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;
}
BTreeNode* GetAlternateNode(BTreeNode* delNode)
{
BTreeNode* alternateNode; //대체 노드를 저장할 변수
int leftOrRight; //왼쪽 서브 트리에서 대체 노드를 찾으면 LEFT, 오른쪽 서브 트리에서 찾으면 RIGHT
if (GetLeftSubTree(delNode) != NULL) //삭제할 노드의 왼쪽 자식 노드가 존재하면
{
alternateNode = GetLeftSubTree(delNode); //삭제할 노드의 왼쪽 자식 노드를 대체 노드로 설정
leftOrRight = LEFT;
}
else if (GetRightSubTree(delNode) != NULL) //삭제할 노드의 오른쪽 자식 노드가 존재하면
{
alternateNode = GetRightSubTree(delNode); //삭제할 노드의 오른쪽 자식 노드를 대체 노드로 설정
leftOrRight = RIGHT;
}
else //자식 노드가 존재하지 않으면
{
return NULL; //대체 노드는 NULL 반환
}
BTreeNode* parentNode = delNode; //대체 노드의 부모 노드를 저장할 변수
switch (leftOrRight)
{
case LEFT: //왼쪽 서브 트리에서 대체 노드를 찾는 경우
while (GetRightSubTree(alternateNode) != NULL) //대체 노드의 오른쪽 자식 노드가 존재한다면
{
parentNode = alternateNode;
alternateNode = GetRightSubTree(alternateNode); //오른쪽 자식 노드를 새로운 대체 노드로 설정
}
if (parentNode == delNode) //만약 대체 노드의 부모 노드가 삭제할 노드라면
{
parentNode->left = NULL; //대체 노드는 부모 노드의 왼쪽 자식일 것이므로 NULL로 바꿈
}
else //대체 노드의 부모 노드가 삭제할 노드가 아니라면
{
parentNode->right = NULL; //대체 노드는 부모 노드의 오른쪽 자식일 것으므로 NULL로 바꿈
}
break;
case RIGHT: //오른쪽 서브 트리에서 대체 노드를 찾는 경우
while (GetLeftSubTree(alternateNode) != NULL) //대체 노드의 왼쪽 자식 노드가 존재한다면
{
parentNode = alternateNode;
alternateNode = GetLeftSubTree(alternateNode); //왼쪽 자식 노드를 새로운 대체 노드로 설정
}
if (parentNode == delNode) //만약 대체 노드의 부모 노드가 삭제할 노드라면
{
parentNode->right = NULL; //대체 노드는 부모 노드의 오른쪽 자식일 것이므로 NULL로 바꿈
}
else //대체 노드의 부모 노드가 삭제할 노드가 아니라면
{
parentNode->left = NULL; //대체 노드는 부모 노드의 왼쪽 자식일 것이므로 NULL로 바꿈
}
break;
}
return alternateNode;
}
BSTData RemoveBSTNode(BTreeNode** pRoot, BTreeNode* removeNode)
{
BTreeNode* parentNode = NULL; //삭제할 노드의 부모 노드를 저장할 변수
BTreeNode* delNode = *pRoot; //삭제할 노드를 저장할 변수
BSTData delData = GetData(removeNode); //삭제할 데이터 저장
while (GetData(delNode) != delData) //delNode의 데이터와 삭제할 데이터가 다르다면
{
parentNode = delNode; //현재 delNode를 부모 노드로 저장
if (GetData(delNode) < delData) //삭제할 데이터가 delNode의 데이터보다 크다면
{
delNode = delNode->right; //delNode의 오른쪽 자식 노드를 새로운 delNode로 설정
}
else //삭제할 데이터가 delNode의 데이터보다 작다면
{
delNode = delNode->left; //delNode의 왼쪽 자식 노드를 새로운 delNode로 설정
}
}
BTreeNode* alternateNode = GetAlternateNode(removeNode); //대체 노드를 찾고 대체 노드의 부모 노드가 대체 노드 대신 NULL을 가리키도록 함
if (parentNode != NULL) //부모 노드가 존재한다면
{
if (GetLeftSubTree(parentNode) == removeNode) //삭제할 노드가 부모 노드의 왼쪽 자식 노드라면
{
parentNode->left = alternateNode; //부모 노드가 삭제할 노드 대신 대체 노드를 가리키도록 함
}
else //삭제할 노드가 부모 노드의 오른쪽 자식 노드라면
{
parentNode->right = alternateNode; //부모 노드가 삭제할 노드 대신 대체 노드를 가리키도록 함
}
}
else //부모 노드가 존재하지 않는다면, 즉, 삭제할 노드가 루트 노드라면
{
*pRoot = alternateNode; //루트 노드의 주소를 대체 노드의 주소로 바꿈
}
if (alternateNode == NULL) //대체 노드가 존재하지 않는다면
{
free(removeNode); //삭제할 노드 삭제
return delData; //삭제된 데이터 반환
}
BTreeNode* lastNode = alternateNode; //대체 노드를 루트 노드로 하는 서브 트리에서 가장 왼쪽, 또는 가장 오른쪽의 자식 노드를 저장하는 변수
while (GetLeftSubTree(lastNode) != NULL) //lastNode의 왼쪽 자식 노드가 존재하면
{
lastNode = GetLeftSubTree(lastNode); //왼쪽 자식 노드를 lastNode로 설정
}
lastNode->left = removeNode->left; //lastNode가 왼쪽 자식 노드로서 삭제할 노드의 왼쪽 자식 노드를 가리키게 함
lastNode = alternateNode; //lastNode를 다시 대체 노드로 초기화
while (GetRightSubTree(lastNode) != NULL) //lastNode의 오른쪽 자식 노드가 존재하면
{
lastNode = GetRightSubTree(lastNode); //오른쪽 자식 노드를 lastNode로 설정
}
lastNode->right = removeNode->right; //lastNode가 오른쪽 자식 노드로서 삭제할 노드의 오른쪽 자식 노드를 가리키게 함
return delData; //삭제된 데이터 반환
}
BSTData RemoveData(BTreeNode** pRoot, BSTData data)
{
BTreeNode* removeNode = BSTSearch(*pRoot, data);
if (removeNode == NULL)
{
printf("삭제하고자 하는 데이터가 존재하지 않습니다. -1을 반환합니다.\n");
return -1;
}
return RemoveBSTNode(pRoot, removeNode);
}//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));
}
BSTData delData = RemoveData(&bstRoot, 8);
printf("삭제 결과 : %d\n", delData);
delData = RemoveData(&bstRoot, 33);
printf("삭제 결과 : %d\n", delData);
delData = RemoveData(&bstRoot, 10);
printf("삭제 결과 : %d\n", delData);
BSTInsert(&bstRoot, 12);
BSTInsert(&bstRoot, 25);
BSTInsert(&bstRoot, 9);
BSTInsert(&bstRoot, 6);
BSTInsert(&bstRoot, 7);
BSTInsert(&bstRoot, 26);
delData = RemoveData(&bstRoot, 25);
printf("삭제 결과 : %d\n", delData);
delData = RemoveData(&bstRoot, 12);
printf("삭제 결과 : %d\n", delData);
DeleteTree(bstRoot);
return 0;
}
/*
실행결과
탐색에 성공한 키의 값 : 4
삭제 결과 : 8
삭제 결과 : 33
삭제 결과 : 10
삭제 결과 : 25
삭제 결과 : 12
4 을(를) 삭제합니다.
5 을(를) 삭제합니다.
6 을(를) 삭제합니다.
7 을(를) 삭제합니다.
9 을(를) 삭제합니다.
22 을(를) 삭제합니다.
26 을(를) 삭제합니다.
*/'공부 일지 > 자료구조 공부 일지' 카테고리의 다른 글
| Chapter 12. 균형 잡힌 이진 탐색 트리 : AVL 트리의 구현 (0) | 2021.03.23 |
|---|---|
| Chapter 12. 균형 잡힌 이진 탐색 트리: AVL 트리의 이해 (0) | 2021.03.23 |
| Chapter 11. 이진 탐색 트리 (0) | 2021.03.22 |
| Chapter 11. 탐색의 이해와 보간 탐색 (2) | 2021.03.20 |
| Chapter 10. 복잡하지만 효율적인 정렬 알고리즘 (0) | 2021.03.20 |