트리

1 tree

영어로 나무라는 뜻. 주로 tree라고 하면 살아 있거나 직립해 있는 나무를 가리키고, 목재로서의 나무는 wood라고 한다.

2번항목과 뜻이 완전히 다르기 때문에 (일단 모양이 '나무'같다고 명명된 것이긴 하지만) 공대생 개그로 회자될 수 있다. 일례로, 어떤 학자가 기차에 탔는데 옆에 앉은 사람이 tree에 대한 책을 읽길래, What is tree?라고 물어서 주변 사람들은 의아해하고, 읽던 사람은 2번 항목을 설명했다던 이야기가 있다. 순수하게 위상수학적 용어만 써서 contractible 1-dimensional CW complex라고 설명하면 골때렸을듯

1.1 앨범

2 그래프 이론

수학, 특히 그래프 이론에서 회로[1]가 없는 연결 무향 그래프를 트리라고 한다.

자료구조에서 쓰이는 트리와 기본적으로는 같으나 차이가 있다.

  • 자료구조에서의 트리는 부모-자식 관계로 정의하고, 부모에서 자식으로 간선이 이어져있는 유향 그래프이다.
  • 자료구조에서의 트리는 부모가 없는 루트노드를 정의한다.

2.1 정의

트리를 정의할 때에는 다양한 정의가 쓰이고, 다음은 모두 동치이다.

  • G는 트리이다.
  • G는 회로가 없는 연결 그래프이다.
  • G는 회로가 없고, 단순 그래프의 형태를 유지하면서 간선을 추가 할 경우 회로가 생긴다.
  • G는 연결그래프 이고, 어떤 간선을 제거해도 연결그래프가 아니게 된다.
  • G는 연결그래프이고 G의 마이너가 K_3_ 가 아니다.
  • G의 어떤 두 정점을 잡아도 단순 경로가 하나 존재한다.

유한 그래프의 경우에는 다음의 정의도 사용한다.

  • G는 연결되어있고 간선의 수는 정점의 수보다 하나 작다.
  • G는 회로가 없고 간선의 수는 정점의 수보다 하나 작다.

2.2 용어

  • 말단(leaf): 루트노드를 제외한 차수가 1인 정점을 뜻한다. leaf node라 하여 단말 노드라 부르기도 한다.
  • 내부 정점(internal vertex): 차수가 2이상인 정점을 뜻한다.
  • 포레스트(forest): 서로 독립인 트리들의 모임이다.
  • 방향 트리(directed tree): 방향을 무시하고 생각했을 때 트리인 유향그래프는 방향트리이다. 자료구조의 트리는 방향트리의 일종이다.

3 자료구조

부모 노드 밑에 여러 자식 노드가 연결되고, 자식 노드 각각에 다시 자식 노드가 연결되는 재귀적 형태의 자료구조다. 단, 자식 노드의 자식이 부모로 연결되는 경우는 보통 트리로 인정하지 않는다. 트리는 몇가지 기본적이며 재미있는 성질을 갖고 있는데, 트리구조에서 어떤 노드를 빼 버리면 그로 인해 새로 생성되는 연결되지 않은 트리의 개수는 해당 노드에 연결된 엣지의 갯수와 같다.

자식 노드에서 부모 쪽으로 계속해서 타고 올라가다 보면 결국 부모가 없는 하나의 노드로 이어지게 되는데, 이 노드를 루트 노드(root node)라고 부르며, 루트 노드를 중심으로 뻗어나가는 모습이 나무의 구조와 비슷하여 '트리'라는 이름이 붙었다. '수형도(樹形圖)'라고 부르기도 한다.

루트가 정의된 트리를 rooted tree, 루트를 정의하지 않은 트리를 unrooted tree라 한다.

rooted tree에서는 여러가지 용어를 정의한다. 높이(height)는 루트의 높이를 0으로 하고, 자식의 높이를 원래 노드보다 1 큰 것으로 정의를 한다. 말단 노드(leaf node)의 정의는 자식이 없는 노드이다. unrooted tree에서는 차수가 1인 노드로 말단 노드를 정의한다.

주변에서 볼 수 있는 트리의 쉬운 예로 나무위키의 목차를 볼 수 있다. 그 외에 유닉스/윈도우의 디렉토리(폴더)구조 역시 트리구조이다. 유닉스와 달리, 윈도우의 경우는 드라이브마다 디렉토리 구조를 갖게 되므로, 포레스트라 볼 수도 있다. 디아블로의 스킬트리도 트리의 한 예.[2]

3.1 이진 트리(Binary Tree)

300px-Binary_tree.svg.png
이진 트리(위키백과)

