[자료구조] 이진 탐색 트리 (Binary Search Tree)

1. 이진 탐색 트리(Binary Search Tree)

• 이진 트리에 탐색을 위한 조건을 추가하여 정의한 자료구조

 

1) 정의

• 모든 원소는 서로 다른 유일한 키를 가진다.
• 왼쪽 서브 트리에 있는 원소의 키들은 그 루트의 키보다 작다.
• 오른쪽 서브 트리에 있는 원소들의 키들은 그 루트의 키보다 크다.
• 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리다.

 

2. 탐색 연산

• 루트에서 시작
• 탐색할 킷값 x를 루트 노드의 킷값과 비교
• 킷값 x = 루트 노드의 킷값인 경우
   - 원하는 원소를 찾았으므로 탐색 연산 성공
• 킷값 x < 루트 노드의 킷값인 경우
   - 루트 노드의 왼쪽 서브 트리에 대해서 탐색 연산 수행
• 킷값 x > 루트 노드의 킷값인 경우
   - 루트 노드의 오른쪽 서브 트리에 대해서 탐색 연산 수행
   - 서브 트리에 대해서 순환적으로 탐색 연산을 반복

 

1) 알고리즘

 

searchBST(bsT, x)
	p <- bsT;
	if(p == NULL)
		return NULL;
	if(x == p.key)
		return p;
	if(x < p.key)
		return searchBST(p.left, x);
	else	return searchBST(P.right, x);
end searchBST()

 

3. 삽입 연산

• 탐색 연산을 수행
• 삽입할 원소와 같은 원소가 트리에 있으면 삽입할 수 없으므로 같은 원소가 트리에 있는지 탐색하여 확인
• 탐색에서 탐색 실패가 결정되는 위치가 삽입 원소의 자리가 된다.
• 탐색 실패한 위치에 원소를 삽입

 

1) 알고리즘

 

insertBST(bsT, x)
	p <- bsT;
	while(p != NULL) do{	// 삽입할 자리 탐색
		if(x = p.key)
			return;
		q <- p;
		if(x < p.key)
			p <- p.left;
		else p <- p.right;
	}

// 삽입할 노드 만들기

	new <- getNode();	
	new.key <- x;
	new.left <- NULL;
	new.right <- NULL;

// 삽입할 노드 만들기
    
// 탐색한 자리에 노드 연결

	if(bsT == NULL)
		bsT <- new;
	else if(x < q.key)
		q.left <- new;
	else 
		q.right <- new;
	return;

// 탐색한 자리에 노드 연결
end insertBST()

 

4. 삭제 연산

• 삭제할 노드의 위치를 찾기 위해 탐색 연산 수행
• 탐색하여 찾은 노드 삭제
   - 삭제할 노드가 단말 노드일 때 : 차수 0
   - 삭제할 노드가 하나의 자식 노드일 때 : 차수 1
   - 삭제할 노드가 두 개의 자식 노드일 때 : 차수 2
• 노드의 삭제 후에도 이진 탐색 트리를 유지해야 하므로 삭제 노드의 경우에 대한 후속 처리(이진 탐색 트리의 재구성 작업)가 필요

 

1) 알고리즘

 

deleteBST(bsT, x)
	p <- 삭제할 노드;
	parent <- 삭제할 노드의 부모 노드;
	if(p == NULL) return;
	if(p.left == NULL and p.right == NULL){	// 1. 단말 노드 삭제, 자식 노드 없음(차수 0)
		if(parent.left == p) parent.left <- NULL;
		else parent.right <- NULL;
	}
	else if(p.left == NULL or p.right == NULL){	// 2. 차수가 1인 노드 삭제
		if(p.left != NULL){		// 왼쪽 자식 노드를 가진 경우
			if(parent.left == p) parent.left <- p.left;
			else parent.right <- p.left;
		}
		else{	// 오른쪽 자식 노드를 가진 경우
			if(parent.left == p) parent.left <- p.right;
			else parent.right <- p.right;
		}
	}
	else if(p.left != NULL and p.right != NULL){	// 3. 차수가 2인 노드 삭제
		q <- maxNode(p.left);
		p.key <- q.key;
		deleteBST(p.left, p.key);
	}
end deletBST()

 

5. C언어 실습

 

#include <stdio.h>
#include <stdlib.h>
typedef struct TREENODE {
	char key;	// 데이터 필드
	struct TREENODE *left;	// 왼쪽 서브 트리 링크 필드
	struct TREENODE *right;	// 오른쪽 서브 트리 링크 필드
}TNODE;

// typedef char element;  char을 이진 탐색 트리 element의 자료형으로 정의


TNODE *insertNode(TNODE *p, char x) {	// 포인터 p가 가리키는 노드와 비교하여 노드 x를 삽입하는 연산
	TNODE *newNode;
	if (p == NULL) {	// 새로운 노드 만드는 연산
		newNode = (TNODE *)malloc(sizeof(TNODE));
		newNode->key = x;
		newNode->left = NULL;
		newNode->right = NULL;
		return newNode;
	}
	else if (x < p->key) p->left = insertNode(p->left, x);
	else if (x > p->key) p->right = insertNode(p->right, x);
	else printf("\n 이미 같은 키가 있습니다.\n");

	return p;
}

