탐색(Search) 1
by Frinee이 글은 윤성우 저 - "윤성우의 열혈 자료구조"를 공부하고 정리하여 작성하였습니다.
1. 탐색의 이해와 보간 탐색
❓ 탐색의 이해
- 데이터를 찾는 방법을 말함.
- 효율적인 탐색은 대부분 트리의 연장성상에서 이루어짐.
🚨 보간 탐색(interpolation Search)
- 보간 탐색은 이진 탐색의 비효율성을 개선시킨 알고리즘이다.
- 보간 탐색은 이진 탐색과 마찬가지로 모두 정렬이 완료된 데이터를 대상으로 진행함.
“이진 탐색처럼 그냥 중앙에서 시작하지 말고, 탐색대상이 앞쪽에 위치해 있으면 앞쪽에서 탐색을 시작하자!”




- 비례식을 구성하여 탐색 위치의 인덱스 값을 계산한다.
- 다만 오차율을 최소화하기 위해 실수형 나눗셈을 진행한다.
🔑 탐색 키(Search Key)와 탐색 데이터(Search Data)
typedef int Key; // 탐색 키에 대한 typedef 선언 typedef double Data; // 탐색 데이터에 대한 typedef 선언 typedef struct item { Key searchKey; // 탐색 키(search key) Data searchData; // 탐색 데이터(search data) } Item;
🧑🏻💻 보간 탐색의 구현
int ISearch(int ar[], int first, int last, int target) { int mid; if(ar[first] > target || ar[last] < target) return -1; // 탐색 실패 // 이진 탐색과의 차이점 mid = ((double)(target - ar[first]) / (ar[last] - ar[first]) * (last - first)) + first; if(ar[mid] == target) return mid; else if(target < ar[mid]) return ISearch(ar, first, mid-1, target); else return ISearch(ar, mid+1, last, target); }
⚠️ 탈출조건을 만족하지 않는 이유
ex)
int arr\[\] = {1,3,5,7,9};
ISearch(arr,1,4,2);
mid = 0 이 저장됨.
- 그래서
return ISearch(ar, mid+1, last, target)
이 실행이 되버리고 이는ISearch(arr, 1, 4, 2)
가 되어 탈출할 수 없음 - 그래서
if(ar\[first\] > target || ar\[last\] < target) return -1;
// 탐색 실패를 설정해준다.
2. 이진 탐색 트리
- 이진 트리에 데이터 저장 규칙을 더해 놓은 것이 이진 탐색 트리라 할 수 있다.
- 이진 탐색 트리의 노드에 저장된 키(key)는 유일하다.
- 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다.
- 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다.
- 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.
왼쪽 자식 노드의 키 < 부모 노드의 키 < 오른쪽 자식 노드의 키
- 이진 탐색 트리에 데이터를 추가한다 했을 때
- 루트 노드와 비교했을 때, 값이 크면 오른쪽 자식 노드로 이동
- 루트 노드와 비교했을 때, 값이 작으면 왼쪽 자식 노드로 이동
- 왼쪽/오른쪽 노드가 없으면 그 위치에 저장
🌲 이진 탐색 트리 헤더 파일
- BinaryTree2.h
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); - 인자로 전달된 노드의 오른쪽 자식 노드를 교체
- BinarySearchTree.h
#include "BinaryTree2.h" typedef BTData BSTData; // BST의 생성 및 초기화 void BSTMakeAndInit(BTreeNode ** pRoot); // 노드에 저장된 데이터 반환 BSTData BSTGetNodeData(BTreeNode *bst); // BST를 대상으로 데이터 저장(노드의 생성과정 포함) void BSTInsert(BTreeNode ** pRoot, BSTData data); // BST를 대상으로 데이터 탐색 BTreeNode * BSTSearch(BTreeNode *bst, BSTData target);
🌳 이진 탐색 트리: 삽입과 탐색

