22.1 도입

검색트리는 연결 리스트나 큐처럼 자료들을 담는 컨테이너지만, 자료들을 일정한 순서에 따라 정렬한 상태로 저장한다.

리스트나 큐는 주어진 순서에 따라 자료들을 배치한다.

원소의 추가와 삭제, 특정 원소의 존재 여부 확인 등의 다양한 연산을 빠르게 수행한다.

이진 검색 트리와 그 변종들이 검색 트리 중 가장 흔하게 사용됩니다.

이진 검색 트리는 라이브러리에서 지원 (map)

트립

이진 검색 트리의 변종, 직접 구현해야함

22.2 이진 검색 트리의 정의와 조작

정의

이진 탐색(binary search)에서 아이디어를 가져와서 만든 트리입니다. 즉 N개의 원소 중에서 원하는 값을 찾는데 O(lgN) 시간이 걸립니다.

왼쪽에는 해당 노드의 원소보다 작은 원소를 가진 노드들이, 오른쪽 서브트리에는 보다 큰 원소를 가진 노드들이 들어갑니다.

순회

이진 트리를 중위 순회하면 크기 순서로 정렬된 원소의 목록을 얻을 수 있습니다.

중위 순회는 왼쪽 서브 트리 → 루트 → 오른쪽 서브트리 순으로 순회하는 것입니다. 이 순서가 정렬된 결과와 같으니 정렬된 원소의 목록을 얻을 수 있는 것입니다.

자료의 검색

이진 탐색과 비슷한 속도로 자료를 찾을 수 있습니다.

조작

집합에 원소를 추가하거나 삭제하는 조작 연산에 있어서 이득이 있습니다.

이것이 정렬된 배열보다 나은 점 입니다.

이진 검색 트리의 삽입 연산은 쉽습니다. 현재 삽입하고자하는 공간이 null이면 삽입하면 됩니다.

삭제 연산은 조금 어렵습니다.

노드 t를 삭제한다고 가정했을때 노드 t의 왼쪽을 A 서브트리 오른쪽을 B 서브트리라고 합시다.

A의 최대 원소는 B의 최소 원소보다 작습니다.

A를 루트로 하는 합치기 연산을 구현하면, A의 왼쪽은 원래 A의 왼쪽입니다. (위 문장에 의해)

A의 오른쪽은 B와 A의 오른쪽을 합치기 연산한것이 됩니다.

//이준수 구현 / 피드백 환영
#include <iostream>

using namespace std;

class binarytree {
private:
	binarytree* left;
	binarytree* right;
	int element;
public:
	//삽입 연산
	void insert(int element) {
		if (!this->element) {
			this->element = element;
			return;
		}
		//루트의 원소가 삽입 원소보다 큰 경우 -> 왼쪽
		if (this->element > element) {
			if (this->left == NULL)
				this->left = new binarytree();
			left->insert(element);
			return;
		}
		//루트의 원소가 삽입 원소보다 작은 경우 -> 오른쪽
		else {
			if (this->right == NULL)
				this->right = new binarytree();
			right->insert(element);
			return;
		}
	}

	//합치기 연산 A의 최대 원소가 B의 최소원소보다 작다는것을 가정한다.
	//즉, 소모되는건 A뿐이다.
	binarytree* merge(binarytree* A, binarytree* B) {
		if (A == NULL)
			return B;

		binarytree* res = new binarytree();
		res->insert(A->element);
		res->left = A->left;
		res->right = merge(A->right, B);
		return res;
	}

	//찾는 연산
	bool find_element(binarytree* root, int element) {
		if (root->element == element)
			return true;
		//찾고자하는게 더 작다.
		if (root->left != NULL && root->element > element)
			return find_element(root->left, element);
		//찾고자하는게 더 크다.
		if (root->right != NULL && root->element < element)
			return find_element(root->right, element);
		return false;
	}

	//삭제후 병합된 트리를 반환.
	binarytree* del(binarytree* root, int element) {
		if (root->element == element)
			return merge(root->left, root->right);
		//찾는 값이 왼쪽에 있는 경우
		if (root->left!=NULL&&root->element>element)
			root->left = del(root->left, element);
		//찾는 값이 오른쪽에 있는 경우
		else
			root->right = del(root->right, element);
		
		return root;
	}

	//출력 연산
	void print(binarytree* root) {
		if (!root)
			return;
		print(root->left);
		cout << root->element << " ";
		print(root->right);
	}
};

int main() {
	cout << "이진 트리를 생성합니다......\n";
	binarytree* bnt = new binarytree();
	
	int number;
	while (1) {
		cout << "1. 삽입연산 2. 찾기연산 3. 삭제연산 4. 전체 출력  \n";
		int cmd;
		cin >> cmd;
		switch (cmd)
		{
		case 4:
			bnt->print(bnt);
			break;

		case 1:
			cout << "수를 입력하세요 : ";
			cin >> number;
			bnt->insert(number);
			break;
		case 2:
			cout << "수를 입력하세요 : ";
			cin >> number;
			if (bnt->find_element(bnt, number))
				cout << "값이 존재합니다.";
			else
				cout << "값이 없네요.";
			break;
		case 3:
			cout << "수를 입력하세요 : ";
			cin >> number;
			if (bnt->find_element(bnt, number)) {
				bnt = bnt->del(bnt, number);
				cout << "삭제완료";
			}
			else
				cout << "값이 없네요";
			break;
		default:
			return 0;
		}
		cout << "\n";
	}
}