Binary Tree

Full binary tree

•     단말 노드가 아닌 모든 노드가 2개의 자식을 가진 트리

 

Perfect binary tree

•     모든 단말 노드의 깊이가 같은 full binary tree

 

Complete binary tree

•     Perfect binary tree에서 끝 부분을 제외하고 다른 것이 남아 있는 트리이다. Perfect binary tree의 각 노드에 부모에서 자식으로, 외쪽에서 오른쪽으로 번호를 매겼을 때 perfect binary tree는 아니지만 그 번호가 연속되어 있는 경우이다. 

Balanced binary tree

•     모든 단말 노드의 깊이 차이가 많아야 1인 tree이다. Balanced binary tree는 예측 가능한 깊이 (predictable depth)를 가진다. 노드 개수를 n이라고 하면 길이는 log₂ⁿ 이 된다.

 

Order of tree traversal

•     In-order: 왼쪽 자식 -> 나 -> 오른쪽 자식

•     Pre-order: 나 -> 왼쪽 자식 -> 오른쪽 자식

•     Post-order: 왼쪽 자식 -> 오른쪽 자식 -> 나

•     Level-order: Root -> depth 1인 노드들 -> depth 2인 노드들 -> ...

 

자료구조

•     Binary tree는 배열(array)로 표현할 경우 따로 포인터를 가지고 있지 않아도 부모, 자식에 대한 indexing이 가능하다는 장점이 있다. 

•     Root를 0부터 시작하느냐 1부터 시작하느냐에 따라 다른데,

•     (위 그림에서 처럼) root가 0부터 시작하면, parent index = (my index – 1) / 2, left child index = my index * 2 + 1, right child index = my index * 2 + 2 가 된다. 

• Root가 1부터 시작하면, parent index = my index / 2, left child index = my index * 2, right child index = my index * 2 + 1 가 된다.