[자료구조] 이진 탐색 트리(Binary Search Tree)의 정의, 노드 탐색, 삽입, 삭제

이진 탐색 트리(Binary Search Tree)는 이진 트리 기반의 탐색을 위한 자료구조이다.

이진 탐색 트리의 정의

 

1. 모든 원소의 키는 유일한 키를 가진다.
2. 왼쪽 서브 트리 키들은 루트 키보다 작다.
3. 오른쪽 서브 트리의 키들은 루트의 키보다 크다.
4. 왼쪽, 오른쪽 서브 트리 모두 이진 탐색 트리이다.

 

위의 이진 탐색 트리에서,
15의 값을 가진 노드의 왼쪽 서브트리에 있는 값들(5,7,10)은 루트 노드인 15보다 모두 작고,
오른쪽 서브트리에 있는 값들(16, 18, 19, 20)은 모두 15보다 큰 값들이다.

이진 탐색 트리를 중위 순회 방법으로 순회하면,
5 -> 7 -> 10 -> 15 -> 16 -> 18 -> 19 -> 20 -> 22 -> 36 -> 45 ->60 으로
숫자들의 크기 순이다. 이는, 이진 탐색 트리가 어느정도 정렬된 상태를 유지하고 있음을 보여준다.

 

---

이진 트리 탐색

1. 순환적인 탐색 연산

// 순환적 탐색 함수
TreeNode* search(TreeNode* node, int key) {
	TreeNode* p = node;

	if (node == NULL) return NULL;  // 탐색 실패한 경우(마지막 노드까지 도달)

	if (key == node->data) return node; // 탐색 성공한 경우 해당 노드 주소 반환
	else if (key > node->data)
		search(node->right, key);
	else
		search(node->left, key);
}

2. 반복적인 탐색 연산

// 반복적 탐색 함수
TreeNode* search2(TreeNode* node, int key) {
	while (node != NULL) {
		if (key == node->data)return node; // 탐색 성공한 경우 해당 노드 주소 반환
		else if (key < node->data)
			node = node->left;
		else
			node = node->right;
	}
	return NULL; // 마지막까지 도달 - 탐색에 실패하여 NULL반환
}

 

---

이진 탐색 트리에서의 삽입 연산

이진 탐색 트리에서 원소를 삽입하기 위해선 먼저 탐색을 수행해야 한다.
그 이유는,

1. 같은 키값을 갖는 노드가 없어야 하고
2. 타색에 실패한 위치가 새로운 노드를 삽입하는 위치가 되기 때문

이진 탐색 트리의 성질을 이용하여,
새로운 노드를 삽입하는 위치를 탐색하여, 탐색에 실패하는 곳에서 원소를 삽입해야 한다.
새로운 노드는 항상 단말노드에 추가된다.

1. 순환적인 삽입 연산

// 트리의 새로운 노드 동적 할당
TreeNode* new_node(int item) {
	TreeNode* temp = (TreeNode*)malloc(sizeof(TreeNode));
	temp->data = item;
	temp->left = temp->right = NULL;
	return temp;
}

// 탐색 후 특정 위치에 새로운 key를 갖는 노드 삽입
TreeNode* insert_node(TreeNode* node, int key) {
	
	// 트리가 공백이면 새로운 노드를 반환
	if (node == NULL)return new_node(key);
	
	if (key < node->data)
		node->left = insert_node(node->left, key);
	else if (key > node->data)
		node->right = insert_node(node->right, key);

	// 변경된 루트 포인터 반환
	return node;
}

순환적으로 탐색을 반복하며, 탐색 실패의 경우 (null값인 node에 도달하는 경우)
key 값을 data로 대입한 새로운 노드를 동적 할당 받아 해당 위치에 노드를 삽입한다.

 

 

2. 반복적인 삽입 연산

// 노드 삽입 (반복)
void insert_node_iter(TreeNode** root, int key) {
	TreeNode* p, * t;	// p: 부모노드, t: 현재노드
	TreeNode* n;		// n: 새로운 노드

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

	// key가 트리 안에 없으므로 삽입
	n = (TreeNode*)malloc(sizeof(TreeNode));
	if (n == NULL)return;
	n->key = key;
	n->left = n->right = NULL;

	// 부모 노드와 링크 연결
	if (p != NULL)
		if (key < p->key)p->left = n;
		else p->right = n;
	else *root = n;
}

---

이진 탐색 트리에서 삭제 연산

노드를 삭제하는 경우, 먼저 해당 키 값을 갖는 노드를 탐색한다.
탐색에 성공한 경우, 다음의 3가지 경우를 고려하여 삭제 연산을 수행해야 한다.

