알고리즘) 트리(Tree)

# 트리 : 사이클이 없는 연결 그래프

1. 사이클이 없다

2. 연결되어 있다.

3. 그래프이다.

 

트리의 정점의 개수 = V,

트리의 간선의 개수 = V-1

(정점이 N개, 간선이 N개면 사이클이 1개만 존재하게 된다.)

 

cf) 트리라고 무조건 루트가 존재하는 것은 아니다.

루트는 정하기에 따라 달라진다.

 

# 트리에서의 부모(parent), 자식(child), 단말 노드(leaf node)

트리 예시

위 예시에서 

루트 = 노드 1로 정의했을 때,

노드 1의 자식 = 노드 2, 노드 3

노드 2의 부모 = 노드 1

(루트 노드(노드 1)의 부모는 존재하지 않는다.)

해당 트리의 단말 노드 = 노드 4, 5, 6, 7

노드 2의 형제(sibling) 노드 = 노드 3

 

# 깊이(Depth) : 루트로부터 노드의 거리

깊이는 정의마다 값이 다른데 일반적으로

root의 깊이를 0으로 설정하느냐, 1로 설정하느냐에 따라 달라진다

ex) 노드 4의 깊이 = (전자면) 2, (후자면) 3

 

# 높이(Height) : 단말 노드로부터의 거리

높이 역시 단말노드의 높이를 0으로 하느냐 1로 하느냐에 따라 달라진다.

 

# 조상(Ancestor), 후손(Descendent)

위 개념의 가장 큰 특징을 자신을 포함한다는 것이다.

ex) 노드 4의 조상 = 노드 4, 노드 2, 노드 1

노드 3의 후손 = 노드 3, 노드 6, 노드 7

 

 

# 이진 트리 (Binary Tree) : 자식을 최대 2개만 갖는 트리

(위 트리 예시는 이진 트리의 예시이기도 하다.)

 

# 포화 이진 트리 (Full Binary Tree) : 모든 단말 노드에서의 깊이가 동일한 이진 트리

포화 이진 트리의 전체 노드의 개수 = (2^h)-1

(h = 트리의 최대 높이)

위 트리 예시는 포화 이진 트리의 예시이기도 하다.

(단말 노드인 노드 4, 5, 6, 7의 깊이가 모드 3)

포화 이진 트리의 전체 노드 개수 공식

# 완전 이진 트리 (Complete Binary Tree) : 마지막 level(깊이)에서 오른쪽 leaf 노드의 일부가 없어진 형태

아래는 완전 이진 트리의 예시들이다.

완전 이진 트리의 예시

위 그림의 오른쪽 예시에서 노드 7이 추가되어 있다면, 해당 트리는 완전 이진 트리가 아니다.

 

 

# 트리의 구현

- 그래프 구현 방식으로 구현할 수 있다. (트리도 그래프의 일종이기 때문)

- root가 존재한다면, 트리만의 저장 방식을 사용할 수 있다.

1) 부모만 저장하는 방식 - Union Find에 사용

-> 모든 노드들의 부모를 배열에 저장하는 방식으로 구현한다.

(모든 노드는 부모 노드가 1개이고, 부모가 없는 노드는 root 노드 하나만 존재하기 때문에 사용가능한 방식이다.)

위 방식은 부모를 찾는것은 수월하지만 O(1)

자식을 찾는데는 O(노드개수) 만큼의 시간이 걸린다.

2) 완전 이진 트리 - Heap, Segment Tree 구현에 사용한다.

완전 이진 트리 구현 방식

완전 이진 트리의 경우에는 배열을 사용하여 트리를 구현하는 것이 가능하다.

3) 그냥(일반) 이진 트리 

구조체 또는 클래스를 사용하여 구현한다.

 

# 트리의 탐색

트리를 탐색하는데에도 DFS/BFS 방식을 사용할 수 있다.

(트리도 그래프의 일종이기 때문이다.)

1. DFS - 출력 순서 3가지 (노드 방문 처리 시점에 따른 차이)

   1) pre-order

   2) in-order

   3) post-order

 

 

트리 예시 - DFS

1) pre-order : 그래프의 DFS 방문 순서와 동일하다는 특징이 있다.

순서 :

노드 방문 ->

왼쪽 자식를 루트로 하는 서브 트리의 pre-order 출력 -> 

오른쪽 자식를 루트로 하는 서브 트리의 pre-order 출력

ex) A B D E C F G

2) in-order : Binary Searcj Tree의 삭제를 구현하는데 inorder successor가 사용된다는 특징이 있다.

순서 : 

왼쪽 자식를 루트로 하는 서브 트리의 in-order 출력 ->

노드 방문 ->

오른쪽 자식를 루트로 하는 서브 트리의 in-order 출력

ex) D B E A F C G

3) post-order : 자식의 노드의 정보를 이용하여 현재 노드에 정보를 저장할 때 사용하기 용이하다. (중요)

순서 :

왼쪽 자식를 루트로 하는 서브 트리의 post-order 출력 ->

오른쪽 자식를 루트로 하는 서브 트리의 post-order 출력 ->

노드 방문

ex) D E B F G C A

 

cf) pre-order, post-order 방식은 이진 트리가 아니여도 사용 가능하다.

그러나 in-order 방식에서는 왼쪽, 오른쪽 자식을 구분하는 기준이 없기 때문에 현재 노드를 언제 방문해야하는지 정해지지 않기 때문에 사용할 수 없다.

 

2. BFS - 트리에서의 최단 경로 탐색에 사용될 수 있다.

트리는 사이클이 존재하지 않는 그래프이다.

사이클이 존재하지 않는 그래프에서는 임의의 두 정점 사이에는 경로가 1개만 존재한다.

그렇기 때문에 트리에서의 두 정점 사이의 경로는 1개뿐이므로 해당 경로가 곧 최단 경로이며

BFS 탐색을 통해 이를 구할 수 있다.

 

 

# 트리의 지름

트리에 존재하는 모든 경로 중 가장 긴 경로를 트리의 지름이라고 한다.

구하는 방법 2가지 

1. 탐색 2번으로 구하기

탐색 1 : 임의의 정점 s에서 모든 정점까지의 거리를 구하고 최장 거리에 위치하는 정점을 u로 둔다.

탐색 2 : 탐색 1로 구한 정점 u에서 모든 정점 까지의 거리를 구하고 최장 거리에 위치하는 정점을 v로 둔다.

이 때, 정점 u와 v 사이의 거리가 트리의 지름이 된다.

2. post-order 이용하기

루트 노드를 v라고 할때, 트리의 지름을 v를 통과하는 경우, 통과하지 않는 경우로 총 2가지가 존재한다.

v를 통과하는 경우 : 트리의 지름은 각각의 자식에서 단말 노드까지의 거리 중 가장 긴 경로 2개를 이용하여 만들 수 있다.

v를 통과하지 않는 경우 : 각각의 자식을 루트로 하는 서브트리에서 다시 트리의 지름을 구하는 것으로 지름을 구한다.