1. 트리(Tree)
트리(Tree)는 값을 가진 노드(Node)와 노드들을 연결해주는 간선(Edge)으로 이루어진 계층적 자료구조이다. 사이클을 이루지 않으며 계층 구조를 나타낸다는 점이 그래프와의 가장 큰 차이점이다. 자식 노드는 0개 이상의 자식 노드를 가지며 트리 자료구조는 양방향 연결 리스트를 이용하여 구현한다.
트리는 비선형 자료구조이며, 계층적(Hierarchical) 자료구조라고도 불린다.
트리 자료구조는 주로 컴퓨터의 디렉터리 구조, 조직도 등에 이용된다.
- 깊이(depth): 루트 노드에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
- 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
- 높이(height): 트리의 최대 깊이
- 차수(degree): 각 노드가 자식 노드와 연결된 간선 개수
- 잎 노드(leaf node): 자식 노드가 없는 노드(단말 노드, 말단 노드)
- 내부 노드(internal node): 잎 노드가 아닌 노드
트리 순회 방식
1) 전위 순회(pre-order): root -> 왼쪽 자식 -> 오른쪽 자식
2) 중위 순회(in-order): 왼쪽 자식 -> root -> 오른쪽 자식
3) 후위 순회(post-order): 왼쪽 자식 -> 오른쪽 자식 -> root
4) 레벨 순회(level-order): 루트부터 계층별로 방문한다.
- 레벨 순회는 너비 우선 탐색(Breadth-First Search, BFS)인 반면 나머지는 깊이 우선 탐색(Depth-First Search, DFS)이다.
트리의 종류
1) 이진 트리(Binary Tree): 각 노드들이 최대 2개의 자식 노드를 가질 수 있는 트리
2) 완전 이진 트리(Complete Binary Tree): 마지막 레벨을 제외한 모든 레벨이 채워져 있으며, 마지막 레벨은 왼쪽부터 채워져 있는 트리
3) 전 이진 트리(Full Binary Tree): 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리
4) 포화 이진 트리(Perfect Binary Tree): 모든 레벨에 노드가 전부 채워져 있으며, 모든 노드는 0개 또는 2개의 자식 노드를 갖는 트리
5) 이진 탐색 트리(Binary Search Tree, BST): 부모의 키가 왼쪽 자식 노드의 키보다 크고, 오른쪽 자식 노드의 키보다 작은 트리. 중복값을 허용하지 않으며, 데이터의 빠른 검색을 위해 만들어졌다. 특정 값에 대해 탐색하는 시간 복잡도가 트리의 높이에 의존하기 때문에 평균적으로 logN의 시간복잡도를 갖는다.
그러나, 이진탐색트리의 왼쪽 서브 트리와 오른쪽 서브 트리의 균형이 맞지 않고 한 쪽으로만 치우쳐진 경우에는 트리의 높이 자체가 N이 되므로 Worst Case의 경우 O(N)의 시간복잡도를 갖는다.
2. 힙(Heap)
힙(Heap)은 완전 이진 트리의 한 종류로, 우선순위 큐를 위해(가장 작거나 큰 값을 찾기 위해) 만들어진 자료구조이다. 중복값을 허용하지 않는 이진 탐색 트리와는 달리 중복값을 허용한다.
- 최대 힙(max heap): 부모 노드의 키가 자식 노드의 키보다 크거나 같은 완전 이진 트리
- 최소 힙(min heap): 부모 노드의 키가 자식 노드의 키보다 작거나 같은 완전 이진 트리
< 이진 탐색 트리와 힙의 차이점 >
- 둘 다 이진 트리이다.
- 이진 탐색 트리는 왼쪽 자식 노드, 부모 노드, 오른쪽 자식 노드 순으로 크기가 크지만, 힙은 순서가 없다.
- 이진 탐색 트리는 탐색용 자료 구조이고, 힙은 최댓값과 최솟값을 찾기 위한 자료 구조이다.
힙은 주로 배열을 이용하여 구현된다. 구현을 쉽게 하기 위해 배열의 첫 번째 인덱스인 0은 사용하지 않는다.
삽입 연산: 트리의 가장 마지막 노드에 이어서 삽입한 후, 부모 노드와의 크기 비교를 통해 적절한 위치를 찾는다.
삭제 연산: 힙의 루트 노드가 삭제되면, 빈 루트 노드의 자리는 힙의 가장 마지막 노드를 가져와 채운다. 새로 채삽입된 노드와 자식 노드와의 크기 비교를 통해 이동하며 적절한 위치를 찾는다.
삽입과 삭제의 시간복잡도는 모두 O(logn)이다.
단, 완전 이진 트리가 아닐 경우에는 공간 낭비가 있을 수 있다는 단점이 있다.
힙은 주로 운영 체제에서의 작업 스케줄링, 네트워크 트래픽 제어, 우선순위 큐, 힙 정렬 등에 이용된다.
[Max Heap]
class MaxHeap:
def __init__(self, size):
self.MAX_SIZE = size
self.heap = [None] * (self.MAX_SIZE + 1)
self.size = 0
def heappush(self, data):
if self.size >= self.MAX_SIZE:
return
self.size += 1
self.heap[self.size] = data
child = self.size
parent = child // 2
while child != 1 and self.heap[child] > self.heap[parent]:
self.heap[child], self.heap[parent] = self.heap[parent], self.heap[child]
child = parent
parent = child // 2
def isLeef(self, pos):
if pos * 2 > self.size:
return True
return False
def heapify(self, pos):
if not self.isLeef(pos):
if self.heap[pos] < self.heap[pos*2]:
self.heap[pos], self.heap[pos*2] = self.heap[pos*2], self.heap[pos]
self.heapify(pos*2)
elif pos*2+1 <= self.size and self.heap[pos] < self.heap[pos*2+1]:
self.heap[pos], self.heap[pos*2+1] = self.heap[pos*2+1], self.heap[pos]
self.heapify(pos*2+1)
def heappop(self):
if self.size == 0:
return None
ret = self.heap[1]
self.heap[1] = self.heap[self.size]
self.heap[self.size] = None
self.size -= 1
self.heapify(1)
return ret
High Level
Q. 트리를 거울에 비춘 것처럼 좌우대칭으로 만들기 위한 작업은?
=> 재귀적으로 left와 right child의 포인터를 스왑한다. / 거울에 비춘 것처럼 좌우대칭으로 만들기 위해서는 노드가 가진 데이터뿐만 아니라 트리의 구조가 바뀌어야 한다. 재귀적으로 subtree 단위의 교환을 반복해주어야 한다.
Q. 노드 수가 n인 이진 트리의 검색 시간 복잡도는 ___이다.
=> O(n) / 이진 트리는 정렬되어 있지 않기 때문에 원하는 노드를 찾기 위해 트리를 전부 탐색해야 한다.
Q. 노드 수가 n인 이진 탐색 트리(Binary Search tree, BST)의 검색 시간 복잡도는 ___이다.
=> O(logn) / 이진 트리와 달리 BST는 정렬되어 있기 때문에 이진 검색 알고리즘(Bianry search algorithm)이 적용 가능하다.
Q. BST의 성능을 개선하는 방법은?
=> BST의 양쪽 높이의 균형을 맞춘다. 대표적으로 개량된 BST 트리로 AVL 트리, Red-Black 트리가 있다.
'자료구조' 카테고리의 다른 글
| 세그먼트 트리(Segment Tree) 자료구조 (0) | 2023.02.04 |
|---|---|
| 그래프(Graph) (0) | 2022.12.30 |
| 해시 테이블(HashTable) (0) | 2022.12.30 |
| 스택(Stack)과 큐(Queue) (0) | 2022.12.29 |
| 배열(ArrayList)과 연결 리스트(LinkedList) (0) | 2022.12.29 |