[DiscreteMath]트리

📚기본사항

트리는 계층구조를 표현하기 위한 자료구조이고 그래프 종류 중 하나입니다. 또한 트리는 꼭지점 대신 노드라는 용어를 사용하고 각 노드는 자식 노드의 개수만을 차수로 가집니다.

노드의 차수에 따라 이진 트리와 m-원 트리로 나뉩니다. 이진 트리는 노드의 배열방법에 따라 힙과 이진 탐색 트리로 나뉘고 이진 탐색 트리는 노드 깊이에 따라 AVL 트리, BB 트리, 스플레이 트리로 나뉩니다. 또한 m-원 트리는 차수에 따라 트라이와 m-원 탐색 트리로 나뉘고, m-원 탐색 트리는 다시 B^* - 트리, B⁺ - 트리, 2-3 트리, 2-3-4 트리 및 레드-블랙 트리로 나뉩니다.

📄트리

트리는 사이클이 없는 단순 연결 그래프입니다. 하나의 노드로 이뤄진 트리는 사소한 트리(trivial tree)라고 하고 어떠한 노드도 없는 트리는 공백 트리(empty tree)라고 합니다.

📄루트 트리

루트 트리는 아래 조건을 만족하는 1개 이상 노드들의 유한집합입니다.

1. 루트라고 부르는 특정한 노드가 1개 존재한다.
2. 나머지 노드들은 m개의 서로 분리된 집합 T₁, T₂, …, T_m으로 나뉘고 T_i는 다시 루트 트리가 된다. T₁, T₂, …, T_m은 각각 노드들의 서브트리라고 합니다.

아래 트리의 루트는 A입니다. A의 서브트리는 B, C, D를 루트로 하는 트리입니다. 재귀적으로 B도 E, F를 서브트리로 가집니다. C는 서브트리를 가지지 않습니다.

트리는 상하 방향성을 가지고 있어서 방향 그래프로 표현할 수 있습니다. 이렇게 방향성을 가지는 트리를 방향 트리라고 합니다.

트리에서 루트는 임의로 선택되는 것이 아니고 진입차수가 0인 노드가 됩니다. 쉽게 말해 루트는 자기 자신으로 들어오는 변을 가지지 않습니다.

루트를 제외한 모든 노드는 진입차수가 1입니다. 트리에서 진입차수가 0 또는 1 값만 가지기 때문에 노드의 차수는 진출차수를 의미합니다.

📄트리의 주요 용어

만약 트리의 노드 N이 서브트리를 갖는다면

• 자식 노드: 각 서브트리의 루트
• 부모 노드: 부모 노드가 없는 최상위 노드, 트리의 시작점
• 형제 노드: 같은 부모 노드를 갖는 노드들
• 단말 노드(리프): 노드의 차수가 0인 노드들, 자식이 없는 노드들
• 내부 노드: 루트도 아니고 리프도 아닌 트리 안의 노드들
• 트리의 차수: 한 트리 내의 각 노드 차수 가운데 최대 차수
• 노드의 레벨: 루트로부터 그 노드 까지의 경로 길이
• 트리의 높이: 노드들 레벨 중 가장 큰 레벨.
• 트리의 무게: 리프 노드들의 수

https://namu.wiki/w/트리(그래프)

구조는 동일하지만 노드의 내용이 다른 두 개의 트리가 있다고 할 때, 이 둘은 닮았다고 합니다. 모두 공집합이거나 대응하는 서브트리들이 닮았다면 그 트리들은 같은 모양을 갖습니다.

• 트리의 성질
  n개의 꼭지점을 가지는 트리는 n-1 개의 변을 가진다는 성질이 있습니다. 이런 성질을 가지는 그래프가 있다면 그 그래프는 트리입니다.

📚이진 트리

📄이진 트리

이진 트리(Binary Tree)는 공집합이거나 모든 노드가 최대 2개의 서브트리를 가지는 루트 트리입니다. 쉽게 말해, 각각의 노드가 최대 두 개의 자식 노드를 가진다는 의미입니다. 각 노드의 서브트리는 왼쪽 서브트리와 오른쪽 서브트리로 구분되고 각각 최대 하나씩만을 가집니다. 왼쪽 서브트리만 두 개를 가지거나 오른쪽 서브트리만 두개를 가지는 노드가 존재하지 않습니다. 왼쪽 서브트리의 루트는 왼쪽 자식이라고 하고, 오른쪽 서브트리의 루트는 오른쪽 자식이라고 합니다.