부모 노드 밑에 자식 노드가 최대 2개밖에 오지 않는, 트리의 가장 간단한 형태이다. 두 자식 노드를 보통 왼쪽 자식과 오른쪽 자식으로 구분지으며, 하나의 값과 왼쪽, 오른쪽 자식 노드를 각각 가리킬 두 개의 포인터를 가진 구조로 구현할 수 있다.

일반적인 트리 구조를 왼쪽에 자식 노드, 오른쪽에 형제 노드를 배치 하는 이진 트리 구조로 생각할 수 있으며(Left-Child, Right-Sibling), 이 방법으로 모든 트리를 이진 트리 형태로 재구성할 수 있다(좌우를 바꾸어도 동일). 때문에 특별한 이유가 없는 이상 트리는 보통 이진 트리로 구현된다.

이진트리에는 다음과 같은 종류가 있다.

  • 정 이진 트리(full binary tree): 모든 트리의 자식은 0개나 2개이다.
  • 포화 이진 트리(perfect binary tree): 모든 리프 노드의 높이가 같다.
  • 완전 이진 트리(complete binary tree): 모든 리프노드의 높이가 최대 1 차이가 나고, 모든 노드의 오른쪽 자식이 있으면 왼쪽 자식이 있는 이진트리이다. 다시 말해 트리의 원소를 왼쪽에서 오른쪽으로 하나씩 빠짐없이 채워나간 형태이다.

일반적으로 비선형 구조인 이진트리는 각각의 노드가 자식들의 포인터를 갖도록 구현되지만, 완전 이진 트리의 경우 왼쪽부터 빠짐없이 채워져있다는 성질을 이용해 배열을 사용하여 구현 하기도 한다. 1번부터 시작하는 배열을 생각하면 n번째 원소의 왼쪽 자식은 2n, 오른쪽 자식은 2n+1번째 원소로 구성하면 된다. 또 n번째 원소의 부모 노드는 [n/2]번째 원소가 된다.

3.1.1 이진 탐색 트리(Binary Search Tree, BST)

300px-Binary_search_tree.svg.png
이진 트리의 일종으로, 노드의 왼쪽 가지에는 노드의 값보다 작은 값들만 있고, 오른쪽 가지에는 큰 값들만 있도록 구성되었다. 자식 노드들도 동일한 방법으로 정렬되어 노드의 왼쪽 자식의 왼쪽 가지에는 왼쪽 자식이 가진 값보다 작은 값만 있고, 왼쪽 자식의 오른쪽 가지에는 왼쪽 자식의 값보다 큰 값들만 있고, 오른쪽 자식의 왼쪽 가지에는... 이런 식으로 이진 탐색 트리의 어느 노드를 잡아도 동일한 규칙으로 정렬이 되어 있다.

이렇게 구성해 두면 어떤 값 n을 찾을 때, 루트 노드와 비교해서 n이 더 작다면 루트 노드보다 큰 값들만 모여 있는 오른쪽 가지는 전혀 탐색할 필요가 없다. 마찬가지로 루트 노드의 왼쪽 자식보다 n이 크다면 왼쪽 자식의 왼쪽 가지는 탐색할 필요가 없고... 다시 말해 트리 자체가 이진 탐색을 하기에 적합한 구성이 되는 것이다. 또한 값을 찾을 때 뿐만이 아니라 값을 삽입하거나 삭제할 때도 똑같은 과정을 거치므로, 이상적인 상황에서 탐색/삽입/삭제 모두 시간복잡도가 O(log N)이 된다.

다만 단점이 있는데, 값이 삽입되거나 삭제되는 경우에 따라서 운이 안좋으면 최악의 경우에 O(N)의 시간이 걸리게 된다. 예를 들어, 비어있는 이진 탐색 트리에 1부터 100까지 순서대로 삽입한다면 처음 루트 노드는 1이 되고, 2는 1보다 크니 1의 오른쪽 자식이 되고, 3은 1보다 크니 1의 오른쪽, 2보다 크니 2의 오른쪽... 이런 식으로 트리의 오른쪽 끝으로만 계속 성장하게 된다. 이 상태로 50을 찾는다고 하면 결국 1부터 순서대로 오른쪽으로 쭈욱 내려가는 선형 탐색이나 다를게 없게 된다. 이러한 경우를 트리가 편향(skew)되었다고 한다.

3.1.1.1 C++

