힙과 트리

트리

노드를 나무 형태로 연결한 구조를 트리라고 합니다.
트리에 있는 각각의 요소는 노드입니다.
위 사진에서처럼 노드는 부모, 자식 형태로 이어집니다.

root: 트리의 시작 부분입니다. 뿌리를 통해 들어가서 트리를 탐색합니다.
leaf: 자식이 딸려있지 않은 부분입니다.
edge: 두 노드를 연결하는 선입니다. 뿌리로부터의 간선의 수에 따라 level을 나눕니다.

힙

힙은 빠른 연산을 하기위해 완전이진트리를 기반으로 한 자료구조입니다.

최대 힙 (max heap) : 부모노드가 자식노드보다 큰 경우
최소 힙 (min heap) : 부모노드가 자식노드보다 작은 경우

최대 힙을 사용할 지 최소 힙을 사용할지는 어플리케이션에 따라 달라지게 됩니다.

트리의 높이 : 루트에서부터 가장 먼 잎까지 가는 동안 거치는 엣지의 개수

최대 힙에서 노드의 개수 n, level, height, $log_2(n+1) -1$은 위 사진과 같이 나타납니다.
$log_2(n+1) -1$ 은 height와 일치하므로, 트리에 요소가 몇 개 있는지 알면 트리의 높이를 계산할 수 있습니다.