C# Data Structure++

이진 탐색 트리(Binary Search Tree)

---

이진탐색트리(BST)는 이진 탐색(binary search)과 연결리스트를 결합한 자료구조이다. 이진탐색의 효율적인 탐색 능력을 유지하면서 자료의 입력과 삭제가 가능하도록 고안되어있다. 달리 말하면 이진탐색은 정렬된 자료구조에서 수행이 가능한데, 이진 탐색 트리는 정렬을 깨지 않고 자료의 입력과 삭제가 가능하다는 의미이다.

개념

이진 탐색 트리에서는 2가지 명확한 법칙이 존재한다.

• 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값이 위치한다.
• 노드의 오른쪽 서브트리에는 해당 노드보다 큰 값이 위치한다.

위 사진을 보면 노드 5를 기준으로 5보다 작은 1,2,3,4는 왼쪽 서브트리, 5보다 큰 6,7,8,9는 오른쪽 서브트리에 있는 것을 알 수 있다. 그리고 서브트리 또한 하나의 BST임으로 해당 법칙이 성립해야한다.

탐색

따라서 이러한 법칙이 존재하는 BST에서 이진 탐색을 하기 위해서는 특별한 방식이 필요한데, 이를 중위 순회라고 한다. 중위 순회의 순서는 다음과 같다.

1. 왼쪽 서브 트리를 순회한다.
2. 노드를 반환한다.
3. 오른쪽 서브 트리를 순회한다.

이를 재귀구조로 반복하는 것이 중위 순회이며, 위 그림과 같은 순서로 탐색되는 것을 확인할 수 있다.

삽입

이진 탐색 트리에 새로운 데이터를 추가할 때는 반드시 잎새노드에서 진행한다. 중간에 삽입을 하게 되면 이진 탐색 트리의 법칙이 깨질 수 있기 때문이다.

제거

이진 탐색 트리에서 기존 데이터를 제거할 때는 트리의 법칙을 깨지 않기 위해 삭제하려는 노드의 자식 노드 수를 기준으로 3가지 경우로 나누어 구현해야한다.

1. 자식 노드가 없는 경우

이 경우는 추가 조치 없이 단순히 해당 노드를 제거하면 된다.

2. 자식 노드가 1개인 경우

이 경우에는 해당 노드를 제거하고, 자식 노드와 부모 노드를 서로 연결하면 된다.

3. 자식 노드가 2개인 경우

이 경우는 2가지 방식으로 구현이 가능한데, 삭제 대상 노드 위치에 predecessor을 넣고, 기존 predecessor의 위치를 삭제하는 방식과 삭제 대상 노드 위치에 successor를 넣고, 기존 successor의 위치를 삭제하는 방식이다.

• predecessor : 노드의 왼쪽 서브 트리의 최댓값
• successor : 노드의 오른쪽 서브 트리의 최솟값

우선순위 큐

---

우선순위 큐는 우선순위를 가지고 있는 데이터가 저장되어있는 자료형으로, 데이터를 처리할 때 우선순위가 높은 순으로 처리한다는 특징을 갖는다. 만약 두 원소의 우선순위가 같으면 이는 큐(FIFO)의 순서로 처리된다.

개념

우선순위 큐는 자료형이다. 리스트가 연결리스트나 배열로 구현이 되는 것 처럼 우선순위 큐 또한 힙이나 배열, 연결리스트 등 다양한 방식으로 구현될 수 있는 것이다. 따라서 우선순위 큐는 힙이다 라는 말은 옳지 않다. 다만 힙으로 구현할 경우 삽입과 제거에서 모두 $log\,n$ 을 보장하기에 대부분 힙으로 구현한다.

Heap

우선순위 큐를 힙으로 구현하는 경우 node를 갖는데, 이때 부모 노드와 자식 노드의 관계는 다음과 같다.

• 왼쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 x 2
• 오른쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 x 2 + 1
• 부모 노드의 인덱스 = 자식 노드의 인덱스 / 2