1. 삭제하려는 노드가 단말 노드인 경우
2. 삭제하려는 노드가 하나의 왼쪽이나 오른쪽 서브 트리 중 하나만 가지는 경우
3. 삭제하려는 노드가 두 개의 서브 트리 모두 가지고 있는 경우

첫번째 경우, 단말 노드의 부모 노드를 찾아 링크 필드를 null 값으로 바꾸어 연결을 끊고, 해당 단말 노드의 메모리를 해제하면 된다.
두번째 경우, 자신 노드를 삭제하고 서브 트리는 자기 노드의 부모 노드에 그대로 붙여주면 된다.




마지막 세번째의 경우는 조금 복잡하다.
삭제하려는 노드의 위치에 다른 노드를 가져와 공백의 자리를 메꿈으로써,
다른 노드들을 변경시키지 않고 이진 탐색 트리의 조건을 만족시켜야 한다.
이를 위해 삭제되는 노드와 가장 값이 비슷한 노드자를 후계자로 선택해야 한다.

삭제하려는 노드와 가장 가까운 노드는,
삭제 대상 노드의 왼쪽 서브 트리에서 가장 큰 값(가장 오른쪽에 있는 노드)
또는 오른쪽 서브 트리에서의 가장 작은 값(가장 왼쪽에 있는 노드)이다.
이 두 노드들은 각각 이진 탐색 트리를 중위순회하였을 때 삭제 노드의 선행노드와 후속노드에 해당한다.


후계자를 오른쪽 서브트리에서의 가장 작은 값으로 설정해보자.
오른쪽 서브트리에서 왼쪽 자식 링크를 타고 NULL을 만날 때까지 계속 진행하면 된다.

// 노드 탐색 후 삭제
TreeNode* delete_node(TreeNode* root, int key) {
	if (root == NULL) return root;

	// 탐색
	if (key < root->data)
		root->left = delete_node(root->left, key);
	else if (key > root->data)
		root->right = delete_node(root->right, key);
	// 탐색 성공한 경우 (key==root->data)
	else {
		// 왼쪽 자식 노드가 없는 경우 - 오른쪽 자식 노드 연결
		if (root->left == NULL) {
			TreeNode* temp = root->right;
			free(root);
			return temp;
		}
		// 오른쪽 자식 노드가 없는 경우 - 왼쪽 자식 노드 연결
		else if (root->right == NULL) {
			TreeNode* temp = root->left;
			free(root);
			return temp;
		}
		// 세번째 경우
		// 오른쪽 서브트리에서 가장 왼쪽 단말 노드 탐색
		TreeNode* temp = min_value_node(root->right);

		// 후계 노드 복사 (데이터필드)
		root->data = temp->data;
		// 후계 노드 삭제 (단말 노드이므로 메모리 해제)
		root->right = delete_node(root->right, temp->data);
	}
	return root;
}

오른쪽 자식 노드가 없는 경우, 혹은 왼쪽 자식 노드가 없는 경우는
반대편 자식 노드를 연결해주면 된다.

자식 노드가 모두 있는 경우에는, min_value_node(root->right) 을 호출하여
오른쪽 서브트리에서 가장 왼쪽에 위치한 단말 노드, 즉 오른쪽 서브트리에서의 가장 큰 값을 탐색하여
데이터 값을 복사하고, 해당 노드를 삭제하도록 한다.

// 가장 왼쪽 단말 노드 탐색
TreeNode* min_value_node(TreeNode* node) {
	TreeNode* current = node;

	while (current->left != NULL)
		current = current->left;

	return current;
}

 

반복적인 삭제 연산은 다음과 같다.

