트리(Tree)는 계층적인 구조를 표현하는 비선형 자료구조로 노드(Node)와 간선(Edge)으로 이루어져 있으며, 루트(Root) 노드에서부터 여러 개의 자식 노드들이 분기(Branch)되어 나가는 형태로 구성된다.
대표적인 트리의 종류는 다음과 같다.
- 삼항 트리(Ternary Tree) : 각 노드가 최대 세 개의 자식 노드를 갖는 구조
- 이진 트리(Binary Tree) : 각 노드가 최대 두 개의 자식 노드를 갖는 구조
이진 검색 트리(Binary Serach Tree)
- 최대 두 개의 자식을 가지는 구조
- 노드의 왼쪽 자식의 값이 자신의 값 이하이며,오른쪽 자식의 값은 자신의 값 이상이다.
- 이진 검색 트리의 장점 가운데 하나로 룩업 연산(특정 노드의 위치를 알아내는 연산)을 빠르고
간단하게 처리할 수 있다. - 한 단계 올라갈때마다 절반이 줄어들기 때문에, 시간 복잡도는 O(log n)이다.
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
위의 이진 검색 트리는 루트 노드의 값이 8이고, 왼쪽 서브 트리는 노드의 값이 작은 값을,
오른쪽 서브 트리는 노드의 값이 큰 값들을 가지도록 구성되어있다.
14의 값을 갖는 노드를 찾을 때, 2lv에서 3보다 10이 크기 때문에 오른쪽으로 가면 해당 값을 찾을 수 있다.밸런스(Blance)
왼쪽 오른쪽의 자식이 크게 치우치지 않고 균일한 구조를 갖는다.
AVL 트리(Adelson-Velsky and Landis Tree)
AVL 트리는 높이 균형을 맞추기 위해 삽입과 삭제 연산 시 자동으로 회전하는 이진 검색 트리이다.
AVL 트리의 균형 인자(balance factor)는 노드의 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이의 차이로
이 규형 인자의 절댓값이 1보다 크면 회전 연산을 수행하여 균형을 맞춘다.
9
/ \
4 15
/ \ / \
2 6 12 18
/ \
5 14
AVL 트리는 높이 균형을 유지하기 위해 회전 연산을 수행하므로 노드의 균형 인자가
-1, 0, 1인 경우에는 균형을 유지하지만 균형 인자가 2이상이거나 -2이하인 경우에는
회전 연산을 수행하여 균형을 맞춘다.
위 AVL 트리는 루트 노드 9를 중심으로 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이가
각각 2와 3으로 차이가 1이상 나지 않으므로 균형을 유지하고 있다.레드-블랙 트리(Red-Black Tree)
레드-블랙 트리는 자식 노드가 있는 노드를 검은색으로, 자식 노드가 없는 노드를 빨간색으로 표시하는 이진 검색 트리이다.
레드-블랙 트리는 균형 인자 대신 색상을 사용해 균형을 맞추며 각 노드의 색상은 일정한 규칙에 따라 지정된다.
11B
/ \
7R 15B
/ \ / \
5B 9B 13R 20R
/ \ /
8R 10R 18B
위 레드-블랙 트리의 루트 노드 11은 블랙으로 표시되어있다.
이 때 블랙 노드의 자식 노드는 레드나 블랙일 수 있지만, 레드 노드의 자식 노드는 반드시 블랙이어야한다.B 트리 (B-Tree)
B트리는 데이터를 저장하는 노드(블록)의 개수를 최소화하고, 각 노드의 균형을 유지하면서 데이터를 탐색할 수 있는 트리이다.
B트리는 여러 개의 키와 값으로 이루어진 레코드를 블록으로 관리하는데 이진 검색 트리와 달리 B트리는 각 노드가 하나 이상의 키를 가질 수 있으며 키와 자식 노드를 하나의 블록으로 관리한다.
(B트리는 대용량 데이터 처리나 데이터베이스 인덱스 등에서 사용된다.)
8 18 35
/ | | | \
2 5 7 20 21
/| | | \ | \
1 3 4 6 7.5 22 23
각 노드는 여러 개의 자식을 가지며, 자식 노드들은 정렬된 순서로 저장된다.
위 B트리에서 각 노드는 노드에 저장된 키의 개수와 자식 노드의 개수에 따라 종류를 구분한다.
예시로 위의 B트리에서 루트 노드는 3개의 키와 4개의 자식 노드를 가지므로 3차 B트리이고
B 트리는 노드에 저장된 키의 개수가 가득 차면 분할 연상을 수행하기 때문에 현재 분할 연산이 필요한 상태이다.완전 이진 트리(Complete binary tree)
완전 이진 트리는 마지막 레벨을 제외하고 모든 레벨이 노드로 꽉 차 있는 이진 트리를 말한다.
마지막 레벨은 왼쪽부터 노드를 채우는 형태로 구성된다.
모든 노드가 2개의 자식 노드를 가지거나, 마지막 레벨의 모든 노드가 왼쪽부터 차례대로 채워진 이진 트리를 완전 이진 트리라고 하고,
완전 이진 트리는 배열을 사용해 각 노드를 저장하면 메모리 사용을 최적화할 수 있다.
(완전 이진 트리는 이진 검색 트리, 힙(Heap) 등에서 사용된다.)
1
/ \
2 3
/ \ /
4 5 6
완전 이진 트리는 모든 레벨이 노드로 꽉 차 있기 때문에 마지막 레벨은 왼쪽부터 채워져 있다.
따라서 이진 트리의 노드들이 배열로 구성된 경우, 마지막 노드의 인덱스를 찾기가 쉬워지며,
배열을 이용한 탐색과 삽입 연산 등에 용이하다.이진 힙 (Binary Heaps)
Binary Heaps은 완전 이진 트리를 기반으로 하는 자료구조 중 하나로, 특정한 조건을 만족하는 트리이다.
힙은 여러 개의 값 중에서 최소값 또는 최대값을 빠르게 찾아내는 연산을 지원한다.
Binary Heaps은 다음 두 가지 조건을 만족해야한다.
- 완전 이진 트리(Complete Binary Tree) 구조를 가져야한다.
- 모든 노드에 저장된 값은 해당 노드의 자식 노드에 저장된 값 보다 작아야한다.
(Min-Heap인 경우)
즉, 모든 레벨에서 노드들이 왼쪽에서 오른쪽으로 채워져 있으며, 부모 노드의 값은 자식 노드의 값보다 작은 값을 가진다.
Min-Heap의 경우 루트 노드의 값이 항상 최소값을 갖는다.
Binary Heaps은 삽입, 삭제, 최소값 조회 등의 연산을 O(log n)의 시간 복잡도로 수행할 수 있고 이런 특성 때문에 Binary Heap은
우선 순위 큐(Priority Queue)와 같은 자료구조를 구현하는데 많이 사용된다.
1
/ \
3 5
/ \ / \
4 7 6 8
위 트리는 완전 이진 트리이면서,
모든 노드의 값이 해당 노드의 자식 노드에 값보다 작기 때문에 Min-Heap 조건을 만족한다.
이 때 이 트리에 새로운 값을 추가하게 되면 완전 이진 트리의 조건을 유지하기 위해
가장 왼쪽에 있는 비어있는 노드에 값을 채워 넣는다.
1
/ \
3 5
/ \ / \
4 7 6 8
/
2
완전 이진 트리의 조건은 만족했으나, 이진 힙의 조건을 만족하지 않았기 때문에
이진 힙의 조건을 만족할 때까지 노드를 비교하며 교환하는 연산을 수행한다.
1
/ \
2 5
/ \ / \
4 7 6 8
/
3
완전 이진 트리와, 이진 힙을 모두 만족하는 구조를 갖게되었다.Min-Heap 혹은 Max-Heap의 루트 값을 반환하게 될 경우 힙의 규칙을 유지하기 위해 루트 노드를 제거하고, 힙의 마지막 노드를 루트로 이동시킨 후, 새로운 루트 노드를 기준으로 다시 힙을 재구성하는 과정을 갖는데 이를 힙의 재구성 또는 힙의 재배치라고 한다.
힙의 재구성은 말단 노드를 루트로 가져왔기 때문에 Min-Heap 혹은 Max-Heap의 조건을 만족하지 못한 상태의 이진 힙을 노드간 비교를 통해 다시 정렬하는 과정을 말한다.
3 5
/ \ / \
5 8 -> 7 8
/ \ / \ / \ /
7 9 6 10 9 6 10Full Binary Tree
Full Binary Tree는 모든 노드가 0개 또는 2개의 자식 노드를 가지고 있는 이진 트리를 말한다. 다른 말로는 2-tree, Proper binary tree 라고도 한다.
Full Binary Tree는 모든 레벨이 노드로 꽉 차 있으므로, 높이가 k인 Full Binary Tree의 노드 수는 2^(k+1) - 1로 표현할 수 있다. Full Binary Tree 는 이진 검색 트리에서 사용되기도 하며, 압축 데이터 구조 등에서도 활용된다.
1
/ \
2 3
/ \ / \
4 5 6 7
Full binary tree에서는 각 노드가 0개 또는 2개의 자식 노드를 가지기 때문에,
위의 예시에서는 모든 레벨이 노드로 꽉 차 있다.
이러한 특성 때문에 full binary tree는 배열을 사용해 노드를 저장할 때 메모리 사용을 최적화할 수 있다.
Full binary tree는 완전 이진 트리와 마찬가지로 이진 검색 트리 등에서 사용된다.Perfect Binary Tree
Perfect binary tree는 모든 내부 노드가 2개의 자식 노드를 가지고, 모든 리프 노드가 같은 깊이 또는 레벨에 있는 이진 트리를 말한다.
다른 말로는 높이가 h인 perfect binary tree는 2^(h+1)-1개의 노드를 가지며, 2^h개의 리프 노드를 가지기도 한다.
Perfect binary tree는 각 노드의 자식 개수가 2개로 고정되어 있기 때문에, 완전 이진 트리와 full binary tree와도 구별되고
perfect binary tree는 배열을 사용해 노드를 저장할 때도 메모리 사용을 최적화할 수 있다.
(이진 검색 트리를 구현할 때 perfect binary tree의 특징을 활용하기도한다.)
1
/ \
2 3
/ \ / \
4 5 6 7
위의 예시에서는 모든 내부 노드가 2개의 자식 노드를 가지고 있으며,
모든 리프 노드가 같은 레벨에 있다.
Perfect binary tree에서는 높이가 h일 때 노드의 개수는 2^(h+1)-1이며,
리프 노드의 개수는 2^h이다.Trie Tree
Trie Tree는 문자열 검색에 특화된 자료 구조로 문자열을 트리 구조로 저장하며, 각 노드는 문자열의 한 글자를 나타낸다. 루트 노드는 공백 문자열을 나타내며, 자식 노드로는 첫 글자가 같은 문자열들이 연결된다.
Trie Tree의 가장 큰 장점은 검색 속도가 빠르다는것으로 문자열 검색 시간은 O(m)으로 문자열 길이에 비례하여 상수 시간 내에 검색이 가능하다.
예를 들어 문자열 ["apple", "app", "banana", "ball"]을 Trie Tree로 표현하면 다음과 같다.
''
/ | \
a b b
/ \ /
p p a
/ \
p l
\
e
루트 노드는 공백 문자열을 나타내며, 자식 노드로는 'a' 'b'가 있다.
이런 방식으로 문자열을 저장하고 검색할 수 있는게 Trie Tree이다.Binary Tree 순회 방법
이진 트리에서 노드를 탐색하거나 출력하기 위해서 순회(traversal)라는 방법을 사용하고 대표적으로 전위, 중위, 후위 순회 방법을 사용한다.
전위 순회(Preorder Traversal)
전위 순회는 루트 노드를 먼저 방문하고, 왼쪽 서브 트리를 순회한 후 오른쪽 서브 트리를 순회하는 방법으로 전위 순회를 수행하면 노드를 깊이 우선 순서로 탐색할 수 있다.
- 루트 노드 방문
- 왼쪽 서브 트리 순회
- 오른쪽 서브 트리 순회
1
/ \
2 3
/ \ / \
4 5 6 7
순회 결과 : 1-2-4-5-3-6-7중위 순회(Inorder Traversal)
중위 순회는 왼쪽 서브 트리를 순회한 후 루트 노드를 방문하고 오른쪽 서브 트리를 순회하는 방법으로 중위 순회를 수행하면 노드를 정렬된 순서대로 탐색할 수 있다.
- 왼쪽 서브 트리 순회
- 루트 노드 방문
- 오른쪽 서브 트리 순회
1
/ \
2 3
/ \ / \
4 5 6 7
순회 결과 : 4-2-5-1-6-3-7후위 순회(Postorder Traversal)
후위 순회는 왼쪽 서브 트리를 순회한 후 오른쪽 서브 트리를 순회하고 루트 노드를 방문하는 방법으로 후위 순회를 수행하면 노드의 자식
노드를 모두 처리한 후 노드를 방문할 수 있다.
- 왼쪽 서브 트리 순회
- 오른쪽 서브 트리 순회
- 루트 노드 방문
1
/ \
2 3
/ \ / \
4 5 6 7
순회 결과 : 4-5-2-6-7-3-1