[BST] 이진 탐색 트리 알고리즘을 이용한 데이터 삽입,삭제(C언어코드포함)

댓글로 소스 문의가 많아서 파일로 첨부했습니다.

저도 학교 수업 들으면서 처음 짜본 코드라 부족하고, 틀린 부분도 있을 수 있지만

도움이 되면 좋겠네요

 

Binary_Search.zip

다운로드

 

이진 탐색 트리란? (BST)

이진 탐색 트리(binary search tree)는 데이터의 삽입, 삭제, 탐색 등이 자주 발생하는 경우에 효율적인 구조로, 이진 트리이면서 같은 값을 갖는 노드가 없어야 한다. 왼쪽 서브 트리에 있는 모든 데이터는 현재 노드의 값보다 작고, 오른쪽 서브 트리에 있는 모든 노드의 데이터는 현재 노드의 값보다 크다.

 

<이진  트리에서  데이터 z를 삽입하는 수도 코드>

 

BST-insert

 정렬되지 않은 배열 a를 key값으로 하는 이진탐색트리를 만들기 위해 차례로 insert함수에 넣어 트리의 루트부터 아래로 내려가면서 순차적으로 비교하면서 왼쪽자식, 오른쪽자식, key 값을 가지는 노드로 만들어(트리 구조체 이용) 삽입해 나간다. 삽입할 때는 해당 노드의 key값보다 작으면 왼쪽자식으로 이동하고 크면 오른쪽자식으로 이동하는 것을 반복하다가 삽입하려는 곳의 위치가 NULL이 되면 그때 해당 key값을 삽입한다.

 

 위의 이진 트리를 보면, 루트에 12가 있고 루트의 왼쪽 서브 트리에는 루트보다 작은 값이, 오른쪽 서브 트리에는 루트보다 큰 값이 달려있는 것을 볼 수 있다. 꼭 루트가 아니더라도 각각의 노드가 기준이 된다.

 예를 들어, 노드 18을 보면 노드 18의 왼쪽 서브 트리에는 18보다 작은 값이, 오른쪽 서브 트리에는 18보다 큰 값이 달려있는 것을 볼 수 있다.

 

이진 트리에서 데이터를 삭제할 때는 3가지의 경우의 수가 존재한다.

 

삭제하고자 하는 데이터를 x라고 했을 때

 

1. x의 자식이 없는 경우

 

2. x의 자식이 1개 있을 경우

 

3. x의 자식이 2개 있을 경우

 

<이진  트리에서  데이터 z를 삭제하는 수도 코드>

 

BST-delete

 delete의 경우에는 먼저 트리를 순회하면서 제거하고자 하는 key값을 가지는 노드의 위치를 알아내고 해당 노드의 부모노드의 위치도 같이 저장한다. 그리고 제거를 해야 하는데 이 때 방법이 3가지 경우에 따라 나뉜다.

 

1. 제거하고자 하는 노드의 자식이 하나도 없는 경우

제거하고자 하는 노드가 부모의 왼쪽과 오른쪽 중에 어디에 달려있는지 검사하고 해당자리를 NULL로 채운다.

 

2. 제거하고자 하는 노드의 자식이 모두(2개) 있을 경우

제거하고자 하는 노드를 기준으로 왼쪽 서브트리 중에서 가장 큰 key를 가지는 노드를 찾아내어 이 노드의 부모노드를 저장하고 해당 key를 제거하고자하는 노드의 key에 복사를 한다. 그리고 가장 큰 key를 가지고 있었던 노드의 왼쪽 자식을 처음에 저장했던 부모노드의 오른쪽자식으로 이어 붙인다.

 

3. 제거하고자 하는 노드의 자식이 왼쪽이나 오른쪽 중 하나만 있을 경우

 

① 오른쪽자식이 있는 경우

제거하고자 하는 노드가 부모의 왼쪽과 오른쪽 중에 어디에 달려있는지 찾은 후에 해당하는 곳에 제거하고자하는 노드의 오른쪽자식을 연결한다.

 

② 왼쪽자식이 있는 경우

제거하고자 하는 노드가 부모의 왼쪽과 오른쪽 중에 어디에 달려있는지 찾은 후에 해당하는 곳에 제거하고자하는 노드의 왼쪽자식을 연결한다.

 

코드

이진 트리 삽입

void tree_insert(tree *t, int key){
	tree *temp = t;

	if(temp==NULL){
		temp  = tree_create(key);
	}
	else{

	while(1){
		
			if(temp->key < key){
				if(temp->right ==NULL){
					temp->right = tree_create(key);
					break;
				}
				else{

					temp = temp-> right;
					
				}

			}

			else{
				if(temp->left ==NULL){
					temp->left= tree_create(key);
					break;
				}
				else{
					temp = temp-> left;
				}

			}
				
	}
	}
}

이진 트리 삭제

int tree_delete(tree *t, int key){

	tree *temp = t;
	tree *parent = temp;
	tree *del;

	while(temp->key != key){
		parent = temp;

		if(temp->key < key){
			temp = temp -> right;
		}
		else
			temp = temp -> left;
	}
    
	del = temp;

	if(temp->left==NULL && temp->right ==NULL){
		if(parent->left){
			if(temp->key==parent->left->key){
				parent->left=NULL; return 1;
			}
		}
		parent->right=NULL;
		printf("%d 제거\n",key);
		return 1;
		
	}
	
	else if(temp->left!=NULL && temp->right !=NULL){
		temp = temp->left;
		if(temp->right ==NULL){
				del->key = temp->key;
				del->left = temp->left;
				printf("%d 제거�\n",key);
				return 1;
			}
		while(1){
			if(temp->right ==NULL){
				del->key = temp->key;
				parent->right = temp->left;
				printf("%d 제거\n",key);
				return 1;
			}
			else{
				parent = temp;
				temp= temp->right;
			}
		}
	}
	
	else{
		if(temp->right != NULL){
			if(parent->left->key == key){
				parent->left =temp->right;
			}
			else{parent->right =temp->right;}
			printf("%d 제거\n",key);
			return 1;	
		}
		if(temp->left != NULL){
			if(parent->left->key == key){
				parent->left =temp->left;
			}
			else{parent->right =temp->left;}
			printf("%d 제거\n",key);
			return 1;	
		}
	}

}

Input Data

84 271 173 100 28 13 89 206 39 222 255 152 182 299 15

 

결과 화면