// 노드 삭제 (반복)
void delete_iterative(TreeNode** root, int key) {
	// 탐색 후 삭제
	// p: 부모
	// child: 
	TreeNode* p, * child, * succ, * succ_p, * t;

	// key를 갖는 노드 t 탐색, p는 t의 부모노드
	p = NULL;
	t = *root;

	// 먼저 트리에 키 값이 있는지 탐색
	while (t != NULL && t->key != key) {
		p = t;
		t = (key < t->key) ? t->left : t->right;
	}
	// 탐색 종료, 

	// 탐색이 종료된 시점에 t가 NULL이면 탐색 실패
	if (t == NULL) {
		printf("key is not in the tree \n");
		return;
	}

	// 첫번쨰 경우: 단말 노드인 경우
	if (t->left == NULL && t->right == NULL) {
		if (p != NULL) {
			// 부모노드의 자식필드를 NULL로 변경
			if (p->left == t)
				p->left = NULL;
			else p->right = NULL;
		}
		else
			*root = NULL; // 부모노드가 NULL이면 삭제되는 노드가 루트
	}

	// 두번째 경우: 하나의 자식만 가지는 경우
	else if ((t->left == NULL) || t->right == NULL) {
		child = (t->left != NULL) ? t->left : t->right;
		if (p != NULL) {
			// 부모를 자식과 연결
			if (p->left == t) p->left = child;
			else p->right = child;
		}
		else // 부모 노드가 NULL이면 삭제되는 노드가 루트
			*root = child;
	}
	// 세번째 경우: 두개의 자식을 가지는 경우
	else {
		printf("두 개 자식 \n\n");

		// 오른쪽 서브트리에서 후계자를 찾는다.
		succ_p = t;
		succ = t->right;
		// 후계자를 찾아 계속 왼쪽으로 이동
		while (succ->left != NULL) {
			succ_p = succ;
			succ = succ->left;
		}

		// 후속자의 부모와 자식 연결
		if (succ_p->left = succ)
			succ_p->left = succ->right;
		else succ_p->right = succ->right;

		// 후속자가 가진 키 값을 현재 노드에 복사
		t->key = succ->key;
		// 원래의 후속자 삭제
		t = succ;
	}
	free(t);
}

---

전체 프로그램은 다음과 같다.

#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct TreeNode{
	element data;
    struct TreeNode* left, * right;
}TreeNode;

// 순환적 탐색 함수
TreeNode* search(TreeNode* node, int key) {
	TreeNode* p = node;
    if (node == NULL) return NULL; // 탐색 실패한 경우(마지막 노드까지 도달)
    	if (key == node->data) return node; // 탐색 성공한 경우 해당 노드 주소 반환
    	else if (key > node->data)
        	search(node->right, key);
    else search(node->left, key);
}

// 반복적탐색 함수
TreeNode* search2(TreeNode* node, int key) {
	while (node != NULL) {
    	if (key == node->data)return node; // 탐색 성공한 경우 해당 노드 주소 반환
        else if (key < node->data) node = node->left;
        else node = node->right; } return NULL; // 탐색에 실패한 경우 NULL반환
 }
 
 // 트리의 새로운 노드 동적 할당
 TreeNode* new_node(int item) {
 	TreeNode* temp = (TreeNode*)malloc(sizeof(TreeNode));
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
 }
 
 // 탐색 후 특정 위치에 새로운 key를 갖는 노드 삽입
 TreeNode* insert_node(TreeNode* node, int key) {
 	// 트리가 공백이면 새로운 노드를 반환
    if (node == NULL)return new_node(key);
    	if (key < node->data) node->left = insert_node(node->left, key);
        else if (key > node->data) node->right = insert_node(node->right, key);
    // 변경된 루트 포인터 반환 return node;
}

// 가장 왼쪽 단말 노드 탐색
TreeNode* min_value_node(TreeNode* node) {
	TreeNode* current = node;
	while (current != NULL)
		current = current->left;
	return current;
}

// 노드 탐색 후 삭제
TreeNode* delete_node(TreeNode* root, char word) {
	ListNode* q, * next;
	if (root == NULL) return root;

	if (compare(word, root->key->data.word) < 0)
		root->left = delete_node(root->left, word);
	if (compare(word, root->key->data.word) > 0)
		root->right = delete_node(root->right, word);
	// Ű�� ��Ʈ�� ���� ���
	else {
		if (root->left == NULL) {
			TreeNode* temp = root->right;
			
			q = root->key;
			while (q != NULL) {
				next = q->link;
				free(q->data.word);
				free(q->data.meaning);
				q = next;
			}
			free(root);
			return temp;
		}
		else if (root->right == NULL) {
			TreeNode* temp = root->left;
			q = root->key;
			while (q != NULL) {
				next = q->link;
				free(q->data.word);
				free(q->data.meaning);
				q = next;
			}
			free(root);
			return temp;
		}

		TreeNode* temp = min_value_node(root->right); 

		root->key = temp->key;
		root->right = delete_node(root->right, word);
	}
	return root;
}

int main() {
	TreeNode* root = NULL;
    TreeNode* tmp = NULL;
    int key;
    
    root = insert_node(root, 30);
    root = insert_node(root, 20);
    root = insert_node(root, 25);
    root = insert_node(root, 36);
    root = insert_node(root, 60);
    root = insert_node(root, 40);
    root = insert_node(root, 50);
    printf("이진 탐색 트리 중외 순회 결과 \n");
    
    inorder(root);
   
    printf("\n\n탐색하고자 하는 키 값 : ");
    scanf("%d", &key);
    
    if (search(root, key) != NULL)
    	printf("이진 탐색 트리에서 %d 발견 \n", key);
    else printf("이진 탐색 트리에서 %d 발견 실패 \n", key);
}