일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- react
- Galera Cluster
- 자바
- spring webflux
- Java
- 파이썬
- 운영체제
- Algorithm
- Kafka
- Heap
- mongoDB
- 디자인 패턴
- Proxy
- design pattern
- JPA
- 자료구조
- OS
- MySQL
- IT
- 네트워크
- JavaScript
- C
- Data Structure
- Spring
- redis
- c언어
- 컴퓨터구조
- MSA
- 백준
- 알고리즘
Archives
- Today
- Total
시냅스
[자료구조] 이진 탐색 트리 , Binary search tree - 링크드 리스트로 구현 본문
이진 탐색 트리, Binary search tree
이진 탐색 트리는
- 각 노드에는 값이 있다.
- 값들은 전순서(임의의 원소를 비교할 수 있는 부분 순서 집합)가 있다.
- 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지신 노드들로 이뤄진다.
- 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이워진다.
이진 탐색 트리는 일반적으로 탐색에서 O(log n)으로 장점을 갖는다.
다만, 편향 트리로 이뤄져있다면 O(n)의 가능성이 있다.
이 경우 red black tree를 이용할 수 있다.
아래에서는 Linked list를 사용한 이진 탐색 트리의 구현을 살펴본다.
구현
- 생성
- 삽입
- 개별 node 삭제
- Tree 삭제
생성
typedef struct BinSearchTreeNodeType
{
int key;
struct BinSearchTreeNodeType* pLeftChild;
struct BinSearchTreeNodeType* pRightChild;
} BinSearchTreeNode;
typedef struct BinTreeType
{
struct BinSearchTreeNodeType* pRootNode;
} BinSearchTree;
BinSearchTree *makeBinSearchTree(BinSearchTreeNode rootNode) // 생성
{
BinSearchTree *temp = calloc(1, sizeof(BinSearchTree));
temp->pRootNode = calloc(1, sizeof(BinSearchTreeNode));
*temp->pRootNode = rootNode;
temp->pRootNode->pRightChild = 0;
temp->pRootNode->pLeftChild = 0;
return (temp);
}
key와 data를 가질 수 있지만,
이번에는 key만을 가진 이진 탐색 트리를 구현했다.
삽입
BinSearchTreeNode *insertBST(BinSearchTree *pBinSearchTree, BinSearchTreeNode element) // node 삽입
{
BinSearchTreeNode *buf;
BinSearchTreeNode *new_one = calloc(1, sizeof(BinSearchTreeNode));
*new_one = element; // 새로 할당할 node
new_one->pRightChild = 0;
new_one->pLeftChild = 0;
buf = pBinSearchTree->pRootNode; // root노드를 시작으로 들어갈 위치의 부모노드를 저장한다.
while(1)
{
if (buf->key > new_one->key) // 새로들어갈 노드가 더 작다면
{
if (!(buf->pLeftChild)) // 부모노드의 left child가 없다면
{
buf->pLeftChild = new_one; // 부모 노드와 이어준다.
return (new_one);
}
else // 내려가 다시 탐색한다.
buf = buf->pLeftChild;
}
else if (buf->key < new_one->key) // 새로들어갈 노드가 더 크다면
{
if(!(buf->pRightChild)) // 부모노드의 right child가 없다면
{
buf->pRightChild = new_one; // 부모 노드와 이어준다.
return (new_one);
}
else // 내려가 탐색한다.
buf = buf->pRightChild;
}
else
return (NULL);
}
}
root node 는 tree를 생성하며 할당해주어, 이외의 케이스에 대해서만 고려하면 된다.
왼쪽 서브 트리는 항상 부모 노드보다 작다는 것, 오른쪽의 경우에는 항상 크다는 것을 유의하여야 한다.
개별 node 삭제
BinSearchTreeNode *LorR(BinSearchTreeNode *temp, int searchKey) // 왼쪽, 오른쪽 자식 노드인지 판별
{
BinSearchTreeNode *buf;
buf = NULL;
if (searchKey == temp->pRightChild->key) // 만약 오른쪽 자식 노드라면
{
buf = temp->pRightChild; // 오른쪽 자식으로 할당한다.
temp->pRightChild = NULL;
if (buf->pLeftChild && !(buf->pRightChild)) // 자식 노드 1개때 부모 노드와의 연결을 끊는다.
temp->pRightChild = buf->pLeftChild;
else if (!(buf->pLeftChild) && buf->pRightChild)
temp->pRightChild = buf->pRightChild;
}
else if (searchKey == temp->pLeftChild->key) // 만약 왼쪽 자식 노드라면
{
buf = temp->pLeftChild; // 왼쪽 자식 노드로 할당한다.
temp->pLeftChild = NULL;
if (buf->pLeftChild && !(buf->pRightChild)) // 자식 노드 1개때 부모 노드와의 연결을 끊는다.
temp->pLeftChild = buf->pLeftChild;
else if (!(buf->pLeftChild) && buf->pRightChild)
temp->pLeftChild = buf->pRightChild;
}
return (buf);
}
void deleteBST(BinSearchTree *pBinSearchTree, int searchKey) // 개별 노드 삭제
{
BinSearchTreeNode *temp, *delNode, *pSuccessor, *pPredecessor;
// 각각 삭제할 노드의 부모노드, 삭제할 노드, 계승할 노드, 계승할 노드의 부모노드 이다.
temp = pBinSearchTree->pRootNode; // 삭제할 노드의 부모노드로, Root로 시작한다.
delNode = NULL;
while (1)
{
if (temp->key == searchKey) // 만약 삭제할 노드가 root라면 delNode를 temp로 할당한다.
delNode = temp;
if ((temp->pRightChild && temp->pRightChild->key == searchKey) || (temp->pLeftChild && temp->pLeftChild->key == searchKey))
{ // 자식 중 delNode가 있다면,
delNode = LorR(temp, searchKey); // 함수로 들어가 왼쪽인지 오른쪽인지 판별한다.
break ;
}
if (temp->pLeftChild && temp->key > searchKey) // 자식 중 searchKey에 해당하지 않으면 다시 탐색한다.
temp = temp->pLeftChild;
else if (temp->pRightChild && temp->key < searchKey)
temp = temp->pRightChild;
else
break ;
}
if (!delNode)
return ;
else if (delNode->pLeftChild && delNode->pRightChild) // 자식노드 2개라면,
{
pSuccessor = delNode->pLeftChild; // 삭제할 노드의 왼쪽으로 간 뒤 맨 오른쪽 노드가 계승노드로 둔다.
while(pSuccessor->pRightChild)
{
pPredecessor = pSuccessor;
pSuccessor = pSuccessor->pRightChild;
}
if (pSuccessor->pLeftChild) // 만약 계승노드에 자식노드 (무조건 왼쪽이다.)가 있다면 부모노드와 이어준다.
pPredecessor->pRightChild = pSuccessor->pLeftChild;
else // 계승노드에 자식노드가 없다면 연결을 끊어준다.
pPredecessor->pRightChild = NULL;
if (pBinSearchTree->pRootNode->key == searchKey) // 만약 삭제할 노드가 root 였다면
pBinSearchTree->pRootNode = pSuccessor; // root를 갱신단다.
else if (temp->key < pSuccessor->key) // 삭제한 노드의 부모노드와 이어준다.
temp->pRightChild = pSuccessor;
else if (temp->key > pSuccessor->key) // 삭제한 노드의 부모노드와 이어준다.
temp->pLeftChild = pSuccessor;
pSuccessor->pLeftChild = delNode->pLeftChild; // 삭제한 노드의 자식노드와 계승노드를 이어준다.
pSuccessor->pRightChild = delNode->pRightChild;
}
free(delNode); // 할당 해제, 자식노드가 0개일 때는 고려할 것 없이 바로 할당해제 한다.
delNode = NULL;
}
어떠한 노드가 삭제되었을 때 고려해야 할 것은
- 원래 부모노드와 삭제한 노드의 서브트리를 이어줄 것
- 삭제한 노드에 자식 노드가 0개일 때
- 부모노드에 바로 이어주면 된다.
- 삭제한 노드에 자식 노드가 1개일 때
- 왼쪽인지 오른쪽인지 판별하여 이어준다.
- 삭제한 노드에 자식 노드가 2개일 때
- 삭제한 노드가 root인지
- 삭제한 노드의 자식 노드에 자식 노드가 있는지
- 삭제한 노드의 부모노드의 왼쪽 자식이 될지 오른쪽이 될지
- 삭제한 노드의 서브트리를 이어준다.
이다.
Tree 삭제
void deleteBinSearchTree(BinSearchTree *pBinSearchTree) // 트리 삭제
{
deleteBinSearchTreeNode(pBinSearchTree->pRootNode);
free(pBinSearchTree);
pBinSearchTree = NULL;
}
void deleteBinSearchTreeNode(BinSearchTreeNode *pNode) // 노드 삭제
{
if (pNode)
{
deleteBinSearchTreeNode(pNode->pLeftChild);
deleteBinSearchTreeNode(pNode->pRightChild);
free(pNode);
pNode = NULL;
}
}
recursive call을 이용해 하위 노드들을 먼저 끊어주었다.
'자료구조' 카테고리의 다른 글
[자료구조] 최소 신장 트리 Minimum Spanning Tree (0) | 2022.06.07 |
---|---|
[자료구조] 힙, Heap - 배열 리스트로 구현 (0) | 2022.05.18 |
[자료구조] 트리, Tree - 링크드 리스트로 구현 (0) | 2022.05.14 |
[자료구조] 덱 Deque, 큐, Queue - 링크드 리스트로 구현 (0) | 2022.05.01 |
[자료구조] 큐, Queue - 배열리스트로 구현 (0) | 2022.05.01 |
Comments