[자료구조]이진 트리(Binary Tree)

트리(Tree)란?

-트리는 계층적인 구조를 표현할 때 사용할 수 있는 자료구조이다. 스택이나 큐와 달리 비선형이다.

-나무의 형태를 뒤집은 것과 같이 생겼고, 노드로 이루어져 있다.

 

루트 노드(root code) : 부모가 없는 최상위 노드. 트리는 하나의 루트 노드만을 가진다. 

단말 노드(leaf node) : 자식이 없는 노드.

형제(sibling) : 같은 부모를 가지는 노드. 

 

 

이진 트리(Binary Tree)

-이진 트리는 최대 2개의 자식을 가질 수 있는 트리를 말한다

 

포화 이진 트리(Full Binary Tree)

-단말 노드를 제외한 모든 노드가 두 자식을 가지고 있는 트리를 말한다. 

 

완전 이진 트리(Complete Binary Tree)

-모든 노드가 왼쪽 자식부터 차근차근 채워진 트리다. 

 

높이 균형 트리(Height Balanced Tree)

-왼쪽 자식 트리와 오른쪽 자식 트리의 높이가 1 이하인 트리다. 

 

 

힙(Heap)

-원소들 중에서 최댓값 혹은 최솟값을 빠르게 찾아내는 자료구조.

-완전 이진 트리의 자료구조를 따른다. 

-우선순위가 높은 노드가 루트에 위치한다. 

 

-힙은 원소의 삽입과 삭제를 위해 O(logN)의 수행 시간을 요구한다. 

-단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 방식으로 정렬을 수행할 수 있고, 이때 O(NlogN)의 수행 시간을 요구한다. 

 

최대 힙(max heap) : 부모 노드의 키 값이 자식 노드보다 크다. 루트 노드의 값이 가장 크며, 값이 큰 데이터가 우선순위를 가진다. 

최소 힙(min heap) : 부모 노드의 키 값이 자식 노드보다 작다. 루트 노드의 값이 가장 작으며, 값이 작은 데이터가 우선순위를 가진다. 

 

최소 힙 구성 함수 : Heapify

힙에 원소가 삽입되었을 때 : 상향식. 부모로 거슬러 올라가며, 부모보다 자신이 더 작은 경우에 부모와 위치를 교체한다. 

힙에 원소가 제거되었을 때 : 하향식. 가장 마지막 노드가 루트 노트의 위치에 오도록 하고, 이후 루트 노드에서부터 더 작은 자식 노드로 내려간다.