이진 탐색 트리(Binary Search Tree)란?
■ 탐색을 효육적으로 하기 위한 자료구조
※ 특징
- 이진트리이며 모든 원소는 서로 다른 유일한 키(key)를 가진다.
- (왼쪽 sub-트리의 key값) < (루트의 key값) < (오른쪽 sub-트리의 key값)
- 왼쪽 sub-트리와 오른쪽 sub-트리도 이진탐색트리이다.
※ 탐색 : searchBST()연산
- ROOT에서 시작.
- 탐색할 key값을 루트 노드의 key값과 비교.
- (1) (키값 = 루트 노드의 키값) : 원하는 원소를 찾았으므로 탐색 성공.
- (2) (키값 < 루트 노드의 키값) : 루트 노드의 왼쪽 sub-트리에 대해서 탐색연산 수행.
- (3) (키값 > 루트 노드의 키값) : 루트 노드의 오른쪽 sub-트리에 대해서 탐색연산 수행.
▷예시 코드
BinTree* searchBST(BunTree* bt, BTData x)
{
BinTree* p = bt;
while(p != NULL) {
if(x == p->key) return p;
if(x < p->key) p = p->left;
else p = p->right;
}
printf("Error: 찾는 키가 없습니다.\n");
retrun NULL;
}
※ 삽입 : insertBST() 연산
- 먼저 탐색 연산을 수행
- 탐색 실패한 위치에 원소를 삽입
▷예시 코드
void insertBST(BinTree* bt, BTData x) {
BinTree* p = bt;
BinTree* parent = NULL;
//삽입할 노드 탐색
while(p != NULL) {
if(x == p->key) {
printf("Error: 이미 같은 키가 있습니다.\n");
return;
}
parent = p;
if(x < p->key) p = p->left;
else p = p->right;
}
//삽입할 노드 생성
BinTree* newNode = (BinTree*)malloc(sizeof(BinTree));
newNode->key = x;
newNode->left = NULL;
newNode->right = NULL;
//삽입노드 연결
if(bt == NULL) bt = newNode;
if(x < parent->key) parent->left = newNode;
else parent->right = newNode;
}
※ 삭제 : deleteBST() 연산
- Case 1: 삭제할 노드의 차수가 0인 경우
- 부모의 해당 자식의 필드를 NULL로 처리후 노드 삭제
- Case 2: 삭제할 노드의 차수가 1일 경우
- 삭제될 노드의 자식을 삭제될 노드의 부모노드에 연결후 노드 삭제
- Case 3: 삭제할 노드의 차수가 2인 경우
- 1. 삭제할 노드의 자손들 중 후계자를 선택하여 자리를 물려줌
- 2. 후계자: 왼쪽 sub-트리 중 가장 큰 원소 or 오른쪽 sub-트리 중 가장 작은 원소
- 3. 후계자 노드는 자식이 1 또는 0이므로 CASE1, CASE2 이용