.png)
📍 트리
비선형구조, 계층형, 망의 형태로 표현 ex) 파일
✏️ 용어 정리
Node: 트리에서 데이터를 저장하는 기본 요소
Root Node: 트리 맨 위에 있는 노드
Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
Parent Node: 어떤 노드의 상위 레벨에 연결된 노드
Child Node: 어떤 노드의 하위 레벨에 연결된 노드
Leaf Node(Terminal Node): Child Node가 하나도 없는 노드
Sibling: 동일한 Parent Node를 가진 노드
Depth: 트리에서 Node가 가질 수 있는 최대 Level
📍 이진트리
이진 트리(Binary Tree)의 특징은 각 노드가 최대 두 개의 자식을 가진다는 것입니다. (0,1,2개)
ex)
o Level 0
o o o Level 1
o o o Level 2 # 이진 트리(X)
o Level 0
o o Level 1
o o o Level 2 # 이진 트리(O)📍 완전이진트리
완전 이진 트리(Complete Binary Tree)의 특징은 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야 한다는 것 입니다!
ex)
o Level 0
o o Level 1
o o Level 2 # -> 이진 트리 O 완전 이진 트리 X
o Level 0
o o Level 1
o o o Level 2 # -> 이진 트리 O 완전 이진 트리 O예를 들어, [None, 8, 6, 3, 4, 2, 5] 배열로 트리 구조를 분석해보겠습니다.
다음과 같은 방법으로 트리 구조를 파악할 수 있습니다.
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 -> 부모의 인덱스
- [None, 8, 6, 3, 4, 2, 5] 는
8 밑에 6, 3 이 있고, 6, 3 밑에 4, 2, 5가 있는 완전 이진 트리
각 레벨에 노드가 꽉 차 있다면 , 노드의 개수는 2의 k승 개가 있다!
Q. 만약 높이가 h 인데 모든 노드가 꽉 차 있는 완전 이진 트리라면
모든 노드의 개수는 몇개일까요?
1 + 2^1 + 2^2 + 2^3 + 2^4 ..... 2^h
즉, 이를 수식으로 표현하면 2^(h+1) - 1 이 됩니다!즉, 높이가 h 일 때 최대 노드의 개수는 개 입니다.
그러면 이 때 최대 노드의 개수가 N이라면, h 는 뭘까요?
→
라고 할 수 있습니다!
즉 완전 이진 트리 노드의 개수가 N일 때 최대 높이가 이므로
이진 트리의 높이는 최대로 해봤자 이다!
📍 힙
힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조입니다. = 부모 노드의 값이 자식 노드의 값보다 항상 커야 합니다.
- 힙은 다음과 같이 최대값을 맨 위로 올릴수도 있고,
최솟값을 맨 위로 올릴 수도 있습니다! 최댓값이 맨 위인 힙을 Max 힙,
최솟값이 맨 위인 힙을 Min 힙이라고 합니다!
💡 Max힙의 원소 추가
- 원소를 맨 마지막에 넣습니다.
- 그리고 부모 노드와 비교합니다. 만약 더 크다면 자리를 바꿉니다.
- 부모 노드보다 작거나 가장 위에 도달하지 않을 때까지 2. 과정을 반복합니다.
(= 부모노드와 계속 비교하면서 위치 바꾸기!)
class MaxHeap:
def __init__(self):
self.items = [None]
#1. 새 노드를 맨 끝에 추가한다.
#2. 새 노드를 부모와 비교한다, 크면 바꾼다.
#3. 이 과정을 꼭대기까지 반복한다.
def insert(self, value):
# 구현해보세요!
self.items.append(value)
cur_index = len(self.items)-1
while cur_index > 1:
parent_index = cur_index // 2
if self.items[cur_index] > self.items[parent_index]:
self.items[cur_index], self.items[parent_index]
= self.items[parent_index], self.items[cur_index]
cur_index = parent_index
else:
break
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)) 만큼의 시간 복잡도를 가진다
💡 Max힙의 원소 제거
최대 힙에서 원소를 삭제하는 방법은 최댓값, 루트 노드를 삭제하는 것
- 루트 노드와 맨 끝에 있는 원소를 교체한다.
- 맨 뒤에 있는 원소를 (원래 루트 노드)를 삭제한다.
- 변경된 노드와 자식 노드들을 비교합니다. 두 자식 중 더 큰 자식과 비교해서 자신보다 자식이 더 크다면 자리를 바꿉니다.
- 자식 노드 둘 보다 부모 노드가 크거나 가장 바닥에 도달하지 않을 때까지 3. 과정을 반복합니다.
- 2에서 제거한 원래 루트 노드를 반환합니다.
def delete(self):
# 구현해보세요!
self.items[1] , self.items[-1] = self.items[-1] , self.items[1]
prev_max = self.items.pop() #맨 끝 원소 반환
# 여기부터 힙의 규칙을 지키기 위한 코드
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[cur_index]:
max_index = left_child_index
# 오른쪽 자식이 있고, 오른쪽 자식이 부모노드 보다 더 클 경우
if right_child_index <= len(self.items)-1 and self.items[right_child_index] > self.items[cur_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]
return prev_max
맥스 힙의 원소 삭제는 O(log(N)) 만큼의 시간 복잡도를 가진다
