이진 탐색 트리 구현(연결리스트)

이진트리는 배열의 방식으로도, 연결리스트의 방식으로도 구현이 가능합니다.

연결리스트의 경우, 공간의 낭비 없이 필요할 때만 공간을 만들어서 편향 이진트리가 나온다고 해도

공간의 낭비가 전혀 없다는 장점이 있죠.

 

이번에는 이진 트리가 아닌 '이진 탐색' 트리를 구현해 보겠습니다.

이진 트리는 자식이 최대 2개 이하만 되면 모든 조건을 만족하니, 어렵지 않습니다.

이진 탐색트리는 여기에 추가적인 조건이 붙습니다.

 

출처 : [네이버 지식백과] - 이진 탐색 트리

1. 모든 노드는 다른 값을 갖는다.

2. 왼쪽 서브 트리의 데이터 값은 부모 노드의 데이터 값보다 작은 값을 갖는다.

3. 오른쪽 서브 트리의 데이터 값은 부모 노드의 데이터 값보다 큰 값을 갖는다.

4. 왼쪽, 오른쪽 서브트리도 이진 탐색 트리이다.

 

위의 정의에 맞게 C로 구현을 해보겠습니다.

 

이진 탐색 트리 예시

1. 이진 트리의 노드 정의 : 노드가 가질 값 data, 왼쪽 자식을 나타낼 left, 오른쪽 자식을 나타낼 right

typedef struct Node // 이진 트리의 노드를 정의.
{
	int data;
	Node* left; // 왼쪽
	Node* right; // 오른쪽
};

 

예시에서 data를 int형으로 받았을 뿐, 문자형의 입력도 가능하고  다 가능합니다.

 

 

2. 노드의 생성(노드가 필요할 때마다 동작할 코드임)

Node* getNode(int data) // 노드를 할당
{
	Node* newNode = (Node *)malloc(sizeof(Node));

	newNode->data = data;
	newNode->left = NULL;
	newNode->right = NULL;

	return newNode;
}

입력한 data를 값으로 가지는 노드를 1개 생성해주는 과정입니다.

처음 생성된 이 노드는 자식이 아무것도 없고 값만 있는 상태입니다.

 

3. 노드의 추가(생성된 노드를 추가하는 동작)

Node* addNode(Node* node, int data) // 노드 추가
{
	if (node == NULL)
	{
		node = getNode(data);
	}

	else if (node->data == data)
	{
		printf("중복 요소로 실패\n");
	}

	else if (node->data > data)
	{
		node->left = addNode(node->left, data);
	}
	else
	{
		node->right = addNode(node->right, data);
	}

	return node;
}

1) 만약 노드가 아무것도 없다면 노드를 생성하고 데이터를 그대로 넣어주는 것으로 종료

2) 해당 데이터가 이미 트리에 있는 상태라면 '중복'의 상태에 위배이므로 add를 하지 않음

3) 노드의 데이터보다 추가하려는 데이터가 '작다면' 추가하려는 데이터를 이진 탐색트리 정의에 의해 왼쪽으로 보냄

   → 왼쪽으로 내려갔는데 비어있다면 재귀적 호출에 의해 현재 자리에 getNode(data)를 하고 종료할 것입니다.

4) 노드의 데이터보다 추가하려는 데이터가 '크다면' 추가하려는 데이터를 이진 탐색트리 정의에 의해 오른쪽으로 보냄

   → 오른쪽으로 내려갔는데 비어있다면 재귀적 호출에 의해 현재 자리에 getNode(data)를 하고 종료할 것입니다.

 

 * 이진탐색트리의 정의에 의해 data의 크고 작음을 비교함으로써 자연스럽게 정렬을 해주게 됩니다.

 

4. 노드를 탐색(data라는 값을 가진 노드를 반환)

Node* searchNode(Node *ptr, int data) // data라는 값을 가진 노드를 찾는 과정
{
	if (ptr == NULL)
	{
		printf("해당 노드 없음\n");
		return NULL;
	}

	else if (ptr->data == data)
	{
		printf("노드 존재");
		return ptr;
	}

	else if (ptr->data > data)
	{
		searchNode(ptr->left, data);
	}
	else
	{
		searchNode(ptr->right, data);
	}

}

