|
이산수학 Discrete Mathematics |
||
|
{{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px; word-break: keep-all" |
이론 | |
| <colbgcolor=#3CC> 기본 대상 | 수학기초론( 수리논리학 · 집합론) · 수열 · 조합 · 알고리즘 · 확률 | |
| 다루는 대상과 주요 토픽 | ||
| 수열 | 등차수열( 뛰어 세기) · 등비수열 · 계차수열 · 조화수열 · 귀납적 정의( 점화식) · 급수 · 규칙과 대응 · 규칙 찾기 · 피보나치 수열 · 읽고 말하기 수열 · 생성함수 | |
| 조합 | 경우의 수( /공식) · 순열( 완전 순열 · 염주 순열) · 치환 · 분할( 분할수) · 최단거리 · 제1종 스털링 수 · 제2종 스털링 수 · 카탈랑 수 · 벨 수 · 라흐 수 · 포함·배제의 원리 · 더블 카운팅 · 조합론 | |
| 그래프 | 수형도(트리) · 인접행렬 · 마방진 · 마법진 · 한붓그리기( 해밀턴 회로) · 쾨니히스베르크 다리 건너기 문제 | |
| 기타 | P-NP 문제미해결 · 4색정리 · 이항정리( 파스칼의 삼각형) · 이산 푸리에 변환 · 비둘기 집의 원리 · 상트페테르부르크의 역설 · 투표의 역설 · 에르고딕 가설미해결 · 콜라츠 추측미해결 · 시행착오 ( 예상과 확인) · 불 논리 · 브라에스 역설 | |
| 관련 문서 | 논리학 관련 정보 · 수학 관련 정보 · 컴퓨터 관련 정보 · 틀:수학기초론 · 틀:통계학 · 틀:이론 컴퓨터 과학 | }}}}}}}}} |
1. 개요
tree diagram, tree樹形圖(수형도)
수학, 특히 그래프 이론에서 회로가 없는 연결된 무방향의 그래프를 트리라고 한다.
자료구조에서 쓰이는 트리와 기본적으로는 같으나 차이가 있다.
- 자료구조에서의 트리는 부모-자식 관계로 정의하고, 부모에서 자식으로 간선이 이어져 있는 방향 그래프이다.
- 자료구조에서의 트리는 부모가 없는 루트 노드를 정의한다.
중·고교 수학 교과 과정에도 나오는데, 중학교 2학년 수학의 확률 파트에서 나온다.
언어학의 수형도 관련해서는 통사론 문서를 참고하자.
2. 정의
트리를 정의할 때에는 다양한 정의가 쓰이고, 다음은 모두 동치이다.- [math(G)]는 트리이다.
- [math(G)]는 회로가 없는 연결 그래프이다.
- [math(G)]는 회로가 없고, 단순 그래프의 형태를 유지하면서 간선을 추가할 경우 회로가 생긴다.
- [math(G)]는 연결 그래프이고, 어떤 간선을 제거해도 연결 그래프가 아니게 된다.
- [math(G)]는 연결 그래프이고 [math(K_3)]가 [math(G)]의 마이너가 아니다.
- [math(G)]의 어떤 두 정점을 잡아도 단순 경로가 하나 존재한다.
- [math(G)]의 두 정점을 잇는 경로는 유일하다.
유한 그래프의 경우에는 다음의 정의도 사용한다.
- [math(G)]는 연결되어 있고 간선의 수는 정점의 수보다 하나 작다.
- [math(G)]는 회로가 없고 간선의 수는 정점의 수보다 하나 작다.
3. 용어
트리 각 부분의 명칭과 용어는 다음 그림과 같다.트리는 항상 루트(root)에서부터 시작된다. 루트는 자식(child) 노드를 가지며, 간선(edge)으로 연결되어 있다. 자식 노드의 개수는 차수(degree)라고 하며, 크기(size)는 자신을 포함한 모든 자식 노드의 개수다. 높이(height)는 현재 위치에서부터 리프(leaf)까지의 거리, 깊이(depth)는 루트에서부터 현재 노드까지의 거리다. 트리는 그 자식도 트리인 서브트리(subtree) 구성을 띤다. 레벨(level)은 0부터 시작한다. 논문에 따라 1부터 시작하는 경우도 있으나, 0부터 시작하는 것이 좀 더 일반적이다. 트리는 항상 단방향(uni-directional)이기 때문에[1] 간선의 화살표는 생략 가능하다. 그림에서도 마찬가지로 생략해서 표현했고 일반적으로 방향은 위에서 아래로 향한다.
- 노드(node): 트리를 구성하는 기본 원소
- 루트 노드(root node/root): 트리에서 부모가 없는 최상위 노드, 트리의 시작점
- 부모 노드(parent node): 루트 노드 방향으로 직접 연결된 노드
- 자식 노드(child node): 루트 노드 반대방향으로 직접 연결된 노드
- 형제 노드(siblings node): 같은 부모 노드를 갖는 노드들
- 리프 노드(leaf node/leaf): 차수가 0인 정점을 뜻한다. 쉽게 말해 자식이 없는 노드. 단말 노드라 부르기도 한다.
- 경로(path): 한 노드에서 다른 한 노드에 이르는 길 사이에 있는 노드들의 순서
- 길이(length): 출발 노드에서 도착 노드까지 거치는 간선의 개수
- 깊이(depth): 루트 경로의 길이
- 레벨(level): 루트 노드(level=0)부터 노드까지 연결된 간선 수의 합
- 높이(height): 가장 긴 루트 경로의 길이
- 차수(degree): 각 노드의 자식의 개수[2]
- 트리의 차수(degree of tree): 트리의 최대 차수 = [math(\max(\deg_1, \deg_2, \cdots, \deg_n))]
- 크기(size): 노드의 개수
- 너비(width): 가장 많은 노드를 갖고 있는 레벨의 크기
- 내부 정점(internal vertex): 차수가 2 이상인 정점을 뜻한다.
- 포레스트(forest): 서로 독립인 트리들의 모임이다.
- 방향 트리(directed tree): 방향을 무시하고 생각했을 때 트리인 유향 그래프는 방향 트리이다. 자료구조의 트리는 방향 트리의 일종이다.[3]
4. 자료구조
부모 노드 밑에 여러 자식 노드가 연결되고, 자식 노드 각각에 다시 자식 노드가 연결되는 재귀적 형태의 자료구조다. 단, 자식 노드의 자식이 부모로 연결되는 경우는 보통 트리로 인정하지 않는다.자식 노드에서 부모 쪽으로 계속해서 타고 올라가다 보면 결국 부모가 없는 하나의 노드로 이어지게 되는데, 이 노드를 루트 노드(root node)라고 부르며, 루트 노드를 중심으로 뻗어나가는 모습이 나무의 구조와 비슷하여 '트리'라는 이름이 붙었다. '수형도(樹形圖)'라고 부르기도 한다.
루트가 정의된 트리를 rooted tree, 루트를 정의하지 않은 트리를 unrooted tree라 한다.
Rooted tree에서는 여러가지 용어를 정의한다. 높이(height)는 루트의 높이를 0으로 하고, 자식의 높이를 원래 노드보다 1 큰 것으로 정의를 한다. 말단 노드(leaf node)의 정의는 자식이 없는 노드이다. Unrooted tree에서는 차수가 1인 노드로 말단 노드를 정의한다.
주변에서 볼 수 있는 트리의 쉬운 예로 나무위키의 목차를 볼 수 있다. 그 외에 유닉스/윈도우의 디렉터리(폴더)구조 역시 트리구조이다.[4] 유닉스와 달리, 윈도우의 경우는 드라이브마다 디렉터리 구조를 갖게 되므로, 포레스트라 볼 수도 있다. 디아블로의 스킬트리도 트리의 한 예.[5]
학부생 수준에서는 괄호() 기능이 있는 계산기를 작성하는 알고리즘에 전위순환이나 후위순환을 쓰기 때문에 모른다고 그냥 넘기면 나중에 다시 또 공부해야할 순간이 온다.
4.1. 이진 트리(Binary Tree)
이진 트리(위키백과)
부모 노드 밑의 자식 노드 개수(=차수, degree)를 최대 2개로 제한하는, 트리의 가장 간단한 형태다. 두 자식 노드를 보통 왼쪽 자식과 오른쪽 자식으로 구분지으며, 하나의 값과 왼쪽, 오른쪽 자식 노드를 각각 가리킬 두 개의 포인터를 가진 구조로 구현할 수 있다.
일반적으로 n개의 자식을 가질 수 있는 트리 구조에서, 1개를 초과한 자식 하나마다 노드를 하나 추가해 추가된 새 노드의 왼쪽에 원래의 자식 노드, 오른쪽에 형제 노드를 배치 하는 이진 트리 구조로 변환할 수 있으며(left-child, right-sibling), 이 방법으로 모든 트리를 이진 트리 형태로 재구성할 수 있다(좌우를 바꾸어도 동일). 때문에 특별한 이유가 없는 이상 트리는 보통 이진 트리로 구현된다.
이진트리에는 다음과 같은 종류가 있다.
- 정 이진 트리(full binary tree): 모든 트리의 자식은 0개나 2개다.
- 포화 이진 트리(perfect binary tree): 모든 리프 노드의 높이가 같고 리프 노드가 아닌 노드는 모두 2개의 자식을 갖는다. 이진 트리에서 리프 높이의 최대치가 n일 때 가장 많이 존재할 수 있는 노드의 수는 [math(2^n-1)]개인데 포화 이진 트리는 이 개수를 모두 채운 이진 트리라고도 볼 수 있다. 또한, 모든 포화 이진 트리는 정 이진 트리이다.
- 완전 이진 트리(complete binary tree): 모든 리프노드의 높이가 최대 1 차이가 나고, 모든 노드의 오른쪽 자식이 있으면 왼쪽 자식이 있는 이진트리이다. 다시 말해 트리의 원소를 왼쪽에서 오른쪽으로 하나씩 빠짐없이 채워나간 형태이다. 포화 이진 트리는 완전 이진 트리의 부분집합이다. 단, 포화 이진 트리가 아닌 완전 이진 트리는 정 이진 트리일 수도 있고 아닐 수도 있다.
일반적으로 비선형 구조인 이진트리는 각각의 노드가 자식들의 포인터를 갖도록 구현되지만, 완전 이진 트리의 경우 왼쪽부터 빠짐없이 채워져있다는 성질을 이용해 배열을 사용하여 구현 하기도 한다. 1번부터 시작하는 배열을 생각하면 [math(n)]번째 원소의 왼쪽 자식은 [math(2n)], 오른쪽 자식은 [math(2n+1)]번째 원소로 구성하면 된다. 또, [math(n)]번째 원소의 부모 노드는 [math(lfloor n/2 rfloor)]번째 원소가 된다.
4.1.1. 이진 트리 순회 방법
- 중위 순회(in-order traversal): 왼쪽 자손, 자신, 오른쪽 자손 순서로 방문하는 순회 방법. 이진 탐색 트리를 중위 순회하면 정렬된 결과를 얻을 수 있다. 이를 트리 정렬(Tree sort)이라고 한다.
- 전위 순회(pre-order traversal): 자신, 왼쪽 자손, 오른쪽 자손 순서로 방문하는 순회 방법.
- 후위 순회(post-order traversal): 왼쪽 자손, 오른쪽 자손, 자신 순서로 방문하는 순회 방법.
- 레벨 순서 순회(level-order traversal): 너비 우선 순회(Breadth-First traversal)라고도 한다. 노드를 레벨 순서로 방문하는 순회 방법. 위의 세 가지 방법은 스택을 활용하여 구현할 수 있는 반면 레벨 순서 순회는 큐를 활용해 구현할 수 있다.
위의 트리를 순회하면 다음과 같다.
- In-order: 1 3 4 6 7 8 10 13 14
- Pre-order: 8 3 1 6 4 7 10 14 13
- Post-order: 1 4 7 6 3 13 14 10 8
- Level-order: 8 3 10 1 6 14 4 7 13
4.1.2. 이진 탐색 트리(Binary Search Tree, BST)
BST은(는) 여기로 연결됩니다.
BEMANI Sound Team에 대한 내용은
BEMANI 시리즈/아티스트 문서, BEMANI Sound Team의 유래에 대한 내용은
BEMANI 시리즈 아티스트 명의 삭제 논란
문서
참고하십시오.이진 트리의 일종으로, 노드의 왼쪽 가지에는 노드의 값보다 작은 값들만 있고, 오른쪽 가지에는 큰 값들만 있도록 구성되었다. 자식 노드들도 동일한 방법으로 정렬되어 노드의 왼쪽 자식의 왼쪽 가지에는 왼쪽 자식이 가진 값보다 작은 값만 있고, 왼쪽 자식의 오른쪽 가지에는 왼쪽 자식의 값보다 큰 값들만 있고, 오른쪽 자식의 왼쪽 가지에는… 이런 식으로 이진 탐색 트리의 어느 노드를 잡아도 동일한 규칙으로 정렬이 되어 있다.
이렇게 구성해 두면 어떤 값 [math(n)]을 찾을 때, 루트 노드와 비교해서 [math(n)]이 더 작다면 루트 노드보다 큰 값들만 모여 있는 오른쪽 가지는 전혀 탐색할 필요가 없다. 마찬가지로 루트 노드의 왼쪽 자식보다 [math(n)]이 크다면 왼쪽 자식의 왼쪽 가지는 탐색할 필요가 없고… 다시 말해 트리 자체가 이진 탐색을 하기에 적합한 구조가 되는 것이다. 또한 값을 찾을 때뿐만이 아니라 값을 삽입하거나 삭제할 때도 똑같은 과정을 거치므로, 트리가 이상적으로 구성되었을 때 탐색/삽입/삭제 모두 시간복잡도가 [math(O(log N))]이 된다.
이진 탐색 트리를 이용해 원하는 값(여기서는 8)을 찾는(탐색하는) 과정은 위 그림과 같다. 이 그림에서 먼저, 루트는 15이며, 8은 15보다 작다. 따라서 왼쪽 자식 노드를 탐색한다. 10 또한 마찬가지로 8보다 크므로, 왼쪽을 택한다. 8은 5보다 크므로, 오른쪽으로 탐색한다. 그 다음, 8은 7보다 크므로 마지막으로 오른쪽을 탐색해 정답 8을 찾아낸다. 이처럼 많은 데이터 사이에서 단 4번만에 정답을 찾아내는 것을 볼 수 있다. 만약 (트리에 존재하지 않는) 6을 찾는다면 5 이후에 오른쪽을 탐색하게 될 것이고, 다음에는 7, 이후에 다시 왼쪽을 탐색하려 하는데, 왼쪽 노드가 없으므로 탐색을 중단하고 ‘없음’을 출력하게 될 것이다.
다만 이러한 효율성은 트리의 원소들이 좌우로 잘 분배되어 있다는 전제 하에서이다. 그렇지 않다면 최악의 경우에는 [math(O(N))]의 시간이 걸릴 수 있다. 예를 들어, 비어 있는 이진 탐색 트리에 1부터 100까지 순서대로 삽입한다면 처음 루트 노드는 1이 되고, 2는 1보다 크니 1의 오른쪽 자식이 되고, 3은 1보다 크니 1의 오른쪽, 2보다 크니 2의 오른쪽… 이런 식으로 트리는 오른쪽으로만 계속 성장하게 된다. 이 상태로 50을 찾는다고 하면 결국 1부터 시작해 오른쪽으로 모든 원소를 방문하게 되므로 선형 탐색을 하는 것이나 마찬가지이다. 이러한 경우를 가리켜 트리가 편향(skew)되었다고 한다. 이를 방지하기 위해 원소를 추가하거나 제거할 때 자동으로 균형을 맞추어 주는 알고리즘이 사용된다.
4.1.2.1. AVL-tree
AVL-tree(위키백과)가장 처음으로 나온 자가 균형 이진 탐색 트리로, 이진 탐색 트리가 비효율적으로 구성되었을 경우 [math(O(N))]의 시간이 걸리는 것을 보완한 트리이다. 이상적인 상황에서나 최악의 상황에서 탐색/삽입/삭제 모두 시간 복잡도가 [math(O(\log N))]이다. 만족해야 하는 조건은 모든 노드에서 오른쪽 트리와 왼쪽 트리의 높이(height)의 차이가 1 이하로만 나는 것. 삽입/삭제를 할 때마다 깨진 균형을 맞추기 위해 트리의 일부를 왼쪽 혹은 오른쪽으로 회전시킨다.
균형은 아래에 나온 red-black tree보다 엄격하게 맞추므로 탐색 자체는 빠르지만, 삽입과 제거는 느리다. 그래서 일반적으로는 red-black tree가 많이 사용된다.
4.1.2.2. 레드-블랙 트리
자가 균형 이진 탐색 트리의 일종으로, 노드가 블랙 또는 레드의 색깔을 갖는 트리이다.
4.1.3. 스레드 이진 트리
Threaded Binary Tree.
왼쪽, 혹은 오른쪽 자식 노드가 없는 노드의 링크를 중위탐색시 선행노드, 혹은 후속노드로 연결해놓은 이진 트리이다. 자식 노드로 향하는 링크에 현재 링크가 자식 노드인지, 혹은 선행/후속노드인지를 표기하는 플래그가 추가된다. 중위탐색을 재귀호출이나 스택 등을 사용하지 않고도 구현할 수 있어서 순차 탐색 속도가 빨라진다. 삽입/삭제를 할 때 링크를 재연결해주는 과정이 필요하기에 일반 이진 트리에 비해 구현은 약간 복잡해진다. 엄밀히 말하면 회로(cycle)가 생기기 때문에 트리는 아니다.
4.1.4. 힙(heap)
4.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를 쓰는것이 매우 좋다. 자식 노드가 가질 수 있는 수를 늘이고, 트리의 높이를 줄여서 노드에 접근하는 횟수를 줄일 수 있기 때문이다. 이런 경우는 보통 노드들이 하드디스크같은 보조 기억 장치에 있을때 일어난다. 그래서 입출력 성능을 높이기 위해 노드 하나의 크기를 디스크 블럭 하나의 크기와 동일하게 하는 경우가 많다.
4.2.1. 2-3-4 tree
B-tree of order 4의 일종으로 노드당 2개에서 4개까지의 트리를 가리키는 포인터를 가지고 있다. 구조가 이진 트리인 red-black tree와 유사하여 변환이 가능하다. 노드 내부의 키 값은 1개에서 3개까지 가질 수 있으며, 삽입과 삭제시 이를 넘거나(오버플로우) 이 미만이 될 시(언더플로우) 각각 분할과 병합 연산을 따로 해야하기 때문에 기존 트리보다 약간 복잡하다.4.2.2. B+ tree
B-tree의 확장형. 루트 노드와 중간의 노드는 키를 이용하여 위치를 찾아가는 인덱스 역할만을 하며 데이터 자체는 모두 리프 노드에 저장한다. 데이터를 정렬하여 리프 노드에 저장했고, 그 위에 B-tree의 규칙으로 키를 저장해 트리를 구성했다고 생각하면 편하다. 이때 리프 노드는 이중 연결 리스트로 구성하여 데이터를 순차적으로 검색하기 용이하도록 한다.4.3. 포레스트(forest)
나무가 숲을 이루는 것처럼 하나 이상의 트리로 이루어진 집합을 포레스트라고 부른다.트리를 이진 트리로 바꾸는 방법을 포레스트에도 비슷하게 적용하면, 각 트리들의 루트 노드가 이진 트리의 왼쪽 가지에 모여있는 형태의 이진 트리 하나로 바꿀 수 있다.
4.4. 트라이(trie)
5. 기타
정점의 갯수가 n개이고, 트리의 정점에 번호를 붙이는 labled tree의 경우 서로 다른 트리의 갯수는 [math(n^{n-2})]개임이 알려져있고, 이를 케일리 공식(Cayley's theorem)이라고 한다. # 번호를 붙이지 않고 그래프의 isomorphic만으로 서로 다른 것을 구분하는 unlabled tree의 경우도 정점의 갯수에 대한 트리의 갯수를 나타내는 생성함수가 존재하나, labeled tree보다 훨씬 복잡하다.[6]6. 관련 문서
[1]
그렇지 않으면 순환참조가 되어 오류가 발생한다.
[2]
이진 트리에서는 이것의 최댓값이 2로 제한된다.
[3]
또한 자료구조의 트리는 rooted 트리의 일종이기도 하다.
[4]
실제로는 심볼릭 링크 등의 기능이 존재하여 이상적인 트리는 아니다.
[5]
실제로는 루트 노드가 하나가 아닌 경우가 많으므로 포레스트(forest)에 더 가깝다.
[6]
트리뿐만 아니라 unlabled graph의 경우 label을 통해서 구분이 상대적으로 쉬운 labeled grpah와 달리 오로지 isomorphic을 이용해서만 그래프를 구분해야하므로, 경우의 수를 찾는것이 훨씬 어렵다.