늦은 프로그래밍 이야기
트리, 힙 본문
트리 (Tree)
특징
- 계층형 비선형 자료구조.
- 데이터가 계층적 혹은 망으로 구성
- 표현에 초점이 맞춰져 있다.
- 위 아래가 구분되어 있다.
용어
- Node : 각각의 데이터를 저장하는 기본요소. 데이터 뿐만 아니라 포인터까지 포함.
- Root Node: 맨 위에 있는 노드
- Level : 최상위 0, 깊이마다 1~
- Parent Node : 특정 노드의 상위 레벨 노드
- Child Node : 특정 노드의 하위 레벨 노드
- Leaf Node : Child 노드가 하나도 없는 노드
- Sibiling : 동일한 Parent Node를 가진 노드
- Depth : 트리에서 Node가 최대로 가질 수 있는 Level
트리의 종류
1) 이진트리
- 각 노드가 최대 두개의 자식을 가질 수 있음.
2) 완전이진트리
- 왼쪽 노드부터 차례대로 삽입.
배열로 표현하는 방법 (완전 이진 트리)
1) 0번째 인덱스는 사용하지 않는다.(편의를 위해) None값을 배열에 넣고 시작
2) Level 0의 노드를 배열의 1번 인덱스에 넣는다.
2) Level 1의 노드를 배열의 2번, 3번 인덱스에 왼쪽부터 순서대로 넣는다.
3) Level 2의 노드를 배열의 4, 5, 6, 7번 인덱스에 왼쪽부터 순서대로 넣는다.
4) 하위 레벨의 노드들을 배열의 다음 인덱스에 왼쪽부터 순서대로 넣는다.
- 배열의 인덱스로 트리 구조 파악
1) 현재 인덱스 * 2 = 왼쪽 자식의 인덱스
2) 현재 인덱스 * 2 + 1 = 오른쪽 자식의 인덱스
3) 현재 인덱스 // 2 = 부모의 인덱스
트리의 높이
- 루트 노드부터 가장 아래 리프 노드까지의 길이. 레벨의 차로 계산.
- 노드가 꽉차 있다면 K레벨에 2^K개의 노드 존재.
- 높이 h의 꽉찬 이진트리의 총 노드 갯수는 2^(h+1)-1.
- 이진트리의 최대 높이는 O(log(N)).
힙 (Heap)
특징
- 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전이진트리
- 상위 레벨부터 하위 레벨까지 내림차순 혹은 오름차순 정렬할 수 있음.
- max 힙 : 최대값이 상위 레벨에 위치
- min 힙 : 최소값이 상위 레벨에 위치
- 힙에 원소 추가 : 맨 뒤에 원소를 추가하고 부모 노드들과 비교하여 자리를 조정한다.
- 힙에 원소 삭제 : 루트 노드를 맨 뒤의 노드와 교체하고 삭제 후 새로운 루트 노드의 자리를 조정한다.
- 추가와 삭제 모두 O(logN)만큼의 시간복잡도를 가진다.
구현
맥스 힙에 원소 추가
- 원소를 맨 마지막에 넣는다.
- 부모 노드와 비교한다. 만약 부모 노드보다 크다면 자리를 교체한다.
- 부모 노드보다 작거나 가장 위에 도달할 때까지 반복.
class MaxHeap:
def __init__(self):
self.items = [None] # None 값을 배열에 넣는다 (인덱스 0은 사용하지 않음)
def insert(self, value):
self.items.append(value) # 트리에 밸류 값을 넣는다.
cur_index = len(self.items) - 1 # 배열의 끝에 현재 인덱스를 위치 시킨다.
while cur_index > 1: # cur_index가 루트 노드에 올때까지 반복
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 # 부모노드 보다 작은 경우 반복문을 벗어난다.
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)만큼의 시간복잡도를 가진다.
맥스 힙의 원소 제거 (루트 노드를 삭제)
- 루트 노드와 맨 끝에 있는 원소를 교체하고 맨 뒤로 이동한 루트노드를 삭제한다.
- 변경된 노드와 자식 노드를 비교한다. 두 자식 중 더 큰 자식 노드와 비교해서 자식노드가 더 크다면 자리를 교체한다.
- 자식 노드 둘보다 부모 노드가 크거나 가장 바닥에 도달할 때까지 반복한다.
- 삭제한 원래 루트 노드를 반환한다.
def delete(self):
self.items[1], self.items[-1] = self.items[-1], self.items[1] # 루트노드와 맨뒤의 노드를 교체한다.
prev_max = self.items.pop() # 맨뒤로 이동한 루트노드를 제거하고 prev_max 변수에 담아둔다.
cur_index = 1 # 새로운 루트노드를 cur_index에 담는다.
while cur_index <= len(self.items) - 1: # 이동한 노드가 맨뒤에 갈때까지 반복
left_child_index = cur_index * 2 # 왼쪽 자식노드
right_child_index = cur_index * 2 + 1 # 오른쪽 자식노드
max_index = cur_index # max_index 변수에 현재 인덱스 저장
if left_child_index <= len(self.items) - 1 and self.items[left_child_index] > self.items[max_index]:
max_index = left_child_index # 왼쪽 자식노드가 인덱스 내에 있으면서 현재 인덱스보다 큰 경우 왼쪽 자식노드를 max_index에 담는다.
if right_child_index <= len(self.items) - 1 and self.items[right_child_index] > self.items[max_index]:
max_index = right_child_index # 오른쪽 자식노드가 인덱스 내에 있으면서 현재 인덱스보다 큰 경우 오른쪽 자식노드를 max_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 # 위 1번 2번 조건문에 해당하면, 현재 인덱스와 가장 큰 인덱스를 교체하고, 가장 큰 인덱스 값을 현재 인덱스에 이식한다.
return prev_max # 삭제한 루트노드를 반환
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))만큼의 시간복잡도를 가진다.
'내일배움캠프 > TIL, WIL' 카테고리의 다른 글
| 221115 TIL (Java 객체지향) (0) | 2022.11.15 |
|---|---|
| 221114 TIL (자료구조 알고리즘, Java기초, 자주 발생하는 에러) (0) | 2022.11.14 |
| 2주차 WIL (0) | 2022.11.13 |
| 221111 TIL (자료구조 알고리즘) (12) | 2022.11.11 |
| 221110 TIL (자료구조 알고리즘) (1) | 2022.11.10 |
