트리

Tree

• 하나 이상의 노드로 구성된 유한 집합.
• 루트: 특별히 지정된 노드, 루트에서 각 노드로 가는 경로는 단 하나
• 서브 트리: 루트를 제거 했을 때 좌 우로 나타나는 트리(루트 T의 서브 트리)
• n개의 노드를 가진 트리는 n-1개의 연결선을 가진다.
• no loop를 만족하는 그래프

root

• 주어진 그래프의 시작노드, 통상 트리의 가장 높은 곳에 위치한다.
• root로부터 그 밖의 모든 노드로 갈 수 있는 길이 단 하나 존재한다.

degree
어떤 노드의 차수는 그 노드의 서브 트리의 개수를 나타낸다.

leaf node, terminal node
차수가 0인 노드

자식 노드, 부모 노드, 형제 노드

internal node
루트도 아니고 리프 노드도 아닌 노드

ancestor
루트 부터 그 노드에 이르는 경로에 나타난 모든 노드

descendant
그 노드 부터 잎노드에 이르는 경로 상의 모든 노드

level
루트의 레벨을 0으로(혹은 1) 놓고 자손 노드로 내려가면서 하나씩 증가 한다.

height
트리에서 노드가 가질 수 있는 최대 레벨, depth 라고도 한다.

forest
서로 연결되지 않은 트리의 집합. 트리ㅔㅇ서 루트를 제거하면 얻을 수 있다.

---

방향 트리

• 방향이 있고 순서화된 트리.
• 선행자가 없는 루트라고 불리는 노드가 하나 있다.
• 루트에서는 모든 노드로 갈 수 있는 경로가 있다.
• 루트를 제외한 모든 노드들은 오직 하나의 선행자를 가진다.
• 노드의 후속자는 통상 왼쪽으로부터 순서화 되어 있다.
• 위에서 아래 방향의 방향트리는 굳이 화살표를 그리지 않아도 무방하다.

binary tree

• 트리의 모든 노드의 최대 차수를 2로 제한한 것
• 노드들의 유한집합으로서 공집합이거나 루트와 왼쪽 서브트리 오른쪽 서브트리로 이뤄진다.
• 이진트리가 레벨 i에서 가질 수 있는 최대 노드 수: $2^i$(혹은 $2^{i-1}$)
• 높이가 k인 이진 트리의 최대 전체 노드 수: $2^{k+1}-1$(혹은 $2^k-1$)
• 잎 노드 수 $n_0$, 차수가 2인 노드의 개수 $n_2$일 때: $n_0=n_2+1$

  트리 T가 n-ary tree란 뜻은 모든 중간 노드 들이 최대 n개의 자식 노드를 가질 때를 말하며, 특히 n이 2인 경우를 binary tree 라고 한다.

일반 트리를 이진 트리로 만드는 법
첫번째 자식 노드의 간선만 남기고 나머지 간선 제거
형제 노드를 오른쪽 자식 노드로 만든다.

skewed binary tree
왼쪽 또는 오른쪽으로 편향된 트리
모든 노드가 왼쪽과 오른쪽 중 한 방향으로만 서브트리를 가지고 잇는 트리

complete binary tree
높이가 k 일때 레벨1 부터 k-1까지 모두 차있고 k에서는 왼쪽 부터 차례로 차있는 이진 트리

full binary tree
모든 레벨에 노드가 꽉 차 있는 이진 트리
노드의 개수 $2^{k+1} -1$
잎 노드가 아닌 경우 2개의 자식노드를 가지며 트리의 높이가 일정한 경우

이진 트리의 표현
배열이나 연결리스트로 표현(구조체)

---

traversal

indorder traversal LDR
preorder traversal DLR
postorder traversal LRD

thread binary tree

1. 자식 노드가 없는 경우에 링크 필드를 널 포인터 대신 순회 순서상의 다음 노드를 가리키게 한다. 이 링크 필드를 스레드라고 한다.
2. 이진 트리의 순회 경로에 따라 현재 노드 직전에 처리한 노드, 즉 선행자에 대한 포인터를 현재 노드의 왼쪽 NULL링크 대신 저장한다.
3. 현재 노드 직후에 처리할 노드는 오른쪽 널 링크 대신에 저장한다.
4. 스레드 이진 트리에서는 재귀호출 대신 오른쪽 링크 필드의 포인터를 이용한다.
5. 순회방법을 정하고 1에따라 스레드를 설정한다.

binary search tree

이진 트리를 탐색용 자료구조로 사용하기 위해 크기에 따라 노드 위치를 정한 것

1. 모든 원소는 서로 다른 유일한 키를 갖는다.(?)
2. 왼쪽 서브트리에 있는 원소들의 키는 그 루트의 키보다 작다.
3. 오른쪽 서브트리에 있는 원소들의 키는 그 루트의 키보다 크다.
4. 서브 트리도 BST이다.

