이진 검색 트리

이진 탐색 트리란? 이진 트리 기반의 탐색을 위한 자료 구조이다.

• 모든 노드의 키는 유일하다.

• 왼쪽의 서브 트리에는 현재 노드보다 작은 키의 노드만 포함한다.

• 오른쪽의 서브 트리에는 현재 노드보다 큰 키의 노드만 포함한다.

• 서브 트리들도 이진 검색 트리이다.

• 검색, 삽입, 삭제 연산의 시간복잡도는 O(트리의 높이)이다.

’ C언어로 쉽게 풀어쓴 자료구조 ‘를 참고한 영어사전 이진 검색 트리 코드입니다.

#include<iostream>
using namespace std;
//영어 사전 항목의 구조 정의
typedef struct {
	char word[20];
	char mean[200];
}element;
//영어 사전 이진 트리의 노드 구조 정의
typedef struct treeNode {
	element key;
	struct treeNode* left;
	struct treeNode* right;
};
//포인터 p가 가리키는 노드와 비교하여 항목 key를 삽입하는 연산
treeNode* insertKey(treeNode* p, element key) {
	treeNode* newNode;
	if (p == NULL) {
		newNode = (treeNode*)malloc(sizeof(treeNode));
		newNode->key = key;
		newNode->left = NULL;
		newNode->right = NULL;
		return newNode;
	}
	else {
		int compare = strcmp(key.word, p->key.word);
		if (compare < 0) p->left = insertKey(p->left, key);
		if (compare == 0) cout << "이미 존재하는 단어\n";
		if (compare > 0) p->right = insertKey(p->right, key);
		return p;
	}
}
void insert(treeNode** root, element key) {
	*root = insertKey(*root, key);
}
treeNode* deleteNode(treeNode* root, element key) {
	treeNode* parent, * p, * succ, * succ_parent;
	treeNode* child;

	parent = NULL;
	p = root;
	//삭제할 노드 탐색
	while ((p != NULL) && (strcmp(p->key.word, key.word) != 0)) {
		parent = p;
		if (strcmp(key.word, p->key.word) < 0) p = p->left;
		else p = p->right;
	} 
	if (p == NULL) { // 삭제할 노드가 없는 경우
		cout << "삭제할 단어가 사전에 없음\n";
		return NULL;
	}
	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->right;
		while (succ->left != NULL) {
			succ_parent = succ;
			succ = succ->left;
		}
		if (succ_parent->left == succ) succ_parent->left = succ->right;
		else succ_parent->right = succ->right;
		p->key = succ->key;
		p = succ;
	}
	free(p);
	return root;
}

//이진 탐색 트리에서 키값이 key인 노드 위치를 탐색하는 연산
treeNode* searchBST(treeNode* root, element key) {
	treeNode* p;
	int compare;
	p = root;

	while (p != NULL) {
		compare = strcmp(key.word, p->key.word);
		if (compare < 0) p = p->left;
		if (compare > 0) p = p->right;
		if (compare == 0) {
			cout << "\n찾은 단어 : " << p->key.word;
			return p;
		}
	}
	return p;
}

//이진 탐색 트리를 중위 순회하면서 출력하는 연산
void displayInorder(treeNode* root) {
	if (root) {
		displayInorder(root->left);
		cout << '\n' << root->key.word << ' ' << root->key.mean;
		displayInorder(root->right);
	}
}

void menu() {
	cout << "\n*------------------------------*";
	cout << "\n\t1 : 출력";
	cout << "\n\t2 : 입력";
	cout << "\n\t3 : 삭제";
	cout << "\n\t4 : 검색";
	cout << "\n\t5 : 종료";
	cout << "\n*------------------------------*\n";
}
int main(void) {
	element e;
	treeNode* root = NULL, * temp = NULL;
	int choice;
	do {
		menu();
		cin >> choice;
		switch (choice) {
		case 1:
			cout << "\t[사전 출력]";
			displayInorder(root);
			cout << "\n\t[사전 끝]\n";
			break;
		case 2:
			cout << "\n[단어 입력] 단어를 입력하시오 : ";
			cin >> e.word;
			cout << "\n[단어 입력] 단어의 뜻을 입력하시오 : ";
			cin >> e.mean;
			insert(&root, e);
			break;
		case 3:
			cout << "\n[단어 삭제] 삭제할 단어 : ";
			cin >> e.word;
			root = deleteNode(root, e);
			break;
		case 4:
			cout << "\n[단어 검색] 검색할 단어 : ";
			cin >> e.word;
			temp = searchBST(root, e);
			if (temp != NULL) {
				cout << "\n단어 뜻 : " << temp->key.mean;
			}
			else cout << "\n사전에 없는 단어입니다.";
		}
	} while (choice != 5);
	return 0;
}