트리 (Tree)

트리 (Tree) 관련 용어

• 노드 : 데이터를 담는 가장 작은 단위
• 간선(Edge) : 노드와 노드를 연결하는 선
• 루트 노드 : 트리에서 최상위에 있는 노드
• 터미널 노드 : 자식노드가 없는 노드
• 인터널 노드 : 터미널 노드를 제외한 노드

트리의 레벨과 높이

트리는 자식 노드로 내려갈수록 레벨이 증가한다.
루트 노드의 레벨은 1이며, 아래로 내려갈수록 레벨이 점점 높아진다. 이때 트리에서 가장 높은 레벨을 높이라고 한다.

트리 순회

전위 순회

• 방문 순서 : 루트 → 왼쪽 서브트리 → 오른쪽 서브트리
• 1 → 2 → 4 → 5 → 3 → 6 → 7

중위 순회

• 방문 순서 : 왼쪽 서브트리 → 루트 → 오른쪽 서브트리
• 4 → 2 → 5 → 1 → 6 → 3 → 7

후위 순회

• 방문 순서 : 왼쪽 서브트리 → 오른쪽 서브트리 → 루트
• 4 → 5 → 2 → 6 → 7 → 3 → 1

이진 트리 (Binary Tree)

이진 트리는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리 구조이다.

즉, 자식 노드의 수가 0개, 1개, 또는 2개인 노드들로만 구성된 트리를 말한다.
만약 하나의 노드가 자식 노드를 3개 이상 가지고 있다면, 그 구조는 이진 트리라고 할 수 없다.

이진 트리의 종류

포화 이진 트리

트리의 최대 레벨에 있는 모든 터미널 노드가 꽉 찬 트리를 포화 이진 트리라고 한다.

완전 이진 트리

최대 레벨을 제외한 나머지 레벨에는 모두 채워져 있어야 하고 최대 레벨의 노드들은 왼쪽부터 채워진 트리를 완전 이진 트리라고 한다.

이진 탐색 트리 (Binary Search Tree)

이진 트리에서 몇 가지 규칙만 추가하면 이진 탐색 트리가 된다.

이진 탐색 트리의 규칙

1. 중복된 노드가 없어야 한다.
2. 특정 노드의 왼쪽 자식 노드는 그 노드의 값보다 작은 값들로만 이루어진 노드가 있어야 한다.
3. 특정 노드의 오른쪽 자식 노드는 그 노드의 값보다 큰 값으로만 이루어진 노드가 있어야 한다.
4. 자식 트리(노드)에도 위의 모든 규칙이 적용되어야 한다.