BST에서 삭제 연산 삭제할 노드의 차수가 1일 때는 삭제하고 자식노드를 연결
차수가 2일 때는 (왼쪽 서브트리의 가장 큰 값 혹은 오른쪽 서브트리의 가장 작은 값)을 후계자로 선택

balanced binary search tree, balanced tree

왼쪽 서브트리와 오른쪽 서브트리의 높이에 대한 균형 조건을 추가하여 정의한 트리

AVL Tree(Adelson-Velskii Landis tree)
왼쪽 서브트리의 높이 hL과 오른쪽 서브트리의 높이 hR의차이가 1 이하인 트리
왼쪽 서브트리< 부모노드< 오른쪽 서브트리의 크기 관계를 갖는다.
각 노드의 왼쪽 서브 트리 높이와 오른쪽 서브 트리 높이의 차이(HL-HR)를 노드의 균형 인수BF라 한다.
각 노드의 균형 인수로 -1 0 +1 만 가지게 함으로써 균형을 유지한다.

L1의 자식을 L2, L2의 자식을 L3라 하겠다.
LL유형: 불균형 발생 노드의 왼쪽 자식 노드와 자식의 왼쪽 자식 노드에 의해 왼쪽으로 치우침
L2의 오른쪽 자식 노드를 L1의 왼쪽 자식노드로 옮긴다.(L2의 오른쪽을 비우기 위해)
L1을 L2의 오른쪽 자식 노드로 올긴다.
RR유형: 불균형 발생 노드의 오른쪽 자식 노드와 자식의 오른쪽 자식 노드에 의해 오른쪽으로 치우침
L2의 왼쪽 자식 노드를 L1의 오른쪽 자식 노드로 옮긴다.
L1을 L2의 왼쪽 자식 노드로 옮긴다.
LR유형: 불균형 발생 노드의 왼쪽 자식 노드와 자식의 오른쪽 자식 노드에 의해 오른쪽으로 치우침
L2와 L3 구간에 RR
L1에 대해 LL
RL유형: 불균형 발생 노드의 오른쪽 자식 노드와 자식의 왼쪽 자식 노드에 의해 오른쪽으로 치우침
L2와 L3 구간에 LL
L1에 대해 RR

Heap
완전 이진 트리에 있는 노드 중키 값이 가장 큰 노드나 작은 노드를 찾기 위해 만든 자료구조
Max Heap: 부모노드의 키값이 자식노드의 키값보다 항상 크거나 같다
Min Heap: 부모노드의 키값이 자식노드의 키값보다 항상 작거나 같다
히프는 일반적으로 최대히프를 뜻한다.
삽입연산: 완전 이진 트리의 조건을 만족하도록 다음 자리를 확장한다.
부모 노드와 크기 조건이 만족하도록 위치를 찾는다.
삭제 연산: 루트에 있는 원소를 삭제한다.
마지막 노드를 루트로 옮긴다.
자식 노드와 크기 조건 비교

spanning tree (생성트리, 신장 트리)

• 그래프 G에서 모든 노드들을 포함하는 트리
• 비용(cost)은 트리 연결선의 값을 모두 합한 값

MST (Minimum Spanning Tree)
최소한의 비용을 가지는 생성 트리

Prim's algorithm

• 주어진 가중 그래프 G=(V,E)에서 V={1, 2, ..., n}

1. 노드의 집합U를 1로 시작
2. $u \in U, v \in V-U$일 때 $U$와$V-U$를 연결하는 가장 짧은 (u,v)를 찾아서 v를 u에 포함. 이때 (u,v)는 사이클을 형성하지 않아야 한다.
3. 위 과정을 U=V까지 반복

Kruskal's algorithm
주어진 weight gtaph G=(V,E) 에서 V={1, 2, ..., n}
1. T를 연결선의 집합이라고 할 때 T를 공집합으로 둔다
2. 연결선의 집합 E를 비용이 적은 순서로 정렬
3. 가장 최소값을 가진 연결선 (u,v)를 차례로 찾아서 사이클을 이루지 않으면 T에 포함시킨다.
4. 3의 과정을 |T|=|V|-1 까지 반복한다.

Huffman code

• 알파벳의 열로서 이루어진 메시지가 있고 각 메시지의 영문자가 독립적이고 위치에 관계없이 어떤 정해진 확률로 나타날때 0과 1로 코드화 하는 방법
• 어느 영문자의 코드도 다른 영문자 코드의 접두어로 표현되면 안된다.

1. 가장 낮은 확률을 가진 두문자 a,b를 선택하여 가상의 다른 문자 x로 대치한다.
2. x가 나타날 확률은 a, b를 합한 것
3. 위의 과정을 반복하여 최종확률이 1이 될때 까지 계속한다.
4. 최종 트리가 완성되면 서브 트리의 왼쪽에 0 오른쪽에 1을 부여한다.