#include 
const tree* null = NULL;
struct tree {
tree* parent = NULL; //부모 노드
tree* child[2] = { NULL }; //자식 노드
int value = 0; //값
tree(int x, tree* parent1) { //생성자
value = x;
parent = parent1;
}
};
void insert(tree* parent, tree*& node, int value) {
if (node == NULL) { //노드가 비어있다면
node = new tree(value, parent); //새로운 노드를 만들고
return; //종료
}
if (value == node->value) //값이 중복된다면
return; //종료
insert(node, node->child[value > node->value], value);
//삽입할 값이 노드의 값보다 크면 node->child[0] 탐색
//작다면 node->child[1] 탐색
}
tree*& find(tree*& node, int value) {
if (node == NULL) //노드가 비어있다면
return null; //NULL 반환
if (value == node->value) //노드의 값이 검색할 값와 같다면
return node; //검색된 노드의 위치 반환
return find(node->child[value > node->value], value);
//검색할 값이 노드의 값보다 크면 node->child[0] 탐색
//작다면 node->child[1] 탐색
}
void remove(tree*& node) {
if (node == NULL) //삭제될 노드가 없다면
return; //종료
int a = (bool)node->child[0] + (bool)node->child[1]; //삭제될 노드의 자식 수
if (!a) { //삭제될 노드의 자식이 없다면
if (node->parent != NULL) //부모 노드가 있다면
node->parent->child[node->parent->child[1] == node] = NULL;
//부모 노드가 삭제될 노드를 못 가리키게 만듬.
delete node; //노드 삭제
}
else if (a == 1) { //자식 노드가 1개 있다면
if (node->parent != NULL) //부모 노드가 있다면
node->parent->child[node->parent->child[1] == node] = node->child[node->child[1] != NULL];
// 부모 노드가 삭제될 노드 대신 그 노드의 자식을 가리키게 만듬.
delete node;
//노드 삭제
}
else if (a == 2) {
tree* repl = node->child[0]; //삭제될 노드
while (repl->child[1] != NULL)
repl = repl->child[1];
//왼쪽 서브트리 중 가장 작은 값을 가진 노드 선택
node->value = repl->value;
//삭제될 노드의 값을 다른 노드에 넘겨줌
remove(repl);
//노드 삭제
}

if (a

3.1.1.2 AVL-tree

AVL-tree(위키백과, 영어 주의)

가장 처음으로 나온 자가 균형 이진 탐색 트리로, 이진 탐색 트리가 운이 안 좋을 경우 O(N)의 시간이 걸리는 것을 보완한 트리이다.이상적인 상황에서나 최악의 상황에서 탐색/삽입/삭제 모두 시간 복잡도가 O(log N)이다. 만족해야 하는 조건은 모든 노드에서 오른쪽 트리와 왼쪽 트리의 높이(height)의 차이가 1이하로만 나는것. 삽입/삭제를 할 때마다 균형이 안맞는 것을 맞추기 위해 트리의 일부를 왼쪽 혹은 오른쪽으로 회전시켜야 한다.
균형은 아래에 나온 Red-black tree보다 훨씬 잘 잡히지만, 그렇기 때문에 Red-black tree보다 삽입과 제거가 느리고 탐색 자체는 빠르다. 그래서 보통 자가 균형 이진 탐색 트리가 필요한 경우 Red-black tree를 쓰는 경우가 많다.

3.1.1.3 Red-black tree

Red-black tree(위키백과, 영어 주의)

자가 균형 이진 탐색 트리의 일종으로, 노드에 색깔 속성이 붙은 트리이다. 이상적인 상황에서나 최악의 상황에서 탐색/삽입/삭제 모두 시간 복잡도가 O(log N)인 궁극의 트리이다.
구조 표현시 다른 트리와는 달리 자식이 하나도 없는 노드 끝에는 널 리프 노드라는것을 붙인다. 이 널 리프 노드는 단지 트리의 끝을 표현하는데에만 쓰인다.
만족해야 하는 조건은 다음과 같다.

  • 모든 노드는 레드 아니면 블랙이다.
  • 루트 노드는 블랙이다.
  • 모든 널 리프 노드는 블랙이다.
  • 레드 노드의 자식 노드는 언제나 블랙이다. 그러므로 블랙 노드만이 레드 노드의 부모가 될 수 있다.
알기 쉽게 말해서 블랙 노드는 연속으로 나올 수 있지만, 레드 노드는 그렇지 못하다.
  • 임의의 한 노드에서 널 리프 노드까지 도달하는 모든 경로에는 널 리프 노드를 제외하고 항상 같은 수의 블랙 노드가 있다.

마지막 조건을 다시 말해보면, 이 임의의 노드를 루트 노드로 설정하면, 레드블랙 트리의 Black-depth(블랙 노드의 깊이)는 항상 일정하다는 말이다. 또한 바로 전 조건인 '레드 노드의 자식 노드는 언제나 블랙이다'에 의해 레드 노드가 연달아서 나올 수 없기 때문에 총 깊이는 최소 B(블랙 노드의 갯수)에서 최대 2B-1로 제한된다 (이래서 시간복잡도가 일정한 것).
이 때문에 레드블랙트리를 그림으로 그릴 때, 레드 노드를 높이에 영향을 주지 않는 왼쪽과 오른쪽으로 이어지도록 그리기도 한다.
역시 삽입과 삭제시 경우에 따라 노드의 색 변환 또는 트리 회전[3]이 필요하며 구현은 꽤나 복잡하지만 실 사용에선 매우 효율적인 모습을 보인다. C++ STL의 set, map이 이 레드블랙 트리를 이용하여 구현되었다.[4]
또한 2-3-4 트리와 매우 유사하며 2-3-4 트리로 변환도 가능하다.

IOI 국가대표 교육에서 실습 문제중 하나로 튀어나와 학생들을 멘붕시킨 적이 있다 카더라. 심지어 한 번이 아니라 카더라(...) 오오 적흑목 오오 이런 내가 먼저 쓰려 했는데 쩝 위키니트들..

3.1.2 힙(heap)

힙 트리 항목 참고

3.2 B-tree

(위키 백과, 영어 주의)

이진 트리를 확장한 것으로 이진 트리는 하나의 노드가 가질 수 있는 자식 노드의 수가 최대 2개지만 B-tree는 2개 이상을 가질 수 있다.
모든 노드에 있는 값들은 정렬되어 있는 상태이며 order를 나타내는 숫자인 m을 가질 수 있다. 이 B-tree 를 B-tree of order m 이라고 한다.
B-tree of order m은 다음과 같은 조건을 만족 시킨다.

  • 모든 노드가 가질 수 있는 자식 노드의 최대 수는 m이다.
  • 루트 노드를 제외한 내부 노드 들은 적어도 m/2개의 자식 노드를 가진다.
  • 루트 노드는 최소한 두개의 자식 노드를 가진다.
  • k개의 자식 노드를 가진 내부 노드들은 k-1개의 값을 가지고 있다.
  • 모든 리프 노드들의 높이는 같다.

노드에 접근 하는 시간 자체가 노드에서 연산하는 시간보다 훨씬 길 경우, B-tree를 쓰는것이 매우 좋다. 자식 노드가 가질 수 있는 수를 늘이고, 트리의 높이를 줄여서 노드에 접근하는 횟수를 줄일 수 있기 때문이다. 이런 경우는 보통 노드들이 하드디스크같은 보조 기억 장치에 있을때 일어난다. 그래서 입출력 성능을 높이기 위해 노드 하나의 크기를 디스크 블럭 하나의 크기와 동일하게 하는 경우가 많다.

3.2.1 2-3-4 tree

B-tree of order 4의 일종으로 노드당 2개에서 4개까지의 트리를 가리키는 포인터를 가지고 있다. 구조가 이진 트리인 Red-black tree와 유사하여 변환이 가능하다. 노드 내부의 키 값은 1개에서 3개까지 가질 수 있으며, 삽입과 삭제시 이를 넘거나(오버플로우) 이 미만이 될 시(언더플로우) 각각 분할과 병합 연산을 따로 해야하기 때문에 기존 트리보다 약간 복잡하다.

3.2.2 B+ tree

B-tree의 확장형. 루트 노드와 중간의 노드는 키를 이용하여 위치를 찾아가는 인덱스 역할만을 하며 데이터 자체는 모두 리프 노드에 저장한다. 그리고 리프 노드는 이중 연결 리스트로 구성하여 데이터를 순차적으로 검색하기 용이하다.

3.3 포레스트(Forest)

하나 이상의 트리로 이루어진 집합을 포레스트라고 부른다. 나무가 모여서 숲

다만 이것도 트리를 이진 트리로 바꾸는 방법을 비슷하게 적용하면 각 트리들의 루트 노드가 이진 트리의 왼쪽 가지에 모여있는 형태의 이진 트리 하나로 바꿀 수 있다. (...)

3.4 트라이(Trie)

트라이 항목 참고
  1. ↑ Circuit이 아니라 Cycle이다.
  2. ↑ 실제로는 루트 노드가 하나가 아닌 경우가 많으므로 포레스트(Forest)에 더 가깝다.
  3. ↑ 최대 3회
  4. ↑ 언어 자체에서 연관 배열(Associative Array)을 지원하는 경우 대부분 레드블랙 트리로 구현되어 있다.