트리, 이진 탐색 트리 (Binary Search Tree)
- 탐색 시간
- 평균: $O(log N)$
- 최악: $O(N)$
- 요소 추가/삭제
- 평균: $O(log N)$
- 최악: $O(N)$
트리 (Tree)
트리(Tree)형 자료구조는 비선형 계층 관계(부모-자식 관계) 자료구조입니다.
각 노드(Node)는 방향이 있는 간선(Edge)로 연결되며, 루트(Root) 노드에서 시작해 노드(Node)를 확장해 가는 자료구조입니다.
마치 이 모양이 나무가 가지를 뻗어가는 모양과 같다고 하여 트리(Tree) 자료구조 입니다.
트리 관련 용어
| 용어 | 설명 |
|---|---|
| 노드 (Node) | 트리의 기본 요소로, 각 노드는 데이터와 자식을 가리키는 포인터를 가집니다. |
| 루트 (Root) | 트리의 시작 지점으로, 들어오는 간선이 없는 유일한 노드입니다. |
| 간선 (Edge) | 두 노드를 연결하는 개념. 두 노드를 연결하는 선으로 표현합니다. |
| 경로 (Path) | 어떤 노드에서 다른 노드로 향하는, 간선으로 연결된 노드의 순서입니다. |
| 말단 (Leaf) | 더 이상 뻗어 나갈 경로가 없는 노드로, 자식이 없는 노드를 말합니다. |
| 부모 (Parent) | 어떤 노드에서 간선으로 연결된 위쪽 노드를 말합니다. 트리의 모든 노드는 1개의 부모 노드만을 가집니다. |
| 자식 (Children) | 어떤 노드에서 간선으로 연결된 아래쪽 노드를 말합니다. 자식 노드는 여러개 가질 수 있습니다. |
| 형제 (Sibling) | 같은 부모를 가진 노드를 말합니다. |
| 조상 (Ancestor) | 어떤 노드에서 위쪽으로 연결된 모든 노드를 말합니다. |
| 자손 (Descendant) | 어떤 노드에서 아래쪽으로 연결된 모든 노드를 말합니다. |
| 레벨 (Level) | 루트에서부터 어떤 노드까지의 경로에 있는 간선의 수를 말합니다. |
| 높이 (Height) | 루트에서 가장 말단(Leaf)까지의 가장 긴 경로의 간선 수를 말합니다. |
| 깊이 (Depth) | 루트에서 특정 노드까지의 간선 수를 말합니다. |
| 차수 (Degree) | 노드가 갖는 자식의 수를 말합니다. 이때, 트리의 모든 노드의 차수라 n 이하인 트리를 n진 트리라고 합니다. |
이진 트리
이진 트리(binary tree)는 각 노드가 최대 2개의 자식(왼쪽 자식과 오른쪽 자식)을 가질 수 있는 트리입니다.
이진 트리의 형태로 균형 이진 트리, 완전 이진 트리, 포화 이진 트리 등이 있습니다.
이진 트리의 종류
편향 이진 트리 (Skewed Binary Tree)
모든 노드가 한쪽 방향의 자식만을 가지는 이진 트리를 말합니다.
이 편향 이진 트리는 좌편향 이진 트리(left skewed binary tree)와 우편향 이진 트리(right skewed binary tree)가 있습니다.
이런 편향 이진트리는 최악의 탐색/삽입/삭제의 원인이 됩니다. ($O(N)$)
정 이진 트리 (Full Binary Tree)
모든 노드에 대해 자식의 개수가 정확히 2개 혹은 0개(Full or Empty) 를 가지는 경우를 말합니다.
균형 이진 트리 (Balanced Binary Tree)
모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 일정한 범위 내에 있는 이진 탐색 트리입니다.
이렇게 하면 트리의 높이가 최소화되어 최악의 경우에도 탐색, 삽입, 삭제 등의 연산이 $O(log N)$ 시간 복잡도를 가지게 됩니다.
(예를 들어, AVL 트리의 경우 높이 차이가 1 이하가 되도록 유지하는 트리입니다.)
완전 이진 트리 (Complete Binary Tree)
마지막 레벨을 제외한 모든 레벨이 완전이 채워져있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있는 트리입니다.
포화 이진 트리 (Perfect Binary Tree)
말단(Leaf) 노드를 제외한 모든 노드들이 정확히(Perfect) 두 개(차수)의 자식 노드를 가지고 모든 말단(Leaf) 노드들이 완벽히(Perfect) 같은 레벨을 가지는 트리입니다.
이진 트리 탐색
이진 트리의 순회 방법에는 여러 가지가 있으며, 각각의 방법은 노드를 방문하는 순서에 따라 구분됩니다.
전위 순회 (Preorder)
전위 순회는 현재 노드를 먼저(Pre) 탐색하는 방법을 말합니다.
- 현재 노드
- 왼쪽 서브트리
- 오른쪽 서브트리
중위 순회 (Inorder)
중위 순회는 현재 노드를 중간에 탐색하며, 왼쪽 자식을 먼저 탐색하는 방법을 말합니다.
- 왼쪽 서브트리
- 현재 노드
- 오른쪽 서브트리
후위 순회 (Postorder)
후위 순회는 현재 노드를 나중(Post)에 탐색하는 방법을 말합니다.
- 왼쪽 서브트리
- 오른쪽 서브트리
- 현재 노드
너비 우선 탐색 (Breadth-First Search, BFS)
너비 우선 탐색은 낮은 레벨에서 시작해 왼쪽에서 오른쪽 방향으로 탐색하고,
한 레벨에서 탐색이 끝나면 다음 레벨로 넘어가 같은 탐색을 계속하는 방법입니다.
일반적으로 큐(Queue)를 사용해서 구현하게 됩니다.
깊이 우선 탐색 (Depth-First Search, DFS)
깊이 우선 탐색은 말단(Leaf)까지 내려가면서 탐색하는 것을 최우선으로 하는 탐색 방법입니다.
말단(Leaf)에 도착해 더 이상 검색을 진행할 곳이 없는 경우, 부모에게 돌아가 남아있는 자식 노드로 깊이 우선 탐색을 진행합니다.
일반적으로 스택(Stack)을 사용하여 구현합니다.
이진 탐색 트리 (Binary Search Tree)
이진 탐색 트리란, 다음 조건을 만족하는 트리입니다.
- 어떤 노드를 기준으로 왼쪽 서브 트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 구성되어야 합니다.
- 어떤 노드를 기준으로 오른쪽 서브 트리에는 그 노드의 값보다 큰 값들을 지는 노드들로 구성되어야 합니다.
- 같은 값을 갖는 노드는 없어야 합니다.
이진 탐색 트리는 탐색을 빠르게 하기 위해 정렬된 노드들을 가지는 트리입니다.
한 노드를 기준으로 왼쪽 자식에는 작은 값을 가진 노드를 넣고, 오른쪽 자식에는 큰 값을 가진 노드를 넣습니다.
이렇게 구성한다면, 탐색을 진행할 때 어떤 노드를 기준으로 작은 값을 찾는다면 왼쪽 자식으로, 큰 값을 찾는다면 오른쪽 자식으로 탐색을 진행할 수 있게 됩니다.
따라서, 이진 탐색 트리는 평균 $O(log N)$의 탐색 시간을 가질 수 있게 됩니다.
또한, 이진 탐색 트리를 중위 순회(Inorder)하면 오름차순의 값을 얻을 수 있습니다.
위 트리를 각각의 탐색 방법으로 탐색한 결과
- 전위 순회: 7, 3, 2, 1, 5, 4, 6, 11, 9, 8, 10, 12
- 중위 순회: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 (오름차순 정렬)
- 후위 순회: 1, 2, 4, 6, 5, 3, 8, 10, 9, 12, 11, 7
- 너비 우선 탐색: 7, 3, 11, 2, 5, 9, 12, 1, 4, 6, 8, 10
- 깊이 우선 탐색: 7, 3, 2, 1, 5, 4, 6, 11, 9, 8, 10, 12 (전위 순회와 같음)