프로그래밍 공부

Binary Search Tree (수정예정) 본문

CS/Data Struct

Binary Search Tree (수정예정)

khj1999 2021. 6. 24. 17:45

이진검색트리 Binary Search Tree는 이진트리가 다음 조건을 만족하면 된다

1. 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값보다 작다
2. 오른쪽 서브 트리 노드의 키 값은 노드 N의 키 값보다 커야 한다.

3. 같은 키 값을 갖는 노드는 없다.

참고로 이진검색트리는 중위 순회를 하면 키 값의 오름차순으로 노드를 얻을 수 있다.


언어 :  C++

실행환경 : Visual Studio 2017

 

노드

struct BinNode { // 노드를 표현하는 구조체 
	int data; // 노드의 데이터를 나타냄
	 BinNode *left; // 왼쪽 자식 노드에 대한 포인터
	 BinNode *right; // 오른쪽 자식 노드에 대한 포인터
};

노드는 구조체를 사용해서 만든다.
구조체는 정수형인 data와 왼쪽 자식과 오른쪽 자식의 포인터로 구성하고 있다.

난 이진트리를 이해하기 편하게 data 즉 key 값을 정수형으로 설정했다.

 

노드의 설정

static BinNode *AllocBinNode(void) {
	return new BinNode; //(BinNode*)calloc(1, sizeof(BinNode)); // 동적할당으로 Node 생성
}

static void SetBinNode(BinNode *n, const int *x, const BinNode *left = NULL, const BinNode *right = NULL) { // 노드를 설정하는 함수
	n->data = *x; // 데이터
	n->left = (BinNode*)left; // 왼쪽 자식노드에 대한 포인터
	n->right = (BinNode*)right; // 오른쪽 자식 노드에 대한 포인터
}

 

n->left = (BinNode*)left; 와 n->right = (BinNode*)right;에는 NULL을 넣어준다
왜냐하면 새로 생긴 노드는 자식 노드가 없기 때문이다.

 

노드의 검색

bool compare(const int *x, const int *y) { // 비교함수
	return x == y ? true : false; // 참이면 true 반환 아니면 false 반환
}

BinNode *Search(BinNode *p, const int *key) { // 이진검색트리에서 노드를 검색하는 함수
	if (p == NULL) { // p가 NULL이면 더이상 노드가 없다는 뜻이니 
		return NULL; // NULL을 리턴
	}
	else if (compare(&p->data, key)) { // 값이 같으면 true
		return p; // 노드의 주소를 return
	}
	else if (*key < p->data) { // 키 값이 현재 노드 보다 작으면 왼쪽 자식으로 감(왼쪽 서브트리에서 검색)
		Search(p->left, key);
	}
	else if (*key > p->data) { // 키 값이 현재 노드 보다 크면 오른쪽 자식으로 감(오른쪽 서브트리에서 검색)
		Search(p->right, key);
	}
}

 

검색 순서

1. 노드의 검색은 루트부터 진행한다. 여기서 현재 노드는 p이다.

2. p가 NULL이면 찾는 값이 트리에 없다는 것 이거나 트리 자체가 없는 거니 검색에 실패한 것이다.

3. key값과 현재 노드의 값인 p의 데이터 값(p->data)을 비교해서

  • 같으면 검색에 성공하고 현재 노드의 주소를 반환한다.
  • key 값이 p->data보다 작으면 현재 노드에 왼쪽 자식 노드를 대입한다(왼쪽 서브 트리를 검색).
  • key 값이 p->data보다 크면 현재 노드에 오른쪽 자식 노드를 대입한다(오른쪽 서브 트리를 검색).

4. 2번 과정으로 되돌아간다

 

노드의 삽입

BinNode *Add(BinNode *p, const int *data) { // 이진검색트리에 노드를 삽입하는 과점
	if (p == NULL) { // NULL이면 이진검색트리가 비어있다는 뜻
		p = AllocBinNode(); // 새로 노드를 만들고
		SetBinNode(p, data, NULL, NULL); // 노드를 설정해줌
	}
	else if (compare(data, &p->data)) { // 데이터 값이 같으면
		cout << *data << "는 이미 등록되어 있습니다.\n";
	}
	else if (*data < p->data) { // 현재 노드보다 data 값이 작으면
		p->left = Add(p->left, data); // 선택한 노드에 왼쪽 자식 노드를 대입, Add함수에 왼쪽 자식노드를 전달하면서 재귀호출, 왼쪽 서브트리를 검색 
	}
	else if (*data > p->data) { // 현재 노드보다 data 값이 크면
		p->right = Add(p->right, data); // // 선택한 노드에 오른쪽 자식 노드를 대입, Add함수에 오른쪽 자식노드를 전달하면서 재귀호출, 오른쪽 서브트리를 검색
	}
	return p; // p를 반환
}

