트리(tree)
나무의 뿌리처럼 보이는 계층형 비선형 자료 구조
큐, 스택과 같은 선형 구조는 자료를 저장하고 꺼내는데 유용하다면
비선형 구조는 표현에 유용하다.
폴더의 구조들이나 가족관계도는 비선형 구조의 대표적인 형태이다.
트리에 사용되는 용어들
Node: 트리에서 데이터를 저장하는 기본 요소
Root Node: 트리 맨 위에 있는 노드
Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
Parent Node: 어떤 노드의 상위 레벨에 연결된 노드
Child Node: 어떤 노드의 하위 레벨에 연결된 노드
Leaf Node(Terminal Node): Child Node가 하나도 없는 노드
Sibling: 동일한 Parent Node를 가진 노드
Depth: 트리에서 Node가 가질 수 있는 최대 Level
트리의 종류(이진 트리, 완전 이진 트리)
트리의 종류는 다양하지만, 강의에서는 2가지만 배운다.
이진 트리(Binary Tree)
각 노드가 최대 2개(0,1,2)의 Child Node만 가질 수 있다.
완전 이진 트리(Complete Binary Tree)
노드를 삽입할 때 왼쪽 최하단 노드부터 차례대로 삽입해야 한다.
Child Node 2개를 전부 채우지 않고 다음 노드로 넘어간다면 완전 이진 트리가 아니다.
완전 이진 트리를 배열로 표현
트리를 구현할 때는 편의성을 위해 0번째 인덱스는 사용되지 않는다.
8 Level 0 -> [None, 8] 첫번째 레벨의 8을 넣고,
6 3 Level 1 -> [None, 8, 6, 3] 다음 레벨인 6, 3을 넣고
4 2 5 Level 2 -> [None, 8, 6, 3, 4, 2, 5] 다음 레벨인 4, 2, 5를 넣으면 됩니다!위와 같은 트리에서 구조를 파악하는 방법
1. 현재 인덱스 2 -> 왼쪽 자식의 인덱스
2. 현재 인덱스 2 + 1 -> 오른쪽 자식의 인덱스
3. 현재 인덱스 // 2 -> 부모의 인덱스
완전 이진 트리의 높이
트리의 높이는 루트 노드부터 가장 아래 리프 노드까지의 길이를 말한다.
o Level 0 # 루트 노드
o o Level 1
o o o Level 2 # 가장 아래 리프 노드
이 트리의 높이는 ? 2 - 0 = 2! -. 모든 노드가 차있다면, 각 레벨 k에 최대로 들어갈 수 있는 노드의 개수는 2^k개 이다.
-. 모든 노드가 차있고, 높이가 h라고 한다면 모든 노드들의 개수는 2^(h+1)-1개 이다.
-. 모든 노드의 개수가 N 이라고 할 때 최대 높이는 log_2(N+1) - 1 이므로 이진 트리의 높이는 최대로 해봤자 O(log(N))이다.
힙(heap)
-. 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리
-. 힙은 기본적으로 큰 값이 상위 레벨에(level 0), 작은 값이 하위레벨에(level h) 있도록 하는 자료 구조(Parent Node와 Child Node 끼리만 보면 된다.)
예시
8 Level 0
6 3 Level 1 # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
4 2 1 Level 2 # 자식 노드보다 크니까 힙이 맞습니다!: 4보다 3이 상위레벨에 있지만 부모/자식 관계가 아니므로 힙이 맞다.
-. 위에서 말했던 최댓값이 상위 레벨에 있는 배열을 Max Heap
Heap에서 추가/제거는 항상 마지막 노드의 위치에서만 가능하다...?
Max Heap에서 원소를 추가 하려면
1. 원소를 맨 마지막에 넣고
2. 부모 노드와 비교, 값이 올바르지 않다면 자리를 바꾼다.
3. 올바른 값이 될 때 까지 2.의 과정을 반복한다.
예제 - Max Heap에 원소 추가하기
class MaxHeap:
def __init__(self):
self.items = [None] # 완전이진트리를 배열로 표현하기 위해 맨 처음은 None으로 고정한다.
def insert(self, value):
self.items.append(value) # self.items에 새로운 value를 추가할거다
curr_index = len(self.items) - 1 # 가장 마지막에 넣은 노드의 인덱스를 curr_index라고 한다
while curr_index > 1: # 꼭대기로 갈 때 까지 반복
parent_index = curr_index // 2 # 부모 노드의 인덱스는 현재 노드의 인덱스 // 2
if self.items[curr_index] > self.items[parent_index]: # 만약 현재 노드가 부모 노드보다 크다면 둘의 값을 바꾼다
self.items[curr_index], self.items[parent_index] = self.items[parent_index], self.items[curr_index]
curr_index = parent_index # 바꾸고나서 현재 인덱스는 부모의 인덱스로 올라간다
else: # 비교했을 때 문제가 없다면
break # 반복문을 멈춘다
return
max_heap = MaxHeap()
max_heap.insert(3)
max_heap.insert(4)
max_heap.insert(2)
max_heap.insert(9)
print(max_heap.items) # [None, 9, 4, 2, 3] 가 출력되어야 합니다!완전 이진 트리의 최대 높이는 O(log(N))이다.
그렇다면 반복하는 최대 횟수도 O(log(N))이다.
즉 맥스 힙의 원소 추가는 O(log(N))만큼의 시간 복잡도를 가진다.
Max Heap에서 원소를 제거 하려면
힙은 우선순위 큐 역할을 하기 위해 사용되는 자료구조이므로, 항상 최댓값 혹은 최솟값을 내어놓아야 한다. 여기서는 Max Heap 이므로 최댓값 만을 삭제할 수 있다.
1. 루트 노드와 맨 끝에 있는 원소를 교체한다.
2. 맨 뒤에 있는 원소를 (원래 루트 노드)를 삭제한다.
3. 변경된 노드와 자식 노드들을 비교합니다. 두 자식 중 더 큰 자식과 비교해서 자신보다 자식이 더 크다면 자리를 바꿉니다.
4. 자식 노드 둘 보다 부모 노드가 크거나 가장 바닥에 도달하지 않을 때까지 3. 과정을 반복합니다.
5. 2에서 제거한 원래 루트 노드를 반환합니다.
예제 - Max Heap에 원소 제거하기
class MaxHeap:
def __init__(self):
self.items = [None]
def insert(self, value):
self.items.append(value)
cur_index = len(self.items) - 1
while cur_index > 1: # cur_index 가 1이 되면 정상을 찍은거라 다른 것과 비교 안하셔도 됩니다!
parent_index = cur_index // 2
if self.items[parent_index] < self.items[cur_index]:
self.items[parent_index], self.items[cur_index] = self.items[cur_index], self.items[parent_index]
cur_index = parent_index
else:
break
def delete(self):
self.items[1], self.items[-1] = self.items[-1], self.items[1] # 루트 노드와, 마지막 노드의 위치를 바꿔준다.
prev_max = self.items.pop() # 맨 뒤에 원소(8)을 뽑아내고, 반환해줘야 하므로 prev_max에 저장해둔다.
cur_index = 1
while cur_index <= len(self.items) - 1:
left_child_index = cur_index * 2
right_child_index = cur_index * 2 + 1
max_index = cur_index
if left_child_index <= len(self.items) - 1 and self.items[left_child_index] > self.items[max_index]:
max_index = left_child_index
if right_child_index <= len(self.items) - 1 and self.items[right_child_index] > self.items[max_index]:
max_index = right_child_index
if max_index == cur_index:
break
self.items[cur_index], self.items[max_index] = self.items[max_index], self.items[cur_index]
cur_index = max_index
return prev_max # 8 을 반환해야 합니다.
max_heap = MaxHeap()
max_heap.insert(8)
max_heap.insert(6)
max_heap.insert(7)
max_heap.insert(2)
max_heap.insert(5)
max_heap.insert(4)
print(max_heap.items) # [None, 8, 6, 7, 2, 5, 4]
print(max_heap.delete()) # 8 을 반환해야 합니다!
print(max_heap.items) # [None, 7, 6, 4, 2, 5]
완전 이진 트리의 최대 높이는 O(log(N))이다.
그렇다면 반복하는 최대 횟수도 O(log(N))이다.
즉 맥스 힙의 원소 삭제는 O(log(N))만큼의 시간 복잡도를 가진다.
이러한 Max Heap의 특성들을 활용하여 원소를 최댓값에 빠르게 추가하거나 삭제하는 문제 풀이 때 사용하면 좋은 구조이다.
그래프(Graph)
연결되어 있는 정점와 정점간의 관계를 표현할 수 있는 자료구조. [천재학습백과]
-. 연결 관계에 초점이 맞춰져있는 자료 구조
그래프에서 사용되는 용어들
노드(Node): 연결 관계를 가진 각 데이터를 의미합니다. 정점(Vertex)이라고도 합니다.
간선(Edge): 노드 간의 관계를 표시한 선.
인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점)
유방향 그래프, 무방향 그래프
강의에서는 무방향 그래프만 배운다.
그래프 라는 개념을 컴퓨터에서 표현하는 방법
1. 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현
2. 인접 리스트(Adjacencdy List) : 링크드 리스트로 그래프의 연결 관계를 표현
이해를 돕기 위한 그림 설명
이해를 돕기 위해 숫자로 표현
1. 인접 행렬(공간)
이를 2차원 배열로 표현하면 아래와 같다
자신과 자신은 연결되지 않은 상태.
이번엔 다르게 배열로 표현하면 아래와 같다.
graph = [
[False, True, False, False],
[True, False, True, False],
[False, True, False, True],
[False, False, True, False]
]2. 인접 리스트(시간)
인접 리스트로 표현하면 아래와 같다.
0 -> 1
1 -> 0 -> 2
2 -> 1 -> 3
3 -> 2인접 리스트는 모든 노드에 연결된 노드에 대한 정보를 차례로 저장한다.
이를 딕셔너리로 표현하면 아래와 같다.
graph = {
0: [1],
1: [0, 2],
2: [1, 3],
3: [2]
}이 두 방식은 시간 또는 공간 중 어느 것을 우선적으로 할 것인가의 차이가 있다.
