[자료구조/알고리즘] 이진 트리, 완전 이진 트리, 힙(Heap)

1. 이진트리

크기가 9이고 높이가 3인 이진 트리 예시, 출처 _ 위키백과

각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다. 이때 전체 자료의 수가 크기, 최상단 노드로부터 최하단 노드로까지의 거리가 높이이다. 노드가 하나 뿐일 때는 높이가 0이다.

 

2. 포화 이진 트리(Perfect Binary Tree)와 완전 이진 트리(Complete Binary Tree)

 

> 포화 이진 트리(Perfect Binary Tree)

모든 잎의 레벨이 동일하고, 내부 노드들은 모두 2개의 자식을 가지는 트리를 말한다. 즉, 쉽게 말하면 꽉 차 있는 이진 트리이다.

포화 이진 트리 예시

> 완전 이진 트리(Complete Binary Tree)

포화 이진 트리의 잎(leaf)들을 오른쪽부터 순서대로 제거하여 얻을 수 있는 트리를 말한다. 힙(Heap)이 완전 이진 트리를 기반으로 한다.

완전 이진 트리 예시

3. 힙(Heap)

> 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)다. 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙을 '최대 힙', 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙을 '최소 힙'이라고 부른다.

> 키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는다.

> 힙에서는 가장 높은 우선순위(최소 힙의 경우 최솟값)를 가지는 노드가 항상 뿌리노드(최상단)에 오게 되는 특징이 있으며, 이를 응용하면 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다. (우선순위 큐는 특정 순서대로 dequeue가 이루어지는 큐를 말한다.)

최대 힙의 예시, 출처 _ 위키백과

> 특정 자료가 힙에 추가되는 경우(최대힙 기준)

이진트리의 구조를 유지하며 leaf로 데이터를 추가한 뒤, 자식 노드가 부모 노드보다 작을 때까지 두 자료의 위치를 바꾼다. 즉, 힙의 구조를 유지한다.

> 특정 자료를 힙에서 제거하는 경우(최대힙 기준)

최우선순위 자료(최댓값)인 100이 제거된다. 그 다음, 비어있는 최상단 노드의 위치에 가장 마지막 노드에 해당하는 7을 채워 넣은 뒤, 자식 노드가 부모 노드보다 작을 때까지 두 자료의 위치를 바꾼다. 즉, 힙의 구조를 유지한다.

[참고] https://www.youtube.com/watch?v=jfwjyJvbbBI

> 파이썬에서는 heapq 모듈로 구현할 수 있으며, 내부적으로는 위 그림처럼 Array 구조에서의 index를 이용해 연산이 이루어지는 것 같다.