[자료구조] Binary Search Tree (BST)

0. 이진 탐색 트리

이진탐색트리란 이진탐색(binary search)과 연결리스트(linked list)를 결합한 자료구조의 일종이다. 이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됐다.

---

 

1. BST 기본 연산별 시간복잡도

연산 평균 시간복잡도 최악 시간복잡도 (Skewed Tree)

탐색 (Search)	O(log N)	O(N)
삽입 (Insert)	O(log N)	O(N)
삭제 (Delete)	O(log N)	O(N)

 

---

 

2. 시간 복잡도 분석

1) 평균적인 경우 (Balanced BST) → O(log N)

트리가 균형 잡힌 경우 (Balanced Tree), 즉 거의 완전 이진 트리라면:

• 트리의 높이(h)는 O(log N)
• 탐색, 삽입, 삭제 연산 모두 최대 log N 번만 비교하면 끝!
• 따라서 O(log N)

완전 이진 트리 높이(h) 공식

h ≈ log₂N → 트리의 깊이가 log N이므로 연산도 O(log N)

plaintext
복사편집
         50
       /    \\
     30      70
    /  \\    /  \\
   20   40 60   80

• 탐색, 삽입, 삭제 연산은 최악의 경우에도 log N 번만 비교하면 끝.
• 즉, O(log N)

---

 

2) 최악의 경우 (Skewed Tree) → O(N)

트리가 한쪽으로 치우친 경우(편향 트리, Skewed Tree):

• 모든 노드가 한쪽(왼쪽 or 오른쪽)으로만 삽입되면 리스트와 동일한 구조가 됨.
• 트리의 높이 = N이므로 연산을 수행할 때 최대 N번 비교해야 함.
• 따라서 O(N)

plaintext
복사편집
50
 \\
  60
   \\
    70
     \\
      80

• 최악의 경우 선형 탐색과 동일 → O(N)

---

 

3. 시간 복잡도를 개선하는 방법

• 균형을 유지하면 O(log N)를 보장할 수 있음.
• AVL 트리, 레드-블랙 트리 같은 균형 이진 탐색 트리를 사용하면 삽입/삭제 시 자동으로 균형을 맞춰서 항상 O(log N)을 유지함.

---

 

4. 정리

트리 상태 탐색(Search) 삽입(Insert) 삭제(Delete)

균형 트리 (Balanced BST)	O(log N)	O(log N)	O(log N)
편향 트리 (Skewed BST)	O(N)	O(N)	O(N)

BST는 높이에 따라 성능이 결정되므로 균형을 유지하는 것이 중요하다.

최악의 경우(한쪽으로 치우친 트리)는 선형 탐색과 같아 O(N)이 된다.

AVL 트리나 레드-블랙 트리를 쓰면 항상 O(log N) 보장 가능.

---

 

5.  CPP로 구현

#include <iostream>

template <typename T>
struct Node
{
	Node(T Data) : Data(Data), Left(nullptr), Right(nullptr) {}

	T Data;
	Node* Left;
	Node* Right;
};

template <typename T>
class BinarySearchTree
{
public:
	BinarySearchTree() : Root(nullptr), Height(0)
	{
	
	}
	
	BinarySearchTree& Insert(T Data)
	{
		Root = Insert(Root, Data);
		return *this;
	}

	BinarySearchTree& Remove(T Data)
	{
		Root = Remove(Root, Data);
		return *this;
	}

	bool Search(T Data)
	{
		return Search(Root, Data);
	}

	void Preorder()
	{
		Preorder(Root);
		std::cout << std::endl;
	}

	void Inorder()
	{
		Inorder(Root);
		std::cout << std::endl;
	}

	void Postorder()
	{
		Postorder(Root);
		std::cout << std::endl;
	}

private:
	Node<T>* Root;
	int Height;

	Node<T>* Insert(Node<T>* InNode, T Data)
	{
		if (InNode == nullptr) return new Node(Data);
		if (Search(InNode, Data)) return InNode;

		if (InNode->Data > Data)
		{
			InNode->Left = Insert(InNode->Left, Data);
		}
		else if (InNode->Data < Data)
		{
			InNode->Right = Insert(InNode->Right, Data);
		}

		return InNode;
	}

	Node<T>* Remove(Node<T>* InNode, T Data)
	{
		if (InNode == nullptr) return InNode;

		if (InNode->Data > Data)
		{
			InNode->Left = Remove(InNode->Left, Data);
		}
		else if (InNode->Data < Data)
		{
			InNode->Right = Remove(InNode->Right, Data);
		}
		else
		{
			if (InNode->Left == nullptr)
			{
				Node<T>* Temp = InNode->Right;
				delete InNode;
				return Temp;
			}
			else if (InNode->Right == nullptr)
			{
				Node<T>* Temp = InNode->Left;
				delete InNode;
				return Temp;
			}

			Node<T>* Temp = SearchCandidateNode(InNode->Right);
			InNode->Data = Temp->Data;
			InNode->Right = Remove(InNode->Right, Temp->Data);
		}

		return InNode;
	}

	Node<T>* SearchCandidateNode(Node<T>* InNode)
	{
		Node<T>* Current = InNode;
		while (Current && Current->Left != nullptr)
		{
			Current = Current->Left;
		}
		return Current;
	}

	bool Search(Node<T>* InNode, T Data)
	{
		if (InNode == nullptr) return false;
		if (InNode->Data == Data) return true;
		return (InNode->Data > Data) ? Search(InNode->Left, Data) : Search(InNode->Right, Data);
	}

	// 전위 순회 ( 부모 -> 왼쪽 자식 -> 오른쪽 자식 )
	void Preorder(Node<T>* InNode)
	{
		if (InNode != nullptr)
		{
			std::cout << InNode->Data << " ";
			Preorder(InNode->Left);
			Preorder(InNode->Right);
		}
	}

	// 중위 순회 ( 왼쪽 자식 -> 부모 -> 오른쪽 자식 )
	void Inorder(Node<T>* InNode)
	{
		if (InNode != nullptr)
		{
			Inorder(InNode->Left);
			std::cout << InNode->Data << " ";
			Inorder(InNode->Right);
		}
	}

	// 후위 순회 ( 왼쪽 자식 -> 오른쪽 자식 - > 부모 )
	void Postorder(Node<T>* InNode)
	{
		if (InNode != nullptr)
		{
			Postorder(InNode->Left);
			Postorder(InNode->Right);
			std::cout << InNode->Data << " ";
		}
	}
};

template <typename T>
using BST = BinarySearchTree<T>;

int main()
{
	BST<int> Tree;
	Tree.Insert(50);
	Tree.Insert(30);
	Tree.Insert(70);
	Tree.Insert(20);
	Tree.Insert(40);
	Tree.Insert(60);
	Tree.Insert(80);

	std::cout << "이진 탐색 트리 전위 순회 결과 : ";
	Tree.Preorder(); // 50 30 20 40 70 60 80

	std::cout << "이진 탐색 트리 중위 순회 결과 : ";
	Tree.Inorder(); // 20 30 40 50 60 70 80

	std::cout << "이진 탐색 트리 후위 순회 결과 : ";
	Tree.Postorder(); // 20 40 30 60 80 70 50

	std::cout << "검색 : 40 -> " << (Tree.Search(40) ? "발견" : "발견 못함") << std::endl;
	std::cout << "검색 : 90 -> " << (Tree.Search(90) ? "발견" : "발견 못함") << std::endl;
	Tree.Remove(70);

	std::cout << "이진 탐색 트리 70 삭제 후 전위 순회 결과 : ";
	Tree.Preorder(); // 5

	return 0;
}