자료구조 : 이진 트리(Binary Tree) / 이진 탐색 트리(Binary Search Tree)

이진 트리(Binary Tree)

• 사전적 정의 : 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조의 하나로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다.
• 이진 트리의 모든 노드는 왼쪽 자식 노드와 오른쪽 자식 노드만 가진다.
• 모든 노드의 차수가 최대 2

이진 트리 형태

이진 트리의 순환적 구성

• 노드의 왼쪽 자식 노드를 루트로 하는 왼쪽 서브트리도 이진 트리
• 노드의 오른쪽 자식 노드를 루트로 하는 오른쪽 서브 트리도 이진 트리

이진 트리의 순환적 구조

이진 트리의 특성

• N개의 노드를 가진 이진 트리는 항상 (N - 1)개의 간선을 가진다. => 루트를 제외한 (N - 1)개의 노드가 부모 노드와 연결되는 하나의 간선을 가지기 때문이다.
• 높이 h의 이진 트리는 최소 h + 1개 최대 2^(h+1) - 1개의 노드를 가진다. => 이진 트리의 높이가 h가 되려면 한 레벨에 최소한 한 개의 노드가 있어야 하므로 높이가 h인 이진 트리의 최소 노드의 개수는 (h + 1) => 하나의 노드는 최대 2개의 자식 노드를 가질 수 있으므로 레벨 i에서의 노드의 최대 개수는 2^i개 이므로 높이가 h인 이진 트리 전체의 노드 개수는 ∑2^i = 2^(h+1) - 1개

 

포화 이진 트리

• 모든 레벨에 노드가 포화 상태로 차 있는 이진 트리
• 높이가 h일 때, 최대의 노드 개수인 (2^(h+1) - 1)개의 노드를 가진 이진 트리
• 루트를 1번으로 하여 2^(h+1) - 1까지 정해진 위치에 대한 노드 번호를 가진다. 

포화 이진 트리의 형태

 

완전 이진 트리

• 높이가 h이고 노드 수가 n개 일 때 (단, h + 1 <= n <= 2^(h+1) - 1),
• 레벨 h - 1까지는 Full Binary Tree이고, 레벨 h에서 왼쪽부터 노드가 순서대로 채워진 이진 트리
• 즉, 포화 이진 트리에서 리프 노드를 차례로 지우면서 얻어지는 모든 트리 구조들이 완전 이진 트리라고 할 수 있다.

완전 이진 트리의 형태 (리프 노드가 부족할 수 있음)

편향 이진 트리

• 높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만을 가진 이진 트리
• 왼쪽 편향 이진 트리 : 모든 노드가 왼쪽 자식 노드만을 가진 편향 이진 트리
• 오른쪽 편향 이진 트리 : 모든 노드가 오른쪽 자식 노드만을 가진 편향 이진 트리

편향 이진 트리의 형태

이진트리의 순회

전위 순회(Preorder Traversal)

• 수행 방법 : 현재 노드 n에서 명령 수행 -> 왼쪽 서브트리로 이동 -> 오른쪽 서브트리로 이동
• 즉, {부모 -> 왼쪽자식 -> 오른쪽자식}
• 언제나 부모가 자식들보다 순위가 높음
• 어떠한 부모-자식 노드 쌍을 선택하든, 부모가 자식보다 먼저 출력(처리)된다는 특성이 있음

Preorder Traversal : A -> B -> D -> H -> E -> I -> J -> C -> F -> G -> K

중위순회(Inorder Traversal)

• 수행 방법 : 현재 노드 n의 왼쪽 서브트리로 이동 -> 현재 노드 n에서 명령 수행 -> 현재 노드 n의 오른쪽 서브트리로 이동
• 즉, {왼쪽 자식 -> 부모 -> 오른쪽자식}
• 부모 입장에서 왼쪽자식 처리 후 자기자신(부모노드) 처리
• 아직 방문하지 않은 왼쪽자식이 있으면, 부모보다 먼저 처리
• 어떠한 부모-자식 쌍을 선택해도, 왼쪽자식이 부모보다 먼저 출력(처리)되는 특성이 있음
• 왼쪽 서브트리가 부모보다 먼저 출력(처리)됨

Inorder Traversal : H -> D -> B -> I -> E -> J -> A -> F -> C -> G -> K

후위 순회(Postorder Traversal)

• 수행 방법 : 현재 노드 n의 왼쪽 서브트리로 이동 -> 현재 노드 n의 오른쪽 서브트리로 이동 -> 현재 노드 n에서 명령 수행
• 즉, {왼쪽 자식 -> 오른쪽 자식 -> 부모}
• 왼쪽자식, 오른쪽 자식 모두 처리한 뒤, 마지막에 부모 처리

Postorder Traversal : H -> D -> I -> J -> E -> B -> F -> K -> G -> C -> A

이진 탐색 트리(Binary Search Tree)

: 이진 트리에 탐색을 위한 조건을 추가하여 정의한 자료구조

 

이진 탐색 트리의 정의

1. 모든 원소는 서로 다른 유일한 키를 갖는다.
2. 왼쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다 작다.
3. 오른쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다 크다.
4. 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리이다.

이진 탐색 트리 구조

이진 탐색 트리의 특성

• 평균 O(logN)의 시간 복잡도를 가지며, 트리가 한쪽으로 치우친 최악의 경우에는 O(N)의 시간 복잡도를 가진다.