void deleteNode(TNODE *root, char key) {
// root 노드부터 탐색하여 key 값과 같은 노드를 찾아 삭제하는 연산
	
    TNODE *parent, *p, *succ, *succ_parent;
	TNODE *child;

	parent = NULL;
	p = root;

	while ((p != NULL) && (p -> key != key)) {	// 삭제할 노드의 위치 탐색
		parent = p;
		if (key < p -> key) p = p -> left;
		else p = p -> right;
	}
	if (p == NULL) {	// 삭제할 노드가 없는 경우
		printf("\n 찾는 키가 이진 트리에 없습니다.\n");
		return;
	}
	if ((p -> left == NULL) && (p -> right == NULL)) {	// 삭제할 노드가 단말 노드인 경우
		if (parent != NULL) {
			if (parent -> left == p) parent -> left = NULL;
			else parent -> right = NULL;
		}
		else root = NULL;
	}
	// 삭제할 노드가 한 개의 자식 노드를 가진 경우
	else if ((p -> left == NULL) || (p -> right == NULL)) {		
		if (p -> left != NULL) child = p -> left;
		else child = p -> right;

		if (parent != NULL) {
			if (parent -> left == p) parent -> left = child;
			else parent -> right = child;
		}
		else root = child;
	}
	else {	// 삭제할 노드가 두 개의 자식 노드를 가진 경우
		succ_parent = p;
		succ = p -> left;
		while (succ -> right != NULL) {
			succ_parent = succ;
			succ = succ -> right;
		}
		if (succ_parent -> left == succ) succ_parent -> left = succ -> left;
		else succ_parent -> right = succ->left;
		p -> key = succ -> key;
		p = succ;
	}
	free(p);
}

TNODE *searchBST(TNODE *root, char x) {	// 이진 탐색 트리에서 킷값이 x인 노드의 위치를 탐색하는 연산
	TNODE *p;
	p = root;

	while (p != NULL) {
		if (x < p -> key) p = p -> left;
		else if (x == p -> key)	return p;
		else p = p -> right;
	}

	printf("\n 찾는 키가 없습니다.");
	return p;
}

void displayInorder(TNODE *root) {	// 이진 탐색 트리를 중위 순회하면서 출력하는 연산
	if (root) {
		displayInorder(root->left);
		printf(" %c,", root->key);
		displayInorder(root->right);
	}
}

void menu()
{
	printf("\n [ 메뉴 입력 ]\n");

	printf(" 1 : 트리 출력, ");
	printf("2 : 문자 삽입, ");
	printf("3 : 문자 삭제, ");
	printf("4 : 문자 검색, ");
	printf("5 : 종료");;
	printf("\n -------------------------------------------------------- \n\n");

}

int main() {
	TNODE *root = NULL;
	TNODE *foundedNode = NULL;
	char choice, key;

	root = insertNode(root, 'G');	// 트리 만들기
	insertNode(root, 'T');
	insertNode(root, 'H');
	insertNode(root, 'D');
	insertNode(root, 'B');
	insertNode(root, 'M');
	insertNode(root, 'N');
	insertNode(root, 'A');
	insertNode(root, 'J');
	insertNode(root, 'E');
	insertNode(root, 'Q');

	while (1) {
		menu();
		choice = getchar(); getchar();

		switch (choice) {
		case '1':
			printf("\t [이진 트리 출력] ");
			displayInorder(root);
			printf("\n");
			break;

		case '2':
			printf(" 삽입할 문자를 입력하세요 : ");
			key = getchar(); getchar();
			insertNode(root, key);
			break;

		case '3':
			printf(" 삭제할 문자를 입력하세요 : ");
			key = getchar(); getchar();
			deleteNode(root, key);
			break;

		case '4':
			printf(" 찾을 문자를 입력하세요 : ");
			key = getchar(); getchar();
			foundedNode = searchBST(root, key);
			if (foundedNode != NULL)
				printf("\n %c를 찾았습니다.\n", foundedNode->key);
			else printf("\n 문자를 찾지 못했습니다.\n");

			break;

		case '5':
			return 0;

		default:
			printf(" 없는 메뉴입니다. 메뉴를 다시 선택하세요.\n");

			break;
		}
	}
}

 

이진 탐색 트리 실행

 

 

강의의 코드를 보면 char가 아닌 element가 나와야 하는 곳인데 char가 그대로 사용한 곳이 2곳이나 있다.

형 재선언으로 인해 간단한 코드조차 이해하기 어려워지는 심각한 문제가 있다. 형 재선언을 사용할 때는 체계적인 준비를 전제로 해야 한다.

알기 쉽고 자주 사용하는 char형같이 비슷한 형식들을 다른 형식으로 고쳐서 사용하면 작성하는 사람도 헷갈리고 보는 사람도 이해하기 어려워진다. 그래서  "typedef char element;" 이 코드를 주석 처리했다. 

 

char형을 그대로 사용했다면 위 코드는 없어도 된다. 필요 없는 살을 붙여서 자주 사용하는 형식을 버리고 더 이해하기 어려운 코드를 만드는 것은 좋지 않다.

별도의 주석 문이 없어도 누구나 이해하기 쉬운 코드를 만들기 위한 노력이 중요하다.

 

앞 포스팅들은 define 또는 typedef로 형 재선언을 그냥 따라 적었지만 보기도 어렵고 강의 내용에서도 실수하는 것을 보고 자주 사용하는 기본 형식들의 형 재선언은 주석 처리하겠다.