[알고리즘] 트리, 힙
트리란?
뿌리와 가지로 구성되어 거꾸로 세워놓은 나무처럼 보이는 계층형 비선형 자료 구조
비선형자료구조: 계층적 혹은 망으로 구성되어 있는 것 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있지 않는다.
트리의 종류
1. 이진 트리
각 노드가 최대 두개의 자식을 가지는 것이다. 하위의 노드가 4 ~5 개 일 수 없다. 무조건 0,1,2개만 있어야 한다.
2. 완전이진트리
노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야 한다.
완전 이진 트리의 높이:
트리의 높이는 루트 노드부터 가장 아래 리프 노드까지의 길이이다.
그렇다면 레벨에 노드가 꽉 차있을 경우에는 몇 개가 생길까?
1 Level 0 -> 1개
2 3 Level 1 -> 2개
4 5 6 7 Level 2 -> 4개
8 9....... 14 15 Level 3 -> 8개
Level k -> 2^k 개
2^(h+1) -1 이 모든 노드의 갯수이다. h= Level 의 층 갯수
예를들어, h =8 일 때, 2^9-1 = N, N= 511 이다
즉, 높이가 h일 때 최대 노드의 갯수는 2^(h+1) -1 이다.
힙
힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리이다.
힙은 특정 순서에 맞춰서 항상 데이터를 정렬해두는 자료구조이다.
데이터를 뽑아올 때 항상 순서대로 값을 가져올 수 있다.
그렇다면 힙은 "정렬" 이랑 무슨 차이가 있는가?
정렬은 항상 O(NlogN) 만큼의 시간 복잡도가 매번 걸리는 연산이다.
힙이라는 자료구조는 데이터를 가져오고 빼는데 log(N) 만큼의 시간 복잡도가 걸리는 대신 매번 정렬을 해주지 않아도 정렬된 상태를 유지할 수 있다.
그래서 정렬이 된 데이터 삽입 삭제가 잦은 상황에서는 힙이 효율적이다.
힙을 구현할려면?
힙은 항상 큰 값이 상위 레벨에 있고, 작은 값이 하위 레벨에 있도록 하는 자료구조이다.
즉 부모 노드의 값이 자식 노드의 값보다 항상 커야한다.
예를들어,
8 Level 0
6 3 Level 1
2 1 Level 2 # -> 이진 트리 O 완전 이진 트리 X 이므로 힙이 아닙니다!
8 Level 0
6 3 Level 1 # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
4 2 1 Level 2 # 자식 노드보다 크니까 힙이 맞습니다!
8 Level 0
6 3 Level 1 # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
4 2 5 Level 2 # 자식 노드보다 크지 않아서 힙이 아닙니다..!힙은 완전 이진 트리 구조이기 때문에 왼쪽부터 정렬되어야 한다.
부모노드가 자식노드 보다 클 경우 Max Heap, 자식노드보다 부모노드가 작을 경우 Min Heap 이라고 한다.
이러한 Max Heap, Min Heap 에 대한 규칙은 지켜져야 한다.
이 맥스 힙에서 9를 추가해보겠습니다!
8 Level 0
6 3 Level 1
4 2 1 Level 2
1. 맨 마지막에 원소를 넣습니다.
8 Level 0
6 3 Level 1
4 2 1 9 Level 2
2-1. 부모 노드와 비교합니다. 3보다 9가 더 크니까! 둘의 자리를 변경합니다.
8 Level 0
6 3 Level 1
4 2 1 9 Level 2
8 Level 0
6 9 Level 1
4 2 1 3 Level 2
2-2. 다시 부모 노드와 비교합니다. 8보다 9가 더 크니까! 둘의 자리를 변경합니다.
8 Level 0
6 9 Level 1
4 2 1 3 Level 2
9 Level 0
6 8 Level 1
4 2 1 3 Level 2
3. 가장 위에 도달했으므로 멈춥니다. 힙의 특성을 그대로 유지해 데이터를 삽입했습니다!
9 Level 0
6 8 Level 1
4 2 1 3 Level 2
실제 코드로 구현해보기:
class MaxHeap:
def __init__(self):
self.items = [None]
def insert(self, value):
#1. 원소 들어온 것을 추가한다.
self.items.append(value)
#2. 각각 비교하여, 원소값의 인덱스가 1이 된다면 종료한다.
current_index = len(self.items) -1
print("self.items : " , self.items)
print("current_index = " , current_index )
#root인덱스가 되기 전까지만 수행한다.
while current_index > 1 :
#부모 노드랑 비교해서 내가 더 크다면 위치를 바꿔라
parent_index = current_index // 2
print("parent_index = " , parent_index )
if self.items[current_index] > self.items[parent_index] :
self.items[current_index], self.items[parent_index] = self.items[parent_index], self.items[current_index]
current_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] 가 출력되어야 합니다!
맥스 힙의 원소 제거도 해보자
최대 힙에서 원소를 삭제하는 방법은 최댓값, 루트 노드를 삭제하는 것이다.
스택과 같이 맨 위에 있는 원소만 제거할 수 있고, 다른 위치의 노드를 삭제할 수 는 없다
1. 루트 노드와 맨 끝에 있는 원소를 교체한다.
2. 맨 뒤에 있는 원소를 (원래 루트 노드)를 삭제한다.
3. 변경된 노드와 자식 노드들을 비교합니다. 두 자식 중 더 큰 자식과 비교해서 자신보다 자식이 더 크다면 자리를 바꿉니다.
4. 자식 노드 둘 보다 부모 노드가 크거나 가장 바닥에 도달하지 않을 때까지 3. 과정을 반복합니다.
5. 2에서 제거한 원래 루트 노드를 반환합니다.
실제 코드로 구현해보기:
def delete(self):
#마지막의 인덱스 접근하기
self.items[-1]
self.items[1], self.items[-1] = self.items[-1], self.items[1]
print("self.items = 봐1" , self.items)
prec_max = self.items.pop()
print("self.items = 봐" , self.items)
cur_index = 1
left_child = cur_index * 2
right_child = cur_index * 2 + 1
#맨끝에 도달하기 전까지만 돌리겠다.
while cur_index <=len(self.items) -1 :
left_child = cur_index * 2
right_child = cur_index * 2 + 1
max_index = cur_index
if left_child <= len(self.items) -1 and self.items[cur_index] < self.items[left_child] :
max_index = left_child
if right_child <= len(self.items) -1 and self.items[cur_index] < self.items[right_child] :
max_index = right_child
if max_index == cur_index :
break
self.items[max_index], self.items[cur_index] =self.items[cur_index], self.items[max_index]