3. 트리
1. 정의
자료구조 트리(Tree)는 그래프의 종류 중 하니로, 계층관계 형태를 가지고 있으며 회로가 없는 그래프이다.
여기서 그래프란, 각각의 데이터가 Node(또는 Vertex)의 형태로 존재하면서 연결 관계로 이루어져 있는 것을 말하며, 이전 언급된 연결형 리스트도 그래프의 일종이다.
그리고 회로란, 단어가 의미하는 그대로 순환하는 구조를 가진 형태를 의미하며, 대표적으로 원형 링크드 리스트의 형태를 띈다. 다른 말로 사이클, 또는 순환 자료구조라고도 불린다.
트리의 노드는 자신의 위로 부모 노드가 하나 존재하며 아래로 한개 또는 여러개의 자식이 존재할 수도 있다(없을 수도 있다).
| 용어 | 설명 |
|---|---|
| 루트 노드(Root node) | 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다. |
| 단말/리프 노드(Leaf node) | 자식이 없는 노드, 트리에 하나 이상 존재한다. |
| 내부 노드 | 루트 노드, 단말 노드 모두 아닌 중간에 존재하는 노드. |
| 노드의 레벨 | 루트 노드에서 해당 노드까지 연결된 간선 수의 합, 루트의 경우 레벨 0. |
| 트리의 높이 | 루트 노드로부터 가장 깊은 레벨까지의 노드의 거리, 해당 노드의 레벨과 동일함. |
2. 이진 트리 (binary tree)
이진 트리는 트리의 종류 중 하나로, 자식 노드의 개수를 최대 2개로 제한하는 트리이다. 자식은 왼쪽 자식과 오른쪽 자식으로 구분된다.
- 포화 이진 트리 (perfect binary tree)
모든 단말 노드가 같은 레벨에 존재하고, 단말 노드가 아닌 모든 노드는 자식을 2개씩 가진다.
특정 높이의 트리에서 빈 공간 없이 데이터를 가득 채운다면 포화 이진트리가 되며, 포화 이진 트리는 정 이진 트리(full binary tree: 모든 트리의 자식이 0개 또는 2개)에 포함된다.
- 완전 이진 트리 (conplete binary tree)
모든 단말 노드의 레벨 차이가 1을 넘지 않고, 단말 노드가 아닌 노드는 오른쪽 자식이 존재하면 완전 이진 트리이다.
다시 말해, 데이터를 레벨 순서로 왼쪽부터 순차적으로 채워나가면 완전 이진 트리가 된다.
완전 이진 트리는 힙 자료구조를 구현할 때 이용되며, 이러한 힙 트리는 우선순위 큐를 구현할 때 사용된다.
완전 이진 트리의 특징으로 아래와 같이 각 노드가 인덱싱되면 부모 노드의 인덱스가 $n$ 일 때, 자식 노드는 $2n$, $2n + 1$ 의 인덱스에 존재하게 된다.
이러한 특성을 살려서 0번 인덱스를 비운 배열 자료형에 완전 이진 트리를 구현하기에 용이하다.
3. 이진 탐색 트리 (binary search tree)
이진 탐색 트리는 이진 탐색 알고리즘 을 사용하여 데이터를 빠르게 탐색이 가능하도록 구성한 이진 트리 자료구조이다.
이진 트리 자료구조를 바탕으로 이진 탐색 알고리즘을 사용하기 위해 삽입 및 삭제 시 데이터의 정렬 상태를 유지한다.
따라서 삽입 및 삭제는 배열과 연결형 리스트보다 느리지만, 특정 데이터를 탐색할 때 두 자료구조 대비 매우 높은 효율을 보여준다.
| 이진 탐색 트리 | ||
|---|---|---|
| 데이터 작업 | 시간복잡도 | |
| 접근 | $O(log(n))$ | |
| 탐색 | $O(log(n))$ | |
| 삽입 | $O(log(n))$ | |
| 삭제 | $O(log(n))$ |
C++ 의 표준 탬플릿 라이브러리(STL)에는 map 과 set 으로 구현되어 있는데, 이 두 컨테이너는 이진 탐색 트리의 단점을 보완한 레드 블랙 트리(Red Black tree) 자료구조를 사용한다.
일반적인 이진 탐색 트리의 기본 알고리즘을 따르면, 최악의 경우 탐색, 삽입, 삭제에 $O(log(n))$ 의 시간이 아닌 $O(n)$ 의 시간이 소요되게 된다.
예를 들어, 이미 정렬된 데이터를 순서대로 이진 탐색 트리에 넣는다고 가정해 보자. 그러면 아래 그림과 같이 트리가 구성될 것이다.
이 경우 트리가 연결형 리스트처럼 구현되기에 $O(n)$ 의 시간이 소요되게 된다.
이러한 단점을 보완하기 위해 데이터의 삽입 시 트리의 형태를 균형되게 재구성하는 작업을 추가로 진행하는 것이 자가 균형 이진 탐색 트리(Self-Balanced BST)이다.
그 종류로 레드 블랙 트리와 AVL 트리가 있는데, 실제 알고리즘 속도가 레드 블랙 트리가 더 빨라서 대부분 레드 블랙 트리를 이용한다.
또한 데이터의 순회에는 전위 순회, 중위 순회, 후위 순회로 3가지가 있는데, 이진 탐색 트리는 이 중 중위 순회 방식을 사용하여 순회가 이루어진다.
반복자(iterator)가 선행자 또는 후속자로 이동할 때 중위 순회를 기준으로 이동하게 된다.
| 순회 종류 | 설명 |
|---|---|
| 전위 순회 | 부모가 우선순위가 가장 높음. |
| 중위 순회 | 왼쪽 자식이 우선순위가 가장 높음, 부모가 중간의 우선순위임. |
| 후위 순회 | 자식이 왼쪽부터 우선순위를 가지며 부모의 우선순위가 가장 낮음. |
이진 탐색 트리는 이진 탐색 알고리즘을 사용하는 특성상 정렬을 유지하는 것이 매우 중요하다.
따라서 데이터가 정렬되기 위해 중복된 데이터의 삽입을 혀용하지 않으며, 시도될 경우 무시된다.
특수한 경우로 중복을 허용하는 BST 컨테이너 multimap 과 multiset 이 존재하긴 하지만, 해당 컨테이너들은 중복된 데이터를 트리 내부에 중복 데이터끼리의 리스트를 구현해 저장하므로 탐색 속도에서의 이점이 사라진다.
물론 전체를 리스트 또는 배열로 구현하는 것 보다는 탐색이 빠르지만, 되도록이면 중복된 데이터 삽입을 피하는 편이다.
또한 중복 데이터 삽입 시도 자체가 무시되므로, 데이터 존재 유무를 확인 후 삽입하는 것이 데이터 관리 측면에서 안정적이다.
4. BST 함수 알고리즘
- insert, search
- 루트 노드부터 시작해서 삽입될 데이터를 비교한다.
- 삽입 데이터가 노드 데이터보다 클 경우 오른쪽, 작을 경우 왼쪽 자식으로 이동한다.
- 단말 노드에 도착할 때 까지 반복한다.
- 단말 노드에 도달한 경우 비교 후 노드를 생성해 삽입한다.
- 같은 값을 만났을 경우 삽입을 취소하고 알고리즘을 중단한다.
search 알고리즘으 경우 같은 값을 만났을 때가 탐색 성공을 의미하므로 이를 반환하고, 단말 노드에 도달한 경우 탐색 실패이므로 end iterator를 반환한다.
- iterator ++, –
선행자(–)와 후속자(++) 알고리즘은 좌우 방향을 제외하고 모두 같은 양상을 띄므로 후속자를 기준으로 설명한다.
- 오른쪽 자식 노드가 있는 경우
- 해당 노드로 이동 후 왼쪽 자식 노드가 없을 때까지 왼쪽 자식 노드로 이동한다.
- 오른쪽 자식 노드가 없는 경우
- 부모 노드로 이동 후
- 이동한 부모 노드가 왼쪽 자식일 경우 해당 부모 노드로 이동한다.
- 이동한 부모 노드가 모두 오른쪽 자식이었다면(루트 노드에 도달했다면)
- 최초 이동을 시작한 노드가 트리의 마지막 노드였으므로 end iterator 상태가 된다.
- erase
- 단말 노드의 경우
- 노드와 연결관계를 삭제한다.
- 자식이 하나 존재할 경우
- 하나 있는 자식이 삭제될 노드의 자리를 대체한다.
- 자식이 두개 있는 경우
- 중위 순회 기준 선행자 또는 후속자 노드가 자리를 대체한다.
- 대체 후 원래 선행자/후속자가 존재했던 노드 위치를 삭제한다.
3번 케이스의 경우 정렬 상태 유지를 위해 선행자 또는 후속자가 자리를 대체하게 된다.
그 후, 원래 선행자/후속자가 존재했던 자리가 삭제되는데, 이 때 선행자/후속자는 각각 오른쪽/왼쪽 자식의 끝에 존재했기 때문에 자식이 존재하지 않는 단말 노드였거나 하나 존재하는 노드이다.
따라서 이후 1 또는 2의 케이스로 알고리즘을 수행하면 된다.