Binary Tree

각 노드가 자식을 최대 두 개까지만 갖는 트리다. 두 자식은 왼쪽·오른쪽으로 구분되며, 자식이 하나뿐이어도 그것이 왼쪽인지 오른쪽인지가 구조상 의미를 갖는다.

모양에 따른 구분

• full: 모든 노드가 자식을 0개 또는 2개 갖는다
• complete: 마지막 레벨을 뺀 모든 레벨이 꽉 차 있고, 마지막 레벨의 노드는 왼쪽부터 빈틈없이 채워져 있다
• perfect: 모든 내부 노드가 자식 2개를 갖고 모든 잎이 같은 깊이에 있다

complete binary tree 는 노드를 배열에 순서대로 담을 수 있다. 인덱스 $i$ 노드의 자식이 $2i+1$, $2i+2$ 로 계산되므로 포인터 없이 배열만으로 트리를 표현할 수 있고, Heap 이 이 성질을 쓴다.

순회

노드를 한 번씩 방문하는 순서는 자기 자신을 언제 방문하느냐로 갈린다. 자세한 내용은 Tree Traversal 에 있다.

• pre-order: 자신 → 왼쪽 → 오른쪽
• Inorder Search: 왼쪽 → 자신 → 오른쪽
• post-order: 왼쪽 → 오른쪽 → 자신

세 가지 모두 DFS 이고, 방문 시점만 다르다.

Binary Search Tree

“왼쪽 서브트리의 모든 값 < 자신 < 오른쪽 서브트리의 모든 값” 이라는 규칙을 얹은 것이 binary search tree 다. 이 규칙 덕분에 탐색·삽입·삭제가 트리 높이에 비례하는 시간에 끝나고, 중위 순회 결과가 정렬된 순서로 나온다. 같은 값을 두 번 넣지 않는 것이 보통이라 중복을 허용하지 않는다고 설명한다.

다만 정렬된 데이터를 순서대로 넣으면 한쪽으로만 자라 연결 리스트처럼 되고, 높이가 $O(n)$ 이 되어 이점이 사라진다. 이를 막으려고 삽입·삭제 때 균형을 맞추는 AVL 트리, red-black 트리 같은 변형을 쓴다.