Enqueue

우선순위 큐에는 우선순위를 갖는 데이터가 저장되므로, 삽입시에는 데이터의 우선순위를 비교하는 작업과 함께 올바른 위치에 삽입되어야한다.

public void Enqueue()
{
	index = size;
    
	while(index > 0 && tree[index/2] < tree[index]
	{
		Swap(tree[index/2],tree[index]);
   	 	index /= 2;
	}
}

위의 코드에서 index는 힙 끝을 의미하며, 해당 노드의 위치에서 부모노드보다 클 경우 둘의 위치를 Swap하는 방식으로 Enqueue를 구현한다.

Dequeue

Dequeue는 Heap 정렬의 일부로써 우선순위 큐의 특징 상 가장 높은 우선순위를 가진 데이터를 제거하고 반환한다. 제거 이후 Heap의 마지막 요소를 루트 노드에 배치하고 Heapify를 진행하는 것이다.

public int Dequeue()
{
	int MaxValue = tree[0];
    tree[0] = tree[size];
    size--;
    
    Heapify(tree,0)
    
    return MaxValue;
}

peek

Peek 또한 Queue와 동일하게 우선순위가 가장 높은 데이터를 확인하여 반환한다.

public int Peek()
{
	int MaxValue = tree[0];
    
    return MaxValue;
}

Minimum Spanning Tree(MST)

---

Spanning Tree

스패닝 트리는 그래프 내의 모든 정점을 포함하며, n개의 정점을 n-1개의 간선으로 연결한 그래프를 의미한다. 즉 그래프의 최소 연결 부분 그래프라고 볼 수 있다. 앞서 배운 DFS, BFS에서 parent를 타고 가는 것으로 스패닝 트리를 구현할 수 있으며, 이처럼 하나의 그래프에는 수많은 스패닝 트리가 존재한다.

Minimum Spanning Tree

최소신장트리(MST)는 수많은 Spanning Tree 중에서 간선들의 가중치 합이 최소인 트리를 의미한다. 간선에 가중치가 있는 Weight Graph에서 Weight를 고려해 최소 비용의 Spanning Tree를 선택하는 것이다. 이때 MST를 구현하기 위해 Kruskal MST 알고리즘과 Prim MST 알고리즘이 활용된다.

Kruskal Algorithm

크루스칼 알고리즘은 Greedy Algorithm을 이용하여 weight graph의 모든 정점을 최소 비용으로 연결하는 해답을 도출해내는 알고리즘이다. Greedy algorithm을 사용하기에 순간에는 최적이지만 전체적으로는 최적이라는 보장이 없어 검증을 필요로 하지만, Kruskal Algorithm의 경우 최적의 해답을 도출하는 것이 검증되어있다.

1. 그래프의 간선들을 가중치의 오름차 순으로 정렬
2. 정렬된 간선 리스트에서 순서대로 선택하되, 사이클을 형성하지 않는 간선 선택
3. 해당 간선을 현재 MST 집합에 추가

참고. 사이클 생성 여부 확인 : union-find algorithm

Prim Algorithm

프림 알고리즘은 시작 정점에서부터 출발하여 MST 집합을 단계적으로 확장하여 도출해내는 알고리즘이다.

1. 시작 정점 MST 집합에 포함
2. 기존의 MST 집합에 인접한 정점들 중, 최소 간선으로 연결된 정점 선택 및 집합에 추가
3. 위의 과정을 MST가 n-1개의 간선을 가질때까지 반복

Kruskal vs Prim

크루스칼 알고리즘의 시간 복잡도는 $O(n\,log\,n)$
프림 알고리즘의 시간 복잡도는 $O(n^2)$

• 그래프 내의 적은 숫자의 간선을 갖는 희소 그래프의 경우 크루스칼 알고리즘
• 그래프 내 간선이 많이 존재하는 밀집 그래프의 경우 프림 알고리즘이 적합하다.