주의사항

  • 이진검색트리에서 노드를 삽입할 때 주의해야 할 점은 노드를 삽입한 다음에도 트리의 형태가
    이진검색트리의 조건을 충족시켜야 한다는 것이다. 따라서 노드를 삽입할 때는 알맞은 위치에 삽입해야 한다.
  • 이때 삽입할 노드의 키와 같은 값을 가지는 노드가 있다면 노드를 삽입해서는 안됩니다.

1. p에 루트 포인터를 대입합니다.

2. 삽입할 data값과 p의 값을 비교합니다. 값이 같다면 삽입에 실패합니다(종료).

- 값이 같지 않은 경우 key 값이 삽입할 값보다 작으면

   2-1 왼쪽 자식 노드가 없으면 노드를 삽입합니다

   2-2 왼쪽 자식 노드가 있는 경우에는 왼쪽 자식 노드 포인터를 대입

- 값이 같지 않은 경우 key 값이 삽입할 값보다 크면

   2-3 왼쪽 자식 노드가 없으면 노드를 삽입합니다

   2-4 왼쪽 자식 노드가 있는 경우에는 왼쪽 자식 노드 포인터를 대입

3. 2로 되돌아갑니다.

 

노드의 제거

int Remove(BinNode **root, const int *key) { // 노드 제거 함수
	BinNode *change, *remove_node;
	BinNode **Left_SubTree, **p = root; // RmLeft = 삭제할 노드의 왼쪽 서브트리에서 가장 큰값을 찾기 위한 변수, p == root의 주소
	                              // 2중 포인터를 사용한 이유는 루트만 있는 이진검색트리에서 루트 노드를 삭제할 경우 루트 포인터를 NULL로 해줘야한다
	while (true) { // 삭제할 노드를 찾는 과정 Search 함수와 유사함(반복)
		cout << *key << '\n';
		if (*p == NULL) {
			cout << *key << "는 등록되어 있지 않습니다.\n";
			return -1;
		}
		else if ((*p)->data == *key){ //(compare(&(*p)->data, key)) { // 같으면 종료
			break;
		}
		else if (*key < (*p)->data) {
			p = &((*p)->left); // 왼쪽 서브 트리에서 검색
		}
		else if (*key > (*p)->data) {
			p = &((*p)->right); // 오른쪽 서브 트리에서 검색
		}
	}
	if ((*p)->left == NULL) { // 삭제할 노드의 왼쪽 자식이 없으면
		change = (*p)->right; // 오른쪽 자식의 주소를 change에 넣음
	}
	else {
		Left_SubTree = &((*p)->left); // 삭제할 노드의 왼쪽 자식의 주소를 Left_SubTree 변수에 넣음  
		while ((*Left_SubTree)->right != NULL) { // Left_SubTree노드의 왼쪽 자식이 NULL이 될때까지 탐색 즉 삭제할 노드의 왼쪽 서브트리에서 가장 큰 값을 찾음
			Left_SubTree = &(*Left_SubTree)->right;
		}
		change = *Left_SubTree; // 가장 큰 노드를 삭제된 노드가 있는 자리로 옮기기위해 next에 넣음
		*Left_SubTree = (*Left_SubTree)->left; // 옮길 노드의 왼쪽 자식 노드를 옮길 노드의 주소로 바꿔줌
		change->left = (*p)->left; // 삭제할 노드의 왼쪽 자식의 주소를 옮길 노드의 왼쪽 자식 주소로 바꿔줌
		change->right = (*p)->right; // 삭제할 노드의 오른쪽 자식의 주소를 옮길 노드의 오른쪽 자식 주소로 바꿔줌
	}
	remove_node = *p; // 삭제할 노드의 주소를 remove_node에 넣음
	*p = change; // 옮길 노드를 삭제할 노드의 주소로로 바꿔줌
	delete remove_node; // reomove_node의 메모리를 해제해줌

	return 0;
}