https://en.wikipedia.org/wiki/Binary_tree

높이가 k인 이진 트리가 최대 가질 수 있는 노드의 수는 아래와 같습니다.

\[\sum_{i=0}^{h}2^{i} = 2^{h + 1} - 1\]

📄완전 이진 트리

완전 이진 트리(Complete Binary Tree)는 높이가 k인 트리에서 레벨 0부터 k-1까지 모든 노드가 채워져 있고 레벨 k에서는 왼쪽 노드부터 차례로 채워진 이진 트리입니다.

https://en.wikipedia.org/wiki/Binary_tree

완전 이진 트리는 같은 노드 수를 갖는 트리 중 최소 높이를 갖습니다. n개의 노드를 갖는 이진 트리의 최소 높이는 아래와 같습니다.

\[H_{min} = \lfloor \log_2 n \rfloor\]

• 경사 이진 트리(Skewed Binary Tree)
  높이를 가장 크게 구성하여 이진 트리가 한쪽으로 경사진 경우입니다.

📄포화 이진 트리

포화 이진 트리(Full Binary Tree)는 높이가 k인 트리에서 레벨 0부터 k까지 모든 노드가 채워진 이진트리입니다.

아래 그림은 완전 이진 트리가 아닌 포화 이진 트리입니다.

아래는 완전 이진 트리이면서 포화 이진 트리입니다.

https://www.geeksforgeeks.org/difference-between-full-and-complete-binary-tree/

📚이진 탐색 트리

이진 탐색 트리는 이진 트리의 노드가 키값을 가지고 있고 키들이 다음의 속성을 만족합니다.

1. 임의의 노드 N에 대해 N의 왼쪽 서브트리의 키값들은 N의 키값 k보다 작아야한다.
2. 임의의 노드 N에 대해 R의 오른쪽 서브트리의 키값들은 N의 키값 k보다 커야 한다.

키는 각 노드의 식별자로서 키값들은 서로 구별되어야 합니다. 특정 노드에 대한 탐색은 그 키값을 이진 탐색 트리에서 찾는 것을 의미합니다.

키 검색 과정은 이진 탐색 트리에서 루트 노드에서부터 자식 노드로 탐색해 가면서 주어진 키와 일치하는 노드를 찾아냅니다.

1. 탐색 노드를 루트 노드로 설정한다.
2. 탐색 노드와 주어진 키를 비교한다.
3. 일치한다면 키를 반환하고 탐색을 멈춘다.
4. 주어진 키가 현재 탐색 노드의 키보다 작다면 왼쪽 자식을 탐색 노드로 설정한다. 만약 왼쪽 자식이 없다면, 키 없음을 반환하고 탐색을 멈춘다.
5. 주어진 키가 현재 탐색 노드의 키보다 크다면 오른쪽 자식을 탐색 노드로 설정한다. 만약 오른쪽 자식이 없다면, 키 없음을 반환하고 탐색을 멈춘다.
6. 2 ~ 5단계 과정을 반복한다.

📚트리의 활용

📄신장 트리

그래프 G가 주어졌을 때 G의 모든 꼭지점을 연결하고 사이클이 존재하지 않는 G의 부분 그래프를 G의 신장 트리라고 합니다.

아래 그림은 4개의 꼭지점을 가지는 그래프에 대한 서로 다른 신장 트리입니다.

📄최소 신장 트리

그래프 G의 모든 변의 가중치의 합을 총 가중치라고 했을 때, G의 신장 트리 중에서 가장 작은 총 가중치를 가지는 트리를 최소 신장 트리라고 합니다.

• 크루스칼(Kruskal) 알고리즘
  
  1. 가중치의 오름차순으로 변을 정렬한다.
  2. 가장 작은 가중치의 변부터 차례대로 트리에 추가한다.(추가될 변이 사이클을 생성한다면 추가하지 않는다.)
  3. 모든 꼭지점이 연결될 때까지 단계 2를 반복한다.

• 프림(Prim) 알고리즘
  
  1. 임의의 꼭지점 하나를 트리에 추가한다.
  2. 트리의 꼭지점이 아니면서 트리와 연결된 꼭지점 중에서 가장 작은 가중치로 연결된 꼭지점을 추가한다.
  3. 모든 꼭지점이 연결될 때까지 단계 2를 반복한다.