이진탐색트리(Binary Search Tree, BST)

이진탐색트리(BST)

이진탐색트리는 트리의 대표적인 형태로 말 그대로 이진트리 중에서도 탐색에 특화된 트리이다. 탐색에 특화된 이유는  트리 내부 부모노드의 값은 왼쪽 자식노드의 값보다 크고 오른쪽 자식노드의 값보다 작다는 특성을 지니고 있기 때문이다. 그래서 실제 값이 들어있는 이진탐색트리를 살펴보면 아래와 같다.

출처 위키디피아

이 트리를 전위순회방식으로 탐색하면 "1 3 4 6 7 8 10 13 14" 로 값을 오름차순으로 출력할 수 있다. 즉 아까의 특성 때문에 값을 찾기 쉽기 때문에 이진탐색트리라고 한다. 

 

이진탐색트리는 Node와 NodePointer를 통해서 구현할 수 있는데, 아까의 특성을 지키기 위해 아래의 로직으로 구현할 수 있다.

 

• 삽입은 삽입하고자 하는 값이 부모노드보다 작으면 왼쪽 자식노드로, 크면 오른쪽 자식노드로 이동하면서 비어있는 위치에 도달할 때까지 이동한다. 그리고 비어있는 위치에 값을 추가한다.
• 삭제는 크게 2가지의 경우를 고려한다. 
• 삭제하고자 하는 노드가 자식노드가 두 개 있을 경우, 오른쪽 서브트리 중 가장 작은 값(왼쪽 서브트리 중 가장 큰 값도 가능)을 가지고 와 삭제하고자 하는 노드와 값을 바꾼 후 값을 교환한 노드를 삭제한다. (아래 그림 참고)
• 삭제하고자 하는 노드가 자식노드가 한 개 이하일 경우, 자식 트리를 가지고와 삭제하고자 하는 부모 노드 위치에 삽입한다(자식노드가 0개 일 경우도 이 로직으로 가능, NULL도 자식 노드로 생각할 경우).  

15 값을 삭제하고자 할경우 오른쪽 서브트리 중 가장 작은 값을 가지고와 값 교환 후 노드 삭제

---

이진탐색트리 구현

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

// Node 자료형 선언
typedef struct node* nodePointer;
typedef struct node {
	int value;
	nodePointer lch, rch;
}node;

// BST 함수 선언
nodePointer insertNode(nodePointer root, int value);
nodePointer findMinNode(nodePointer root);
nodePointer deleteNode(nodePointer root, int value);
void printTree(nodePointer root);

// 삽입
nodePointer insertNode(nodePointer root, int value) {
	// 초기화
	if (root == NULL) {
		root = (nodePointer)malloc(sizeof(node));
		root->lch = root->rch = NULL ;
		root->value = value;
		return root;
	}

	// 그외 위치 찾아서 삽입(재귀적)
	else {
		// 작을 경우 왼쪽 자식 트리
		if (root->value > value) {
			root->lch = insertNode(root->lch, value);
		}

		// 클 경우 오른쪽 자식 트리
		else {
			root->rch = insertNode(root->rch, value);
		}
	}

	return root;
}

// 최소노드 찾기
nodePointer findMinNode(nodePointer root) {
	nodePointer search_np = root;
	while (search_np->lch != NULL) {
		search_np = search_np->lch;
	}
	return search_np;
}

// 삭제
nodePointer deleteNode(nodePointer root, int value) {
	nodePointer t_np = NULL;
	
	// NULL
	if (root == NULL) {
		return NULL;
	}
	
	// 탐색
	// 작을 경우
	if (root->value > value) {
		root->lch =	deleteNode(root->lch, value);
	}
	// 클 경우
	else if(root->value < value){
		root->rch = deleteNode(root->rch, value);
	}
	// 찾았을 경우
	else {
		// 자식노드가 두개 있을경우(바로 다음값 가져와서 교환)
		if (root->lch != NULL && root->rch != NULL) {
			t_np = findMinNode(root->rch);
			root->value = t_np->value;
			root->rch = deleteNode(root->rch, t_np->value); // 오른쪽 트리 끝값 삭제
		}

		// 자식노드가 하나 이하일 경우
		else {
			t_np = (root->lch == NULL) ? root->rch : root->lch;
			free(root); // 삭제
			return t_np; // 자식트리를 반환한다
		}
	}
	return root;

}

// 전위 순회 방식 
void printTree(nodePointer root) {
	if (root == NULL) {
		return;
	}

	printTree(root->lch);
	printf("%d ", root->value);
	printTree(root->rch);
}


void main() {
	nodePointer root = NULL;
	
	root = insertNode(root, 8);
	root = insertNode(root, 12);
	root = insertNode(root, 19);
	root = insertNode(root, 15);
	root = insertNode(root, 6);
	root = insertNode(root, 2);
	root = insertNode(root, 25);
	root = insertNode(root, 3);
	root = insertNode(root, 5);
	
	printTree(root);

	root = deleteNode(root, 6);
	root = deleteNode(root, 12);
	root = deleteNode(root, 5);

	printf("\n");
	printTree(root);

}

 

참고 : 깃헙 블로그