C++ 이진탐색트리

---

<이진 탐색 트리>

이진 탐색 트리는 정렬된 배열에 삽입, 삭제, 탐색시 시간이 오래걸리는 것을 보완하기 위해 만든 구조이다.

---

<이진 탐색 트리 조건>

1. 각 노드는 유일한 키를 가지고 있다
2. 왼쪽 서브트리에 있는 키들은 모두 루트 노드의 키보다 작다
3. 오른쪽 서브트리에 있는 키들은 모두 루트노드의 키보다 크다.
4. 왼쪽 서브트리와 오른쪽 서브트리도 이진탐색트리다.

---

<이진 탐색 트리 과정>

추가

위 조건을 보면 알 수 있지만, 위 사진처럼 처음 들어오는 값을 루트노드로 두고,

데이터가 들어올때마다, 데이터가 현재 노드보다 크면 오른쪽, 작으면 왼쪽으로 내려가면서 리프노드가 될 때까지 계속 내려간다.

 

탐색

추가와 비슷하게 탐색을 할때에는, 루트노드에서 시작하여, 찾을 데이터가 현재 위치의 노드보다 크면 오른쪽으로, 작으면 왼쪽으로 내려가면서 탐색을 한다.

 

삭제(단노드)

삭제를 할때에는 3가지 경우가 있는데, 먼저 단노드인 경우, 위 사진처럼 그냥 삭제하면 된다.

삭제(자식이 1개인 경우)

만약 자식이 한개가 있다면, 그자리를 자식이 대체한다.

삭제(자식이 2개 이상인 경우)

자식이 2개 이상인 경우 오른쪽 자식의 맨 왼쪽(오른쪽 자식 중 제일 작은 값) 또는 왼쪽 자식의 맨 오른쪽(왼쪽 자식 중 제일 큰 값)으로 대체한다.

 

---

<이진 탐색 트리 순회>

이진 탐색 트리는 3가지 출력 방식이 있다.

전위 순회

첫 번째로 전위 순회는 루트노드를 시작으로 부모 노드 -> 왼쪽 노드 -> 오른쪽 노드 순서로 순회한다.

 

중위 순회

->

두 번째로 중위 순회는 맨 왼쪽 노드를 시작으로 왼쪽 노드 -> 부모 노드 -> 오른쪽 노드 순서로 순회한다.

 

후위 순회

세 번째로 후위 순회는 맨 왼쪽 노드를 시작으로 왼쪽 노드 -> 오른쪽 노드 -> 부모 노드 순서로 순회한다.

 

---

<이진 탐색 트리 구현>

struct Tree
{
	Tree* left;
	Tree* right;
	int val = 0;
};
Tree mainTree;

void SetTree(int num,Tree& tree)
{
	if (tree.val == 0)
		tree.val = num;
	else
	{
		if (num < tree.val)
		{
			if (tree.left == NULL)
				tree.left = new Tree();
			SetTree(num, *tree.left);
		}
		else
		{
			if (tree.right == NULL)
				tree.right = new Tree();
			SetTree(num, *tree.right);
		}
	}
}

위 코드는 추가 기능만 있으며 비슷한 로직으로 삭제, 탐색을 만들면 된다.

---