트리와 이진 탐색 트리 (Binary Search Tree) 정리
트리와 이진 탐색 트리 (Binary Search Tree)
1. 트리의 기본 개념
트리(Tree)는 노드(Node)들이 계층적으로 연결된 자료구조이다. 최상위 노드에서 시작하여 여러 자식 노드로 연결되는 구조를 가진다.
주요 용어
- Node: 데이터를 저장하는 기본 단위이다.
- Root: 트리의 가장 위에 있는 최상위 노드이다.
- Parent: 다른 노드를 자식으로 가지는 상위 노드이다.
- Child: 부모 노드에 연결된 하위 노드이다.
- Leaf: 자식 노드가 없는 노드이다.
- Edge: 노드와 노드를 연결하는 선이다.
- Subtree: 특정 노드를 루트로 하는 하위 트리이다.
- Depth: 루트에서 특정 노드까지 도달하는 데 필요한 간선의 수이다. 루트의 Depth는 0이다.
- Height: 특정 노드에서 가장 깊은 리프 노드까지의 높이이다. 이 자료에서는 리프 노드의 Height를 1로 계산한다.
2. 이진 트리 (Binary Tree)
이진 트리는 하나의 노드가 최대 2개의 자식 노드를 가질 수 있는 트리이다.
자식 노드는 각각 왼쪽(Left)과 오른쪽(Right)으로 구분한다.
3. 이진 탐색 트리 (Binary Search Tree)
이진 탐색 트리는 이진 트리의 구조에 정렬 규칙을 추가한 자료구조이다.
핵심 규칙
- 왼쪽 서브트리의 모든 키는 현재 노드의 키보다 작다.
- 오른쪽 서브트리의 모든 키는 현재 노드의 키보다 크다.
- 이 규칙은 모든 하위 노드에서도 동일하게 적용된다.
이러한 규칙을 통해 데이터를 효율적으로 검색할 수 있다.
4. 주요 기능
검색 (Search)
루트 노드부터 시작하여 찾으려는 키와 현재 노드의 키를 비교한다.
- 키가 같으면 검색을 종료한다.
- 찾으려는 키가 작으면 왼쪽으로 이동한다.
- 찾으려는 키가 크면 오른쪽으로 이동한다.
균형 잡힌 트리에서는 비교할 때마다 검색 범위가 절반씩 줄어들 수 있다.
삽입 (Insert)
새로운 데이터를 삽입할 때는 루트부터 시작하여 키를 비교한다.
BST 규칙에 따라 왼쪽 또는 오른쪽으로 이동하다가 비어 있는 위치를 찾으면 새로운 노드를 추가한다.
삭제 (Remove)
노드를 삭제할 때는 자식 노드의 개수에 따라 처리 방법이 달라진다.
- 자식이 없는 경우
- 해당 노드를 바로 삭제한다.
- 자식이 하나인 경우
- 삭제할 노드를 자식 노드로 대체한다.
- 자식이 두 개인 경우
- 오른쪽 서브트리에서 가장 작은 키를 가진 노드를 찾는다.
- 해당 노드의 키와 값을 삭제할 노드에 복사한다.
- 기존 위치에 있던 노드를 삭제한다.
두 자식이 있는 노드를 삭제할 때 사용하는 대체 노드를 Inorder Successor라고 한다.
왼쪽 서브트리에서 가장 큰 키를 가진 노드인 Inorder Predecessor를 사용할 수도 있다.
5. 트리 순회 (Tree Traversal)
트리 순회는 트리에 저장된 모든 노드를 특정 순서로 방문하는 방법이다.
InOrder (중위 순회)
왼쪽 → 현재 노드 → 오른쪽 순서로 방문한다.
BST에서 중위 순회를 사용하면 키가 오름차순으로 출력된다.
PreOrder (전위 순회)
현재 노드 → 왼쪽 → 오른쪽 순서로 방문한다.
트리의 구조를 저장하거나 직렬화할 때 활용할 수 있다.
PostOrder (후위 순회)
왼쪽 → 오른쪽 → 현재 노드 순서로 방문한다.
자식 노드를 먼저 처리해야 하는 작업이나 트리 삭제 등에 활용할 수 있다.
LevelOrder (레벨 순회)
루트부터 시작하여 같은 깊이에 있는 노드를 순서대로 방문한다.
일반적으로 Queue를 사용하여 구현한다.
6. 시간 복잡도
BST의 시간 복잡도는 트리의 균형 상태에 따라 달라진다.
| 기능 | 평균 | 최악 |
|---|---|---|
| 검색 (Search) | O(log n) | O(n) |
| 삽입 (Insert) | O(log n) | O(n) |
| 삭제 (Remove) | O(log n) | O(n) |
| 순회 (Traversal) | O(n) | O(n) |
데이터가 균형 있게 배치되면 검색 범위를 빠르게 줄일 수 있다.
반대로 정렬된 데이터를 순서대로 삽입하면 한쪽으로 치우친 트리가 만들어질 수 있다. 이 경우 트리가 연결 리스트와 비슷한 구조가 되어 검색 성능이 O(n)까지 떨어진다.
이러한 문제를 해결하기 위해 AVL 트리와 Red-Black 트리 같은 균형 이진 탐색 트리를 사용한다.
7. C# 구현 구조
BinarySearchTree<TKey, TValue>
이진 탐색 트리를 구현하는 클래스이다.
IDictionary<TKey, TValue>인터페이스를 구현한다.where TKey : IComparable<TKey>제약 조건을 사용한다.root를 통해 트리의 시작 노드를 관리한다.Add,Remove,TryGetValue등의 기능을 제공한다.ContainsKey, 인덱서,Count등을 제공한다.- 네 가지 트리 순회 기능을 제공한다.
IDictionary<TKey, TValue>를 구현하면 Dictionary처럼 키와 값을 관리할 수 있다.
IComparable<TKey>는 키를 비교하기 위해 사용한다. 이를 통해 CompareTo()로 두 키의 크기를 비교할 수 있다.
TreeNode<TKey, TValue>
트리의 각 노드를 나타내는 클래스이다.
Key: 노드의 키이다.Value: 노드에 저장된 값이다.Height: 노드의 높이이다.Left: 왼쪽 자식 노드이다.Right: 오른쪽 자식 노드이다.
노드 생성 시 Height는 1로 초기화한다.
virtual 키워드
virtual은 상속받은 클래스에서 메서드를 재정의할 수 있도록 허용한다.
기본 BST를 상속받아 AVL 트리처럼 균형을 유지하는 트리를 구현할 때 활용할 수 있다.
중복 키 처리
Add(key, value): 이미 존재하는 키를 추가하면ArgumentException이 발생한다.tree[key] = value: 이미 존재하는 키라면 기존 값을 갱신한다.
8. 전체 구조 정리
이진 탐색 트리는 노드 간의 연결을 이용하여 데이터를 저장하고 검색하는 자료구조이다.
- Node가 키와 값을 저장한다.
- Left와 Right가 자식 노드를 연결한다.
- BST 규칙이 데이터의 정렬 상태를 유지한다.
- Search, Insert, Remove가 데이터 관리 기능을 담당한다.
- Traversal이 트리에 저장된 데이터를 순서대로 방문한다.
- Height는 트리의 균형 상태를 파악하는 데 활용할 수 있다.
트리의 구조와 정렬 규칙을 이해하면 일반 BST뿐 아니라 AVL 트리와 Red-Black 트리 같은 자료구조로 확장할 수 있다.