참고로 이 글에서 가장 복잡한 부분이 삭제하는 부분이다.

 

자식 노드가 없는 노드를 삭제하는 경우

  • 삭제할 노드가 부모 노드의 왼쪽 자식이면 부모의 왼쪽 포인터를 NULL로 합니다.
  • 삭제할 노드가 부모 노드의 오른쪽 자식이면 부모의 오른쪽 포인터를 NULL로 합니다.

자식 노드가 1개인 노드를 삭제하는 경우

1. 삭제 대상 노드가 부모 노드의 왼쪽 자식인 경우

  • 부모의 왼쪽 포인터가 삭제 대상 노드의 자식을 가리키도록 합니다.

 

2. 삭제 대상 노드가 부모 노드의 오른쪽 자식인 경우

  • 부모의 오른쪽 포인터가 삭제 대상 노드의 자식을 가리키도록 합니다.

자식 노드가 2개인 노드를 삭제하는 경우

삭제할 노드의 왼쪽 서브 트리에서 가장 큰 키 값을 갖는 노드를 검색합니다.

가장 큰 키 값을 가지는 노드를 찾으면 삭제할 노드에 가장 큰 키값을 가지는 노드를 옮기면
삭제 과정은 끝납니다. 가장 큰 값의 노드를 옮기려면 먼저 노드의 데이터를

삭제할 노드의 위치로 복사합니다. 

그런 다음 원래 가장 큰 값의 노드를 트리에서 떼어내면 됩니다

 

 

이것을 정리하면

1. 삭제할 노드의 왼쪽 서브 트리에서 키 값이 가장 큰 노드를 검색합니다.

2. 검색한 노드를 삭제 위치로 옮깁니다(검색한 노드의 데이터를 삭제 대상 노드 위치로 복사합니다).

3. 옮긴 노드를 삭제합니다. 이때

  • 옮긴 노드에 자식이 없으면 - 자식 노드가 없는 노드의 삭제 순서에 따라 노드를 삭제합니다.
  • 옮긴 노드에 자식이 1개만 있으면 - 자식 노드가 1개 있는 노드의 삭제 순서에 따라 노드를 삭제합니다.

참고로 옮긴 노드에 자식이 2개가 있다는 조건이 있을 수 없는 게 삭제할 노드의 왼쪽 서브 트리에서 키 값이 가장
큰 노드를 검색해서 바꿔주기 때문이다 다시 말해 자식 노드가 2개가 있음 옮길 노드보다 더 큰 노드가 존재하는다는
거고 이는 옮긴 노드에 자식이 2개가 있다는 건 이진검색트리의 조건을 충족시킬 수가 없음을 뜻하기 때문이다.

 

마지막으로 매개변수의 자료형이 BinNode ** 인 이유는 루트만 있는 이진검색트리에서 루트 노드를 삭제할 경우에는
루트 포인터를 NULL로 업데이트하기 때문입니다.

 

트리의 출력

void PrintTree(const BinNode *p) { // Tree를 출력하는 함수
	if (p != NULL) { // NULL Pointer면 아무것도 하지 않고 종료
		PrintTree(p->left); // 오름차순으로 출력하기 위해 중위 순회 방법으로 트리를 탐색
		cout << "노드에 저장되어 있는 값은 : " << p->data << '\n';
		PrintTree(p->right);
	}
}

모든 노드를 오름차순으로 출력하는 함수입니다.

오름차순으로 출력하기 위해 중위 순회 방법으로 트리를 검색합니다.

 

트리의 삭제

void FreeTree(BinNode *p) { // 모든 노드를 삭제
	if (p != NULL) {
		FreeTree(p->left); // 후위 순회 방법으로 트리를 탐색하고 삭제함
		FreeTree(p->right);
		delete p; // 메모리 해제
	}
}

모든 노드를 삭제하는 함수로 후위 순회로 트리를 검색하면 삭제를 진행합니다.

참고로 왜 후위 순회를 하냐면

전위 순회를 한다 가정하면 부모 - 왼쪽 - 오른쪽 이 순서대로 삭제를 하는데 

부모 노드를 삭제하면 부모 노드의 왼쪽과 오른쪽 자식 노드의 주소는 다른 어떤 노드도 가지고 있지 않기 때문에