void BSTInsert(BTreeNode ** pRoot, BSTData data) { BTreeNode * pNode = NULL; // parent Node BTreeNode * cNode = *pRoot; // current Node BTreeNode * nNode = NULL; // new Node // 새로운 노드가 추가될 위치를 찾는다. while(cNode != NULL) { if(data == GetData(cNode)) return; // 키의 중복 허용하지 않음 pNode = cNode; if(GetData(cNode) > data) cNode = GetLeftSubTree(cNode); else cNode = GetRightSubTree(cNode); } //pNode의 자식노드로 추가할 새 노드의 생성 nNode = MakeBTreeNode(); // 새 노드 생성 SetData(nNode, data); // 새 노드에 데이터 저장 //pNode의 자식 노드로 새 노드를 추가 if(pNode != NULL) // 새 노드가 루트 노드가 아니라면, { if(data < GetData(pNode)) MakeLeftSubTree(pNode, nNode); else MakeRightSubTree(pNode, nNode); } else { *pRoot = nNode; } }
BTreeNode * BSTSearch(BTreeNode *bst, BSTData target) { BTreeNode * cNode = bst; // current node BSTData cd; // current data while(cNode != NULL) { cd = GetData(cNode); if(target == cd) return cNode; else if(target < cd) cNode = GetLeftSubTree(cNode); else cNode = GetRightSubTree(cNode); } return NULL; }
🌳❌ 이진 탐색 트리: 삭제
- 이진 탐색 트리에서 임의의 노드를 삭제하는 경우, 삭제 후에도 이진 탐색 트리가 유지되도록 빈 자리를 채워야 함.
- 상황 1 : 삭제할 노드가 단말 노드인 경우

if(삭제할 노드가 단말 노드이면) { if(GetLeftSubTree(pNode) == dNode) // 삭제할 노드가 왼쪽 자식 노드라면 RemoveLeftSubTree(pNode); else RemoveRightSubTree(pNode); }
- 상황 2: 삭제할 노드가 하나의 자식 노드를 갖는 경우

if(삭제할 노드가 하나의 자식 노드를 갖고 있다면) { BTreeNode * dcNode; // 삭제 대상의 자식 노드를 찾는다. if(GetLeftSubTree(dNode) != NULL) // 자식 노드가 왼쪽이라면 dcNode = GetLeftSubTree(dNode); else dcNode = GetRightSubTree(dNode); // 삭제 대상의 부모 노드와 자식 노드를 연결한다. if(GetLeftSubTree(pNode) == dNode) // 삭제 대상이 왼쪽 자식 노드이면 ChangeLeftSubTree(pNode, dcNode); // 왼쪽 연결 else ChangeRightSubTree(pNode, dcNode); }
- 상황 3: 삭제할 노드가 두 개의 자식 노드를 갖는 경우



- 왼쪽 서브트리의 가장 큰 값, 또는 오른쪽 서브트리의 가장 작은 값으로 대체한다.

- 가장 큰 값을 찾을 때는 NULL을 만날 때까지 계속 오른쪽 자식 노드로 이동
- 가장 작은 값을 찾을 때는 NULL을 만날 때까지 계속해서 왼쪽 자식 노드로 이동
“삭제할 노드의 오른쪽 서브 트리에서 가장 작은 값을 지니는 노드를 찾아서 이것으로 삭제할 노드를 대체한다.”

- 단계 1 : 삭제할 노드를 대체할 노드를 찾는다.
- 단계 2 : 대체할 노드에 저장된 값을 삭제할 노드에 대입한다.
- 단계 3 : 대체할 노드의 부모 노드와 자식 노드를 연결한다.
if(삭제할 노드가 두 개의 자식 노드를 지닌다.) { BTreeNode * mNode = GetRightSubTree(dNode); // 대체 노드 BTreeNode * mpNode = dNode; // 대체 노드의 부모 노드 // 단계 1. 삭제 대상의 대체 노드를 찾는다. while(GetLeftSubTree(mNode) != NULL) { mpNode = mNode; mNode = GetLeftSubTree(mNode); } // 단계 2. 대체할 노드에 저장된 값을 삭제할 노드에 대입한다. SetData(dNode, GetData(mNode)); // 단계 3. 대체할 노드의 부모 노드와 자식 노드를 연결한다. if(GetLeftSubTree(mpNode) == mNode) { // 대체할 노드의 자식 노드를 부모 노드의 왼쪽에 연결 ChangeLeftSubTree(mpNode, GetRightSubTree(mNode)); } else { ChangeRightSubTree(mpNode, GetRightSubTree(mNode)); } }
🎄❌ 이진 탐색 트리: 삭제를 위한 이진 트리 확장
// 왼쪽 자식 노드를 트리에서 제거, 제거된 노드의 주소 값이 반환된다. BTreeNode * RemoveLeftSubTree(BTreeNode *bt) { BTreeNode * delNode; if(bt != NULL){ delNode = bt->left; bt->left = NULL; } return delNode; } // 오른쪽 자식 노드를 트리에서 제거, 제거된 노드의 주소 값이 반환된다. BTreeNode * RemoveRightSubTree(BTreeNode *bt) { BTreeNode * delNode; if(bt != NULL){ delNode = bt->right; bt->right = NULL; } return delNode; } // 메모리 소멸을 수반하지 않고 main의 왼쪽 자식 노드를 변경 void ChangeLeftSubTree(BTreeNode *main, BTreeNode * sub) { main->left = sub; } // 메모리 소멸을 수반하지 않고 main의 오른쪽 자식 노드를 변경 void ChangeRightSubTree(BTreeNode *main, BTreeNode * sub) { main->right = sub; }
🎄이진 탐색 트리: 완전한 구현 🎄
BTreeNode * BSTRemove(BTreeNode ** pRoot, BSTData target) { BTreeNode *pVRoot = MakeBTreeNode(); BTreeNode *pNode = pVRoot; BTreeNode *cNode = *pRoot; BTreeNode *dNode; // 루트 노드를 pVRoot가 가리키는 노드의 오른쪽 자식 노드가 되게 한다. ChangeRightSubTree(pVRoot, *pRoot); // 삭제 대상인 노드를 탐색 while(cNode != NULL && GetData(cNode) != target) { pNode = cNode; if(target < GetData(cNode)) cNode = GetLeftSubTree(cNode); else cNode = GetRightSubTree(cNode); } if(cNode == NULL) return NULL; dNode = cNode; // 1. 삭제할 노드가 단말 노드이면 if(GetLeftSubTree(dNode) == NULL && GetRightSubTree(dNode) == NULL) { if(GetLeftSubTree(pNode) == dNode) // 삭제할 노드가 왼쪽 자식 노드라면 RemoveLeftSubTree(pNode); else RemoveRightSubTree(pNode); } // 2. 삭제할 노드가 하나의 자식 노드를 갖고 있다면 else if(GetLeftSubTree(dNode) == NULL || GetRightSubTree(dNode) == NULL) { BTreeNode * dcNode; // 삭제 대상의 자식 노드를 찾는다. if(GetLeftSubTree(dNode) != NULL) // 자식 노드가 왼쪽이라면 dcNode = GetLeftSubTree(dNode); else dcNode = GetRightSubTree(dNode); // 삭제 대상의 부모 노드와 자식 노드를 연결한다. if(GetLeftSubTree(pNode) == dNode) // 삭제 대상이 왼쪽 자식 노드이면 ChangeLeftSubTree(pNode, dcNode); // 왼쪽 연결 else ChangeRightSubTree(pNode, dcNode); } // 3. 삭제할 노드가 두 개의 자식 노드를 지닌다. else { BTreeNode * mNode = GetRightSubTree(dNode); // 대체 노드 BTreeNode * mpNode = dNode; // 대체 노드의 부모 노드 int delData; // 단계 1. 삭제 대상의 대체 노드를 찾는다. while(GetLeftSubTree(mNode) != NULL) { mpNode = mNode; mNode = GetLeftSubTree(mNode); } // 단계 2. 대체할 노드에 저장된 값을 삭제할 노드에 대입한다. delData = GetData(dNode); // 대입 전 데이터 백업 SetData(dNode, GetData(mNode)); // 단계 3. 대체할 노드의 부모 노드와 자식 노드를 연결한다. if(GetLeftSubTree(mpNode) == mNode) // 대체할 노드의 자식 노드를 부모 노드의 왼쪽에 연결 ChangeLeftSubTree(mpNode, GetRightSubTree(mNode)); else ChangeRightSubTree(mpNode, GetRightSubTree(mNode)); dNode = mNode; SetData(dNode, delData); } // 삭제된 노드가 루트노드라면 if(GetRightSubTree(pVRoot) != *pRoot) *pRoot = GetRightSubTree(pVRoot); // 루트 노드 변경 free(pVRoot); // 가상 루트 노드 소멸 return dNode; }

- 가상 루트 노드를 둔 이유는 삭제할 노드가 루트 노드인 경우를 일반화하기 위함.
자료
- 윤성우의 열혈 자료구조 (윤성우 저, 2023.10)
블로그의 정보
프리니의 코드저장소
Frinee