1) 노드가 태초부터 존재하지 않았거나, 탐색을 했는데도 data값을 가진 노드가 존재하지 않았을 경우에는 NULL 반환

2) 찾고자하는 데이터가 존재한다면 그대로 return해준다

3) 찾고자하는 데이터가 현재 위치의 노드의 값보다 '작다면' 이진 탐색트리 정의에 의해 왼쪽으로 이동하여 탐색

4) 찾고자하는 데이터가 현재 위치의 노드의 값보다 '크다면' 이진 탐색트리 정의에 의해 오른쪽으로 이동하여 탐색

 

계속하여 같은 말을 반복하고 있죠?

이진 탐색 트리는 왼쪽의 서브트리는 작은 값을, 오른쪽의 서브트리는 큰 값을 저장하기 때문에

찾고하자는 데이터값의 크기에 따라 왼쪽 / 오른쪽으로 내려가는 것을 자연스럽게 재귀적 호출로 수행해줍니다.

그렇게 해서 마지막까지 탐색했는데도 불구하고 없다면 1)의 경우에 가게 됩니다.

 

5. 모든 노드의 데이터 출력

void showTree(Node* tree)
{
	if (tree != NULL)
	{
		showTree(tree->left);
		printf("%d ", tree->data);
		showTree(tree->right);
	}
}

왼쪽 -> 중앙 -> 오른쪽 순서로 출력하도록 하였습니다.

전위, 중위, 후위 순회 등의 여러가지 테크닉이 있으나 그것은 나중에 설명하기로 하겠습니다.

왼쪽의 끝까지 갔다가 더이상 없으면 값 출력, 올라와서 출력, 오른쪽이 있나 없나 검사후 ..... 출력 출력!

 

6. 모든 노드의 메모리 해제

void deleteTree(Node* tree)
{
	if (tree != NULL)
	{
		deleteTree(tree->left);
		deleteTree(tree->right);
		free(tree);
	}
}

노드의 메모리 해제 순서가 중요합니다.

어떠한 노드 A가 왼쪽, 오른쪽 자식을 가지는 노드라고 가정하겠습니다

이 A를 자식들의 메모리를 해제하지 않고 바로 해제해버리는 경우, A->left와 A->right는 해제되지 않은 상태로 존재합니다. 부모가 없기 때문에 더이상 존재하지 않아야 하는데,

실제로 A->left와 A->right는 어떠한 곳에서 메모리를 차지하고 있는 격이 되는 것입니다.

이를 방지하기 위해 우선 노드에서 left까지 쭉 내려간 후, 그 노드가 NULL이라면 left메모리 해제후

중앙으로 가지  않고! right로 쭉 내려가줍니다. 아직 오른쪽 자식이 남아있죠?

재귀적 정의에 의해 right로 내려갔다고 해도, right->left도 존재할 가능성이 있기 때문에 이들을 다 처리해주고 나서야

중앙을 처리할 수 있는 것입니다.

 

 

7. 노드의 삭제

