트리란?

Tree는 graph의 특수한 경우로서 다음과 같은 특징을 가진다.

트리는 각 노드사이에는 오직 한 개의 간선으로 이루어져 있으며(연결성), 각 노드를 연결했는 때 순환하는 경로가 존재해서는 안된다.(비순환성)

Tree의 용어를 살펴보면 다음과 같다.

• Root : 모든 노드의 조상이자 트리내에서 가장 최상단에 위치하며 오직 1개 존재한다.
• 비단말 : 자식이 존재하는 노드
• 단말 : 자식이 없고 마지막 비단말 노드 아래에 위치한 노드

뿐만아니라 K-ary tree, 즉 K진 트리라고 불리우는 모든 node의 자식이 k개 이하인 tree가 있다.

• k=2 => 이진트리
• k=4 => 4진트리
• k=8 => 8진트리

이진트리의 종류

포화 이진트리

• 말 그래도 포화다.
• 즉, 모든 비단말 노드(단말제외)가 2개의 노드를 가진다.
• 모든 단말노드는 동일한 level 즉, 같은 높이에 있다.

total of nodes N = 2^0 + 2^1 + 2^2 + ... + 2^h = 2^(h+1) - 1
위의 식을 계산하면 아래와 같다.
h = log(N+1) - 1 = log N

완전 이진트리

• 트리의 높이를 h라 가정하였을 때 h-1높이까지는 포화 이진트리이다.
• 즉, h-1높이까지는 모든 노드들이 꽉 채워진다.
• 포화 이진트리와 차이점은 마지막 h높이에는 모든 노드들이 꽉 차있는 것은 아니다.
• 그래서 마지막 레벨이 가질 수 있는 노드의 개수는 1개 이상 2^h - 1개이다.

2^h - 1 < N <= 2^(h+1) - 1

2^h <= N < 2^(h+1)
h <= log N < h+1
h = Math.floor(log N) = log N