[BK] 알고리즘 기초 - 트리

트리

(Tree)

- 사이클이 없는 그래프

- 정점의 개수: V

- 간선의 개수: V-1

루트 있는 트리

(Rooted Tree)

- 루트가 있는 트리

- 루트부터 아래로 방향을 정할 수 있음

용어

- 부모(Parent)

- 자식(Child)

- 단말 정점(Leaf/Terminal Node)

- 형제(Sibling)

- 깊이(Depth): 루트에서의 거리

- 높이(Height): 깊이 중 가장 큰 값

- 조상(Ancester), 자손(Descendent): 

p->q로 갈 수 있을 때 p가 q보다 루트에 가까우면 p는 q의 조상, q는 p의 자손

- 이진트리(Binary Tree)

트리의 표현

- 그래프 표현과 같은 방식으로 저장 가능

- 트리의 모든 노드는 0/1개의 부모를 가지기 때문에 부모만 저장하는 방식으로 저장할 수도 있음

- 이진 트리의 경우 배열로 표현

(1) 일차원 배열: 부모의 노드가 x인 경우 자식의 노드는 2*x, 2*x+1

(2) 이차원 배열: A[i][0]에 i의 왼쪽 자식, A[i][1]에 i의 오른쪽 자식 저장

트리의 순회

(Tree Traversal)

- DFS, BFS 사용 가능

- 트리에서만 사용할 수 있는 세 방법: 노드 방문을 언제 하는지의 차이

(1) 전위 순회(pre-order): 노드 방문 -> 왼쪽 자식 프리오더 -> 오른쪽 자식 프리오더

(2) 중위 순회(in-order): 왼쪽 자식 인오더 -> 노드 방문 -> 오른쪽 자식 인오더

(3) 후위 순회(post-order):  왼쪽 자식 포스트오더 -> 오른쪽 자식 포스트오더 -> 노드 방문

트리의 지름

(Diameter)

- 트리에 존재하는 모든 경로 중에서 가장 긴 것의 길이

- 탐색 2번으로 구할 수 있음

(1) 루트에서 모든 정점까지의 거리를 구해, 가장 먼 거리였던 정점을 A라 함

(2) A를 루트라고 하고 모든 정점까지의 거리를 구해, 이떄 구한 가장 먼 거리가 지름