부모 노드를 마지막으로 삭제하는 후위 순회로 트리를 삭제해야 한다

 

 

이진검색트리 코드

#include <iostream>
#include <string>
using namespace std;
// 노드가 왼쪽 자식과 오른쪽 자식을 갖는 트리를 이진트리하고함 이때 각 노드의 자식은 2명 이하만 유지함
// 완전이진트리는 루트부터 노드가 채워져있으면서 같은 레벨에서는 왼쪽에서 오른쪽으로 노드가 채워져 있는 이진트리를 완전이진트리라고 함
// 이진검색트리는 이진 트리가 아래 조건을 만족하면 된다
// 이진검색트리는 어떤 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 N키 값보다 작아야함
// 오른쪽 서브트리 노드의 키 값은 노드 N의 키 값보다 커야함
// 같은 키 값을 갖는 노드는 없음

struct BinNode { // 노드를 표현하는 구조체 
	int data; // 노드의 데이터를 나타냄
	 BinNode *left; // 왼쪽 자식 노드에 대한 포인터
	 BinNode *right; // 오른쪽 자식 노드에 대한 포인터
};

static BinNode *AllocBinNode(void) {
	return new BinNode; //(BinNode*)calloc(1, sizeof(BinNode)); // 동적할당으로 Node 생성
}

static void SetBinNode(BinNode *n, const int *x, const BinNode *left = NULL, const BinNode *right = NULL) { // 노드를 설정하는 함수
	n->data = *x; // 데이터
	n->left = (BinNode*)left; // 왼쪽 자식노드에 대한 포인터
	n->right = (BinNode*)right; // 오른쪽 자식 노드에 대한 포인터
}

bool compare(const int *x, const int *y) { // 비교함수
	return x == y ? true : false; // 참이면 0반환 아니면 y반환
}

BinNode *Search(BinNode *p, const int *key) { // 이진검색트리에서 노드를 검색하는 함수
	if (p == NULL) { // p가 NULL이면 더이상 노드가 없다는 뜻이니 
		return NULL; // NULL을 리턴
	}
	else if (compare(&p->data, key)) { // 값이 같으면 true
		return p; // 노드의 주소를 return
	}
	else if (*key < p->data) { // 키 값이 현재 노드 보다 작으면 왼쪽 자식으로 감(왼쪽 서브트리에서 검색)
		Search(p->left, key);
	}
	else if (*key > p->data) { // 키 값이 현재 노드 보다 크면 오른쪽 자식으로 감(오른쪽 서브트리에서 검색)
		Search(p->right, key);
	}
}

BinNode *Add(BinNode *p, const int *data) { // 이진검색트리에 노드를 삽입하는 과점
	if (p == NULL) { // NULL이면 이진검색트리가 비어있다는 뜻
		p = AllocBinNode();
		SetBinNode(p, data, NULL, NULL);
	}
	else if (compare(data, &p->data)) { // 데이터 값이 같으면
		cout << *data << "는 이미 등록되어 있습니다.\n";
	}
	else if (*data < p->data) { // 현재 노드보다 data 값이 작으면
		p->left = Add(p->left, data); // 선택한 노드에 왼쪽 자식 노드를 대입, Add함수에 왼쪽 자식노드를 전달하면서 재귀호출, 왼쪽 서브트리를 검색 
	}
	else if (*data > p->data) { // 현재 노드보다 data 값이 크면
		p->right = Add(p->right, data); // // 선택한 노드에 오른쪽 자식 노드를 대입, Add함수에 오른쪽 자식노드를 전달하면서 재귀호출, 오른쪽 서브트리를 검색
	}
	return p; // p를 반환
}

