이진 탐색 트리

🔍 이진 탐색 트리란?

이진 탐색 트리 (BST) 는 이진 트리(Binary Tree)의 한 종류로, 탐색을 효율적으로 수행하기 위한 규칙을 가진 트리입니다.

✅ BST의 규칙

• 각 노드는 최대 2개의 자식 노드를 가진다.
• 왼쪽 자식 노드는 부모보다 작은 값을 가진다.
• 오른쪽 자식 노드는 부모보다 큰 값을 가진다.

이 규칙 덕분에, 트리에서 탐색·삽입·삭제 연산을 평균 O(log N) 시간 내에 수행할 수 있습니다.

---

⚙️ 핵심 개념 정리

용어	설명
루트(Root)	트리의 시작 노드
리프(Leaf)	자식 노드가 없는 끝 노드
서브트리(Subtree)	특정 노드를 루트로 가지는 트리
차수(Degree)	노드가 가진 자식의 수
높이(Height)	루트에서 리프까지의 최대 깊이

---

🧱 구조 정의: Node

struct Node
{
	Node* parent = nullptr;
	Node* left = nullptr;
	Node* right = nullptr;
	int   key = {};
};

📌 각 멤버 설명

• parent: 부모 노드를 가리킵니다.
• left: 왼쪽 자식 노드를 가리킵니다.
• right: 오른쪽 자식 노드를 가리킵니다.
• key: 이 노드에 저장된 값입니다.

이 구조는 BST가 재귀적으로 구성된다는 점을 그대로 반영합니다.

---

🏗️ 클래스 정의: BinarySearchTree

주요 기능

class BinarySearchTree
{
public:
	void  Print();                  // 트리를 콘솔에 시각적으로 출력
	void  Print_Inorder();          // 중위 순회
	Node* Search(Node* node, int key);   // 재귀 탐색
	Node* Search2(Node* node, int key);  // 반복 탐색
	Node* Min(Node* node);         // 최소값
	Node* Max(Node* node);         // 최대값
	Node* Next(Node* node);        // 후계 노드
	void  Insert(int key);         // 삽입
	void  Delete(int key);         // 삭제 by key
	void  Delete(Node* node);      // 삭제 by node
	void  Replace(Node* u, Node* v); // 노드 교체

private:
	Node* _root = nullptr;
};

---

🔍 탐색 함수

📌 재귀 탐색 (Search)

Node* BinarySearchTree::Search(Node* node, int key)
{
	if (node == nullptr || key == node->key)
		return node;
	if (key < node->key)
		return Search(node->left, key);
	else
		return Search(node->right, key);
}

• 키 값과 현재 노드를 비교해 왼쪽 또는 오른쪽으로 이동하며 재귀 호출합니다.

---

📌 반복 탐색 (Search2)

Node* BinarySearchTree::Search2(Node* node, int key)
{
	while (node && key != node->key)
	{
		if (key < node->key)
			node = node->left;
		else
			node = node->right;
	}
	return node;
}

• 재귀 대신 while 문을 사용하여 탐색합니다.
• 스택 오버플로우를 방지할 수 있어 큰 트리에서 유리합니다.

---

🧮 삽입 함수

void BinarySearchTree::Insert(int key)
{
	Node* newNode = new Node();
	newNode->key = key;

	if (_root == nullptr)
	{
		_root = newNode;
		return;
	}

	Node* node = _root;
	Node* parent = nullptr;

	while (node)
	{
		parent = node;
		node = (key < node->key) ? node->left : node->right;
	}

	newNode->parent = parent;
	if (key < parent->key)
		parent->left = newNode;
	else
		parent->right = newNode;
}

✅ 핵심 로직

• 루트부터 시작해 크기를 비교하며 적절한 위치에 새 노드를 삽입
• 삽입 시 부모 노드와의 연결도 세팅

---

🗑️ 삭제 함수

삭제 by key

void BinarySearchTree::Delete(int key)
{
	Node* deleteNode = Search(_root, key);
	Delete(deleteNode);
}

삭제 by node

void BinarySearchTree::Delete(Node* node)
{
	if (node == nullptr) return;

	if (node->left == nullptr)
		Replace(node, node->right);
	else if (node->right == nullptr)
		Replace(node, node->left);
	else
	{
		Node* next = Next(node);
		node->key = next->key;
		Delete(next);
	}
}

노드 교체 (Replace)

void BinarySearchTree::Replace(Node* u, Node* v)
{
	if (u->parent == nullptr)
		_root = v;
	else if (u == u->parent->left)
		u->parent->left = v;
	else
		u->parent->right = v;

	if (v)
		v->parent = u->parent;

	delete u;
}

🧠 핵심 개념 정리

상황	처리 방식
자식 없음	바로 삭제
자식 하나	자식과 부모 연결만 변경
자식 둘	후계 노드(Next) 찾아 값 복사 후 후계 노드 삭제

---

🌱 후계 노드 찾기 (Next)

Node* BinarySearchTree::Next(Node* node)
{
	if (node->right)
		return Min(node->right);

	Node* parent = node->parent;
	while (parent && node == parent->right)
	{
		node = parent;
		parent = parent->parent;
	}
	return parent;
}

오른쪽 서브트리의 가장 작은 노드 또는 조상 중 자신보다 큰 첫 노드를 반환

---

📈 최소 / 최대값 찾기

Node* BinarySearchTree::Min(Node* node)
{
	while (node->left)
		node = node->left;
	return node;
}

Node* BinarySearchTree::Max(Node* node)
{
	while (node->right)
		node = node->right;
	return node;
}

가장 왼쪽/오른쪽까지 내려가며 최솟값/최댓값을 찾습니다.

---

🖨️ 트리 출력 및 순회

트리 구조 출력

void BinarySearchTree::Print(Node* node, int x, int y)
{
	if (node == nullptr) return;

	SetCursorPosition(x, y);
	cout << node->key;

	Print(node->left, x - (5 / (y + 1)), y + 1);
	Print(node->right, x + (5 / (y + 1)), y + 1);
}

중위 순회 (Inorder)

void BinarySearchTree::Print_Inorder(Node* node)
{
	if (node == nullptr) return;
	Print_Inorder(node->left);
	cout << node->key << " ";
	Print_Inorder(node->right);
}

중위 순회 결과는 항상 정렬된 순서로 출력됩니다.

---

🔄 트리 순회 방식 정리

순회 방식	순서	설명
전위(Preorder)	[중] → 왼 → 오	루트 먼저
중위(Inorder)	왼 → [중] → 오	정렬 순서
후위(Postorder)	왼 → 오 → [중]	자식 먼저

---

🚀 BST의 장점과 단점

✅ 장점

• 평균 시간 복잡도: O(log N)
• 정렬된 데이터 저장 및 검색에 적합

⚠️ 단점

• 불균형 트리가 되면 시간 복잡도가 O(N)으로 하락
• 해결책: AVL 트리, Red-Black 트리 등 균형 이진 탐색 트리 사용

---