트리 (Tree)
- 트리는 사이클을 갖지 않는 하나의 연결 그래프로, 부모-자식의 계층적 관계를 표현하는 자료구조이다.
- 하나의 루트 노드는 0개 이상의 자식 노드를 가지고, 또 그 자식 노드 또한 0개 이상의 자식 노드를 갖는다.
- 즉, 트리는 재귀로 정의된 자기 참조 자료구조로 서브트리로 구성된다.
- 트리는 특수한 형태의 그래프의 일종으로 그래프에 포함되지만, 그래프와 달리 두 노드 간의 경로는 유일하다.
- 그래프와 트리 모두 비선형 자료구조로 그래프는 단방향과 양방향 모두 표현 가능하지만 트리는 부모 노드에서 자식 노드로의 단방향만 표현 가능하다.
이진 트리
- 각 노드가 최대 두 개의 자식 노드를 갖는 트리로, 대표적으로 다음과 같은 3가지 유형이 있다.
정 이진 트리 (Full Binary Tree)
- 모든 노드의 자식이 없거나 정확히 두 개 있는 이진트리
- 자식이 하나만 있는 노드가 존재해서는 안된다.
완전 이진 트리 (Complete Binary Tree)
- 트리의 모든 높이에서 노드가 꽉 차있는 이진트리
- 마지막 단계는 꽉 차있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 한다.
포화 이진 트리 (Perfect Binary Tree)
- 정 이진 트리이면서 완전 이진 트리인 경우로, 모든 노드가 2개의 자식 노드를 가지며 모든 리프 노드가 동일한 깊이 또는 레벨을 갖는다.
- 노드의 개수는 정확히 2 * (k - 1) 개
이진 탐색 트리 (BST)
- 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값을 지진 노드들로 이루어져있고 노드의 오른쪽 서브트리에는 그 노드의 값과 같거나 큰 값들을 지닌 노드들로 이루어져 있는 이진 트리를 말한다.
- 즉, 왼쪽과 오른쪽의 값들이 각각 값의 크기에 따라 정렬되어 있는 이진 트리로, 탐색 시 시간 복잡도가 O(logN)이다.
- 그러나 저장 순서에 따라 계속 한쪽으로만 노드가 추가되는 편향 트리의 경우(최악의 경우), 탐색 시 시간 복잡도는 O(N)이 소요된다.
- 따라서 이를 해결하기 위해 균형을 잡기 위한 트리 구조의 재조정 기법이 등장했고, 이러한 Rebalancing 기법을 구현한 트리를 자가 균형 이진 탐색 트리라고 한다.
자가 균형 이진 탐색 트리
- 자가 균형 이진 탐색 트리는 삽입, 삭제 시 자동으로 높이를 작게 유지하는 노드 기반의 이진 탐색 트리이다.
- 트리에서 노드의 삽입과 삭제가 이루어질 때 자동으로 모든 하위 트리의 높이 차를 1이하로 만든다.
- 불균형과 균형의 성능 차이는 크기 때문에 트리의 균형, 즉 높이의 균형을 맞추는 작업은 매우 중요하다.
- 이와 같이 높이 균형을 맞춰주는 자가 균형 이진 탐색 트리의 대표적인 형태로는 AVL 트리와 레드-블랙 트리 등이 있으며, 특히 레드-블랙 트리는 높은 효율성으로 인해 빈번하게 쓰이는 트리 형태이다.
- 예를 들어, 자바의 해시맵에서 효율적인 저장 구조를 위해 해시 테이블의 개별 체이닝 시 연결리스트와 함께 레드-블랙 트리를 병행해 저장하는 구조로 구현되어 있다.
AVL 트리
- 자가 균형 이진 탐색 트리의 한종류로, 각 노드에 현재 노드를 루트로 했을 때의 서브트리의 높이 정보를 저장한다.
- 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이가 1이상 차이나지 않게 만들어 트리의 균형을 맞춘다.
레드-블랙 트리
- 자가 균형 이진 탐색 트리의 한 종류로, 노드는 번갈아가며 빨간색과 검은색으로 표시되며 아래 조건을 만족한다.
- 어떤 노드에서 단말 노드까지의 모든 경로에 있는 검은색 노드의 개수는 같아야 한다.
- 루트 노드와 리프 노드는 검은색이고, 모든 빨간 노드는 두 개의 검은색 자식 노드를 갖는다.
- 즉, 두 개의 빨간색 노드가 경로 상에서 인접할 수 없으므로, 빨간색 노드는 경로 상 노드의 절반보다 많을 수 없다.
- 따라서 빨간색 노드가 최소인 경로와 빨간색 노드가 최대인 경로의 차이가 최악의 경우에도 2배보다 크지 않기 때문에 검색과 삽입 연산이 O(logN) 안에 가능하다.
최소 스패닝 트리 (MST)
- 가중치가 있는 연결된 무방향 그래프에서 스패닝 트리는 트리 내의 모든 정점을 포함하는 사이클이 없는 트리를 말한다.
- 최소 스패닝 트리는 이러한 스패닝 트리 중에서 그 가중치의 합이 최소가 되는 경우를 말한다.
크루스칼 알고리즘
- 최소 스패닝 트리를 찾는 알고리즘 중 하나로, 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬한 뒤 사이클을 발생시키지 않는 간선만 스패닝 트리에 추가한다. (사이클을 확인할 때 유니온 파인드 활용)
- 스패닝 트리가 완성되면 모든 노드들이 연결된 상태로 종료되고, 그리디에 의해 그때의 비용이 최소 비용이 된다.
- 간선의 비용을 기존으로 정렬하는 데 O(E*logE), 사이클 생성 여부를 검사하는 데 O((E+V)*logV)의 시간이 걸리므로, 전체 시간 복잡도는 O(E*logE)이다.
# 원소가 속한 집합의 루트 노드 찾기
# 경로 압축 기법: 파인드 함수를 재귀적으로 호출한 뒤에 부모 테이블값을 갱신
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
# 두 원소가 속한 집합 합치기
def union(a, b):
a = find(a)
b = find(b)
# 더 작은 쪽을 루트로 만든다.
if a < b:
parent[b] = a
else:
parent[a] = b
v, e = map(int, input().split())
# 부모를 자기 자신으로 초기화
parent = [i for i in range(v + 1)]
edges = []
for _ in range(e):
a, b, cost = map(int, input().split())
edges.append((cost, a, b))
# 비용 순으로 정렬
edges.sort()
# 최종 비용
res = 0
for edge in edges:
cost, a, b = edge
# 사이클이 발생하지 않는 경우에만 집합에 포함
if find(a) != find(b):
union(a, b)
res += cost
print(res)
프림 알고리즘
- 최소 스패닝 트리를 찾는 알고리즘 중 하나로, 시작 정점에서부터 출발하여 스패닝 트리를 단계적으로 확장해 나가는 방법이다.
- 시작 단계에서는 시작 정점만 최소 스패닝 트리에 포함하고, 앞 단계에서 만들어진 최소 스패닝 트리에 인접한 정점들 중에서 최소 비용을 가지는 간선을 선택하여 트리를 확장한다.
- 이러한 과정을 트리가 V-1개의 간선을 가질 때까지 반복한다.
- 전체 시간 복잡도는 O(E*logV)
(이진) 트리 순회
중위 순회 (In-Order)
- 왼쪽 서브트리, 현재 노드, 오른쪽 서브트리 순서로 노드를 방문하고 출력하는 방법
- 이진 탐색 트리를 이 방식으로 순회한다면 오름차순으로 방문하게 된다.
# 중위 순회
def inorder(node):
if node.left != ".":
inorder(tree[node.left])
print(node.data, end="")
if node.right != ".":
inorder(tree[node.right])
전위 순회 (Pre-Order)
- 자식 노드보다 현재 노드를 먼저 방문하는 방법
- 전위 순회에서 가장 먼저 방문하는 노드는 언제나 루트 노드이다.
# 전위 순회
def preorder(node):
print(node.data, end="")
if node.left != ".":
preorder(tree[node.left])
if node.right != ".":
preorder(tree[node.right])
후위 순회 (Post-Order)
- 모든 자식 노드들을 먼저 방문한 뒤 마지막에 현재 노드를 방문하는 방법
- 후외 순회에서 가장 마지막에 방문하는 노드는 언제나 루트 노드이다.
# 후위 순회
def postorder(node):
if node.left != ".":
postorder(tree[node.left])
if node.right != ".":
postorder(tree[node.right])
print(node.data, end="")
'Python > Algorithm' 카테고리의 다른 글
트라이 (0) | 2022.02.27 |
---|---|
힙과 우선순위 큐 (0) | 2022.02.27 |
최단 경로 알고리즘 (0) | 2022.02.25 |
그래프와 그래프 탐색 (0) | 2022.02.25 |
해시 테이블 (0) | 2022.02.24 |