int Remove(BinNode **root, const int *key) { // 노드 제거 함수
	BinNode *change, *remove_node;
	BinNode **Left_SubTree, **p = root; // RmLeft = 삭제할 노드의 왼쪽 서브트리에서 가장 큰값을 찾기 위한 변수, p == root의 주소
	                              // 2중 포인터를 사용한 이유는 루트만 있는 이진검색트리에서 루트 노드를 삭제할 경우 루트 포인터를 NULL로 해줘야한다
	while (true) { // 삭제할 노드를 찾는 과정 Search 함수와 유사함(반복)
		cout << *key << '\n';
		if (*p == NULL) {
			cout << *key << "는 등록되어 있지 않습니다.\n";
			return -1;
		}
		else if ((*p)->data == *key){ //(compare(&(*p)->data, key)) { // 같으면 종료
			break;
		}
		else if (*key < (*p)->data) {
			p = &((*p)->left); // 왼쪽 서브 트리에서 검색
		}
		else if (*key > (*p)->data) {
			p = &((*p)->right); // 오른쪽 서브 트리에서 검색
		}
	}
	if ((*p)->left == NULL) { // 삭제할 노드의 왼쪽 자식이 없으면
		change = (*p)->right; // 오른쪽 자식의 주소를 next에 넣음
	}
	else {
		Left_SubTree = &((*p)->left); // 삭제할 노드의 왼쪽 자식의 주소를 Left_SubTree 변수에 넣음  
		while ((*Left_SubTree)->right != NULL) { // Left_SubTree노드의 왼쪽 자식이 NULL이 될때까지 탐색 즉 삭제할 노드의 왼쪽 서브트리에서 가장 큰 값을 찾음
			Left_SubTree = &(*Left_SubTree)->right;
		}
		change = *Left_SubTree; // 가장 큰 노드를 삭제된 노드가 있는 자리로 옮기기위해 next에 넣음
		*Left_SubTree = (*Left_SubTree)->left; // 옮길 노드의 왼쪽 자식 노드를 옮길 노드의 주소로 바꿔줌
		change->left = (*p)->left; // 삭제할 노드의 왼쪽 자식의 주소를 옮길 노드의 왼쪽 자식 주소로 바꿔줌
		change->right = (*p)->right; // 삭제할 노드의 오른쪽 자식의 주소를 옮길 노드의 오른쪽 자식 주소로 바꿔줌
	}
	remove_node = *p; // 삭제할 노드의 주소를 remove_node에 넣음
	*p = change; // 옮길 노드를 삭제할 노드의 주소로로 바꿔줌
	delete remove_node; // reomove_node의 메모리를 해제해줌

	return 0;
}

void PrintTree(const BinNode *p) { // Tree를 출력하는 함수
	if (p != NULL) {
		PrintTree(p->left); // 오름차순으로 출력하기 위해 중위 순회 방법으로 트리를 탐색
		cout << "노드에 저장되어 있는 값은 : " << p->data << '\n';
		PrintTree(p->right);
	}
}

void FreeTree(BinNode *p) { // 모든 노드를 삭제
	if (p != NULL) {
		FreeTree(p->left); // 후위 순회 방법으로 트리를 탐색하고 삭제함
		FreeTree(p->right);
		delete p; // 메모리 해제
	}
}

int main() {
	BinNode *root = NULL;
	string cmd;
	do {
		cout << "ADD, REMOVE, SEARCH, PRINT, TERMINATE\n";
		cin >> cmd;
		if (cmd == "ADD") {
			cout << "입력 : ";
			int n; cin >> n;
			root = Add(root, &n);
		}
		else if (cmd == "REMOVE") {
			cout << "입력 : ";
			int n; cin >> n;
			Remove(&root, &n);
		}
		else if (cmd == "SEARCH") {
			cout << "입력 : ";
			int n; cin >> n;
			BinNode *temp;
			if ((temp = Search(root, &n)) != NULL) {
				cout << "성공! Data는 " << temp->data  << '\n';
			}
			else {
				cout << "실패\n";
			}
		}
		else if(cmd == "PRINT") {
			PrintTree(root);
		}
	} while (cmd.compare("TERMINATE"));
	FreeTree(root);

	return 0;
}

개인적으로 이진검색트리에서 가장 어려운 부분은 노드를 삭제하는 부분인 거 같다.

공부를 하면서 다른 부분은 다 무난하게 이해하고 넘어갈 수 있었는데 노드를 삭제하는 부분을 이해하는데 많은 시간이 걸린 거 같다.

 

 

수정예정

 

 

 

'CS > Data Struct' 카테고리의 다른 글

Binary Search/이진 검색  (0) 2021.07.12
Linear Search/선형 검색  (0) 2021.07.12
Insertion Sort  (0) 2020.10.21
Selection Sort  (0) 2020.10.21
Bubble Sort  (0) 2020.10.20
'CS/Data Struct' Related Articles more
Comments