#3. 이진 탐색 트리

이진 탐색 트리

1.이진 탐색이 항상 동작하도록 구현하여 탐색속도를 극대화 시킨 자료구조를 이진 탐색 트리라 한다.

 

특징:

1.이진 탐색트리에서는 항상 부모 노드가 왼쪽 자식보다는 크고, 오른쪽 자식보다는 작다. 

이로인해 훨씬 더 빠르게 탐색이 가능하다.

예) 부모노드가 50이고 , 내가 찾을 숫자가 55라면,  왼쪽노드는 항상 부모노드보다 작으니,

오른쪽 노드만 탐색하면 된다.

 

2.이진 탐색 트리에서는 한 번 확인할 때마다 보아야 하는 원소의 개수가 절반씩 줄어든다는 점에서 '완전 이진 트리'

인 경우 탐색시간에 O(logN)의 시간 복잡도를 가진다.

 

이진 탐색 트리 알고리즘

찾고자하는 값이 부모노드 보다 작을경우 왼쪽 자식으로 ,  찾고자하는 값이 부모노드보다 클 경우 오른쪽자식으로 뻗어 나가며, 탐색한다.  

 

 

코드예시

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>


typedef struct {   //왼쪽자식과 오른쪽자식 구조체 선언
int data;
struct Node* leftChild;
struct Node* rightChild;
}Node;


//이진 탐색 트리의 삽입
Node* insertNode(Node* root, int data) {
if (root == NULL) {         //root가 NULL값이라면, 해당루트 초기화
root = (Node*)malloc(sizeof(Node));
root->leftChild = root->rightChild = NULL;
root->data = data;
return root;
}
else {
if (root->data > data) {   
root->leftChild = insertNode(root->leftChild, data);
}//루트가가지고있는데이터 > 삽입할데이터 ->왼쪽노드로 간다.
else {
root->rightChild = insertNode(root->rightChild, data); 
}//루트가가지고있는데이터 < 삽입할데이터 ->오른쪽노드로 간다.
}
return root;
}

//이진 탐색트리의 탐색

Node* searchNode(Node* root, int data) {
if (root == NULL) return NULL; 
//만약 탐색 실패시, NULL값 반환
if (root->data == data) return root;   
//특정한 데이터 찾을경우->특정데이터로 반환
else if (root->data > data) return searchNode(root->leftChild, data); 
//만약 루트가 가지고있는데이터>찾고자하는데이터 -> 왼쪽자식으로 탐색한다.
else return searchNode(root->rightChild, data);
} //그렇지 않다면, 오른쪽 자식으로 탐색 수행



//이진 탐색 트리의 순회
void preorder(Node* root) {
if (root == NULL) return;
printf("%d ", root->data);
preorder(root->leftChild);
preorder(root->rightChild);
}


//이진 탐색 트리 이용해보기
int main(void) {
Node* root = NULL;
root = insertNode(root, 20);
root = insertNode(root, 5);
root = insertNode(root, 25);
root = insertNode(root, 15);
root = insertNode(root, 30);
root = insertNode(root, 40);
root = insertNode(root, 7);
preorder(root);
system("pause");
}

 

결과값: 20 5 15 7 25 30 40

---

이진 탐색트리의 삭제

 

1.자식이 없는 경우

 

단순히 그냥 제거

 

2.자식이 하나만 존재하는 경우

 

삭제할 노드의 자리에 자식노드를 넣어준다.

 

3.자식이 둘 다 존재하는 경우

 

삭제할 노드의 자리에 자기 다음으로 큰 노드를 넣는다.

 

코드예시

 

//이진 탐색 트리의 가장 작은 원소 찾기 함수

Node* findMinNode(Node* root) {
	Node* node = root;
	while (node->leftChild != NULL) {
		node = node->leftChild;
	}
	return node;
}

//이진 탐색 트리의 삭제 함수

Node* deleteNode(Node* root, int data) {
	Node* node = NULL;
	if (root == NULL) return NULL;
	//찾고자하는 노드를 찾지못하면 NULL값 반환
	if (root->data > data) root->leftChild = deleteNode(root->leftChild, data);
	//삭제하고자하는 노드보다 현재노드가 더 크다면, 왼쪽 탐색
	else if (root->data < data) root->rightChild = deleteNode(root->rightChild, data);
	//그렇지 않다면, 오른쪽 탐색
	else {   //삭제할 노드를 찾은경우
		if (root->leftChild != NULL && root->rightChild != NULL) { //자식이 두개 전부 존재
			node = findMinNode(root->rightChild);
            //오른쪽자식에서 가장 작은걸 찾는것
			root->data = node->data; 
            //가장 작은걸 삭제할 노드자리로 넣는다(오른쪽 자식중 가장작은것은 부모다음으로 큰노드)
			root->rightChild = deleteNode(root->rightChild, node->data);
            //바꿔치기한 노드 지우기
		}
		else {// 왼쪽자식이 존재한다면, 왼쪽자식을 노드에, 오른쪽자식이 존재한다면, 오른쪽자식을 노드에 담는다.
			node = (root->leftChild != NULL) ? root->leftChild : root->rightChild;
			free(root); 
            //현재 자기 자신의 노드를 할당 해제 해준다.
			return node;
		}
	}
	return root;
}