트리(그래프)
덤프버전 :
어떤 마술의 금서목록에 나오는 가상의 슈퍼컴퓨터에 대한 내용은 트리 다이어그램(어떤 마술의 금서목록) 문서 참고하십시오.1. 개요[편집]
tree diagram, tree
樹形圖(수형도)
수학, 특히 그래프 이론에서 회로가 없는 연결된 무향의 그래프를 트리라고 한다.
자료구조에서 쓰이는 트리와 기본적으로는 같으나 차이가 있다.
- 자료구조에서의 트리는 부모-자식 관계로 정의하고, 부모에서 자식으로 간선이 이어져 있는 유향 그래프이다.
- 자료구조에서의 트리는 부모가 없는 루트 노드를 정의한다.
중·고교 수학 교과 과정에도 나오는데, 중학교 2학년 수학의 확률 파트에서 나온다.
언어학의 수형도 관련해서는 통사론 문서를 참고하자.
2. 정의[편집]
트리를 정의할 때에는 다양한 정의가 쓰이고, 다음은 모두 동치이다.
- [math(G)]는 트리이다.
- [math(G)]는 회로가 없는 연결 그래프이다.
- [math(G)]는 회로가 없고, 단순 그래프의 형태를 유지하면서 간선을 추가할 경우 회로가 생긴다.
- [math(G)]는 연결 그래프이고, 어떤 간선을 제거해도 연결 그래프가 아니게 된다.
- [math(G)]는 연결 그래프이고 [math(G)]의 마이너가 [math(K_3)]가 아니다.
- [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): 루트 노드를 제외한 차수가 1인 정점을 뜻한다. 쉽게 말해 자식이 없는 노드. 단말 노드라 부르기도 한다.
- 경로(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): 왼쪽 자손, 자신, 오른쪽 자손 순서로 방문하는 순회 방법. 이진 탐색 트리를 중위 순회하면 정렬된 결과를 얻을 수 있다.
- 전위 순회(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보다 크므로, 왼쪽을 택한다. 5는 8보다 작으므로, 오른쪽으로 탐색한다. 그 다음, 7은 8보다 작으므로 마지막으로 오른쪽을 탐색해 정답 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보다 삽입과 제거가 느리고 탐색 자체는 빠르다. 그래서 보통 자가 균형 이진 탐색 트리가 필요한 경우 red-black tree를 쓰는 경우가 많다.
4.1.2.2. Red-black tree[편집]
Red-black tree(위키백과)
자가 균형 이진 탐색 트리의 일종으로, 노드에 색깔 속성이 붙은 트리이다. 이상적인 상황에서나 최악의 상황에서 탐색/삽입/삭제 모두 시간 복잡도가 [math(O(\log N))]
구조 표현시 다른 트리와는 달리 자식이 하나도 없는 노드 끝에는 널 리프 노드라는것을 붙인다. 이 널 리프 노드는 단지 트리의 끝을 표현하는데에만 쓰인다.
만족해야 하는 조건은 다음과 같다.
- 모든 노드는 레드 아니면 블랙이다.
- 루트 노드는 블랙이다.
- 모든 널 리프 노드는 블랙이다.
- 레드 노드의 자식 노드는 언제나 블랙이다. 그러므로 블랙 노드만이 레드 노드의 부모가 될 수 있다.
알기 쉽게 말해서 블랙 노드는 연속으로 나올 수 있지만, 레드 노드는 그렇지 못하다.
- 임의의 한 노드에서 널 리프 노드까지 도달하는 모든 경로에는 널 리프 노드를 제외하고 항상 같은 수의 블랙 노드가 있다.
마지막 조건을 다시 말해보면, 이 임의의 노드를 루트 노드로 설정하면, 레드블랙 트리의 black-depth(블랙 노드의 깊이)는 항상 일정하다는 말이다. 또한 바로 전 조건인 '레드 노드의 자식 노드는 언제나 블랙이다'에 의해 레드 노드가 연달아서 나올 수 없기 때문에 총 깊이는 블랙 노드의 개수를 [math(B)]라고 하면 최소 [math(\lg B)]에서 최대 [math(2\lg B)]로 제한된다(이래서 시간복잡도가 일정한 것).
이 때문에 레드블랙트리를 그림으로 그릴 때, 레드 노드를 높이에 영향을 주지 않는 왼쪽과 오른쪽으로 이어지도록 그리기도 한다.
역시 삽입과 삭제 시 경우에 따라 노드의 색 변환 또는 트리 회전[6]이 필요하며 구현은 꽤나 복잡하지만 실 사용에선 매우 효율적인 모습을 보인다. C++ STL의 set, map이 이 레드블랙 트리를 이용하여 구현되었다.[7]
또한 2-3-4 트리와 매우 유사하며 모든 red-black tree는 일대일 대응하는 2-3-4 트리가 있다(역도 참이다). 2-3-4 트리에는 노드 하나에 1~3개의 데이터가 들어간다. 이중 가운데의 데이터를 검은색으로, 좌, 우의 데이터를 붉은색으로 표기하면 red-black 트리와 같아진다.
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보다 훨씬 복잡하다.[9]
6. 관련 문서[편집]
이 문서의 내용 중 전체 또는 일부는 2023-12-23 02:06:35에 나무위키 트리(그래프) 문서에서 가져왔습니다.[1] 그렇지 않으면 순환참조가 되어 오류가 발생한다.[2] 이진 트리에서는 이것의 최댓값이 2로 제한된다.[3] 또한 자료구조의 트리는 rooted 트리의 일종이기도 하다.[4] 실제로는 심볼릭 링크 등의 기능이 존재하여 이상적인 트리는 아니다.[5] 실제로는 루트 노드가 하나가 아닌 경우가 많으므로 포레스트(forest)에 더 가깝다.[6] 최대 3회[7] 언어 자체에서 연관 배열(associative array)을 지원하는 경우 대부분 레드블랙 트리로 구현되어 있다.[8] 중학 수학에서는 정말 그렇게 불린다.(…) 원래 수학 교과 과정내에선 정확한 지식을 잘 안 알려주는 경우가 많다. 이 경우는 학생들의 인지 발달 수준을 고려하여 수학이라는 추상적인 개념을 좀더 직관적이고 친근하게 받아들이도록 서술된 것이다.[9] 트리뿐만 아니라 unlabled graph의 경우 label을 통해서 구분이 상대적으로 쉬운 labeled grpah와 달리 오로지 isomorphic을 이용해서만 그래프를 구분해야하므로, 경우의 수를 찾는것이 훨씬 어렵다.