Node *deleteNode(Node *root, int key)
{

	// root가 NULL 일 경우. 트리가 비어있을 경우.
	if (root == NULL) {
		return root;
	}
	if (key < root->data) {
		root->left = deleteNode(root->left, key);
	}
	else if (key > root->data) {
		root->right = deleteNode(root->right, key);
	}
	else {
		if (root->left == NULL) {
			Node *temp = root->right;
			free(root);
			return temp;
		}
		else if (root->right == NULL) {
			Node *temp = root->left;
			free(root);
			return temp;
		}
		Node *temp = minValueNode(root->right);
		root->data = temp->data;
		root->right = deleteNode(root->right, temp->data);

	}
	return root;
}

 

 1) 트리가 비어있을 경우 NULL 출력

 2) 찾고자 하는 데이터가 현재 노드의 데이터보다 작은 경우 왼쪽, 크다면 오른쪽 이동

 3) 데이터를 찾은 경우

    * 삭제할 노드의 자식이 한 개도 없는 경우 알아서 삭제됨.(if문을 거치므로)

    * 삭제할 노드의 자식이 한 개인 경우

       - 오른쪽 자식만 존재하는 경우 temp에 오른쪽을 저장 후 현재 노드를 해제, temp를 반환하고 재귀를 벗어나면서

         반환된 값이 왼쪽이나 오른쪽에 연결됩니다.

       - 왼쪽 자식만 존재하는 경우 temp에 왼쪽을 저장 후 현재 노드를 해제, temp를 반환하고 재귀를 벗어나면서

         반환된 값이 왼쪽이나 오른쪽에 연결됩니다.

   * 삭제할 노드의 자식이 두 개인 경우

      - 두가지 방법이 존재합니다.

        1) 왼쪽 서브트리에서 가장 큰 값을 가져온다

        2) 오른쪽 서브트리에서 가장 큰 값을 가져온다

   1)의 경우 왼쪽 서브트리에서 가장 큰 값을 안가져오는 경우 왼쪽 자식은 항상 작다는 정의에 위배됩니다.

   2)의 경우 오른쪽 서브트리에서 가장 작은 값을 안가져오는 경우 오른쪽 자식은 항상 크다는 정의에 위배됩니다

      →즉, 이진 탐색 트리의 정의에 위배되므로 왼쪽 오른쪽 누군가를 선택하는것은 선택사항이나 반드시 정의를 지킨 상태로 왼쪽, 오른쪽을 이용해주어야 합니다. 여기에서는 오른쪽 서브트리에서 가장 큰 값을 가져오겠습니다.

 

   *삭제할 노드의 자식이 두개인 경우 오른쪽 서브트리에서 가장 작은 값을 가져와서 대체한다

     - 오른쪽 서브트리에서 가장 작은 값을 찾기위해 minValueNode라는 함수로 값을 찾아줍니다.

     - 값을 찾았다면, 삭제할 노드의 데이터를 minValueNode에서 찾은 값과 대체해줍니다. (즉, 같은 값이 2개있는 상태)

     - 현재 위치에서 오른쪽 서브트리에서 가장 큰 값을 삭제하는 재귀를 다시 반복해줍니다.

 

(작은 값을 찾는 함수)

Node *minValueNode(Node * node)
{
	BinNode *cur = node;

	while (cur && cur->left != NULL) {
		cur = cur->left;
	}
	return cur;
}

 

이진 탐색트리를 이렇게 구현해보았는데, 삭제가 제일 어렵습니다.

재귀는 문장 하나로 코드를 정리해준다는 점에서 간결하고 강력하지만,

호출에 호출을 연속으로 계속 깊게 들어가는 생각에 너무 깊어지다보면 머릿속에서 헷갈리는 느낌이 강합니다.

이진 탐색트리의 예시를 그림으로 그려보고 공부하면 훨씬 이해에 도움이 됩니다.

 

 

이진탐색트리는 삽입과 삭제에 아주 용이한 자료구조입니다.

Maximum depth(Height)가 8인 이진 탐색트리가 있다고 했을 때, 최대 노드의 개수는 2^(8+1) -1 = 511개입니다.

이 511개에서, 내가 원하는 위치에 삽입과 삭제를 하기 위해 걸리는 시간이 logN의 시간밖에 되지 않습니다.

즉, 높이의 횟수만큼만! 탐색을 하는 것을 보장합니다. (편향적으로 트리가 구성된다면 O(h) = O(n). 최악)

 

 

정의에 의해 왼쪽에는 항상 작은 값, 오른쪽에는 항상 큰 값이 들어가니

삽입이 계층적으로 이루어지기 떄문이죠.(깊이 1에 없다면 깊이 2에 있고, 깊이 2에 없다면 바로 깊이 3으로 ...)

 

 

C언어 | 이진 탐색 트리( Binary Search Tree) 만들기 | 추가, 삭제, 검색

구현은  '코딩각'님의 티스토리 블로그에서 참고하였습니다! 아무래도 제가 이 포스팅을 보고 구현의 버벅거림을

해결한 점이 큰 만큼 구현한 내용이 상당히 흡사합니다..

제 블로그를 보고  이해못하신 분은 위의 블로그도 참고해보세요. 상세한 설명을 해두셨습니다.

블로그의 주인분께서 출처를 남기고 본문을 인용해도 좋다고 하셔서 글의 출처를 남깁니다.