챕터7-1. 트리 | 개념 및 저장방법

트리의 개념

# 트리(Tree)
- 자료구조의 일종으로 '사이클이 없는 그래프'를 Tree 라고 함(이 이유로 임의의 두 정점 사이의 경로는 오직 1개이다)
   따라서, 정점의 개수는 V개이고, 간선의 개수는 V-1개 이다.
- 트리는 임의의 두 정점 간의 경로가 오직 1개이기 때문에, BFS를 이용하여 찾아낸 그 경로가 바로 최단거리가 된다.

- 주의할점이 있는데 
   (True) "Tree" 이면 "정점의 개수는 V개이고, 간선의 개수는 V-1개 이다."
   (False) "정점의 개수는 V개이고, 간선의 개수는 V-1개 이다." 이면 "Tree"이다.
   그 이유는 아래와 같은경우 정점이 6개이고, 간선이 5개인데 사이클이 있어서 트리라고 볼 수 없는 반례가 존재하기 때문이다.

하나의 Graph이나 왼쪽부분에서 사이클이 존재하기 때문에 Tree는 아니다.

   (True) "정점의 개수는 V개, 간선의 개수는 V-1개 이고, 모든 두 정점에 대해서 경로가 존재한다." 이면 "Tree"
   (True) "정점의 개수는 V개, 간선의 개수는 V-1개 이고, 임의의 두 정점 간의 경로는 1개씩 존재한다." 이면 "Tree"
                                                                                                    (바로 위의 True는 방향이 없는 것이어야 성립함)
- "총 n개의 도시로 이루어져 있는데, 도로가 n-1개다. 그리고 모든 두 도시 간의 경로가 존재한다." 라고 하면
   그 문제는 Tree로 보고 문제를 풀어도 된다.

그래프에서 사용되는 용어

# 루트가 있는 트리(Rooted Tree)
- 트리는 원래 루트가 없기 때문에 루트는 임의대로 정할 수 있음. 루트를 정해준 트리라면 Rooted Tree라고 부름.
- 루트를 정하게 되면 부모, 자식 관계가 형성이 되어 각각을 찾을 수 있게 된다. 
- 루트는 1번도 될 수 있고, 5번도 될 수 있고 아무나 될 수 있다.

# 부모(Parent) - 범위는 간선 하나까지만
- 루트부터 아래로 방향을 정할 수 있는데, 그러면 부모와 자식관계가 생긴다.
- 연결된 두 정점에서 둘 중 루트와 가까운 노드가 부모노드가 된다.
- Parent가 존재하지 않으면 그것은 Root이다.
ex) 1은 2, 3의 부모, 2는 4, 5의 부모, 3은 6, 7의 부모

# 자식(Children) - 범위는 간선 하나까지만
- 연결된 두 정점에서 둘 중 루트와 먼 노드가 자식노드가 된다.
ex) 2와 3은 1의 자식, 4와 5는 2의 자식, 6과 7은 3의 자식

# 단말 정점(Leaf Node 또는 Terminal Node)
- 자식이 없는 정점을 의미한다.
ex) 4, 5, 6, 7

# 형제(Sibling)
- 같은 부모를 가지면 형제이다.
ex) 2와 3은 형제, 4와 5는 형제, 6과 7은 형제

# 깊이(Depth)
- 루트에서 부터의 거리(루트의 깊이를 0으로 하는 경우는 0 1 2,,,가 되고 1로 하는 경우는 1 2 3 ,,,이 됨)

# 높이(Height)
- 깊이 중에서 가장 큰 값으로, 루트의 깊이를 어떻게 설정하냐에 따라 위 그림에서 2 또는 3이 될 수 있음.

# 조상(Ancestor), 자손(Descendent) - 범위는 루트를 넘기지 않는 그래프 전체
- p->q로 갈 수 있을 때, p가 q보다 루트에 가까우면 
   p는 q의 조상, 
   q는 p의 자손.

주의할 점은 조상과 자손을 구할 때, 아래와 같이 자기 자신도 포함시킨다는 점이다.

ex) 1의 자손은 1, 2, 3, 4, 5, 6, 7
          2의 자손은 2, 4, 5
          5의 조상은 5, 2, 1
          6의 조상은 6, 3, 1

# 이진트리
- 자식을 최대 2개만 가지고 있는 트리

트리를 저장하는 방법

방법1. 트리는 그래프이기 때문에, 그래프의 표현과 같은 방식으로 저장할 수 있다.
             트리는 정점이 V개이고, 간선이 V-1개 이기 때문에 인접행렬보다 인접리스트로 저장하는 것이 효율적이다.

----아래는 트리일 경우에만 가능한 방법이고, 방법1은 트리와 그래프에서 공통적으로 사용가능한 방법이다.----

방법2. 트리의 모든 노드는 부모를 하나 또는 0개만 가지기 때문에 부모만 저장하는 방식으로도 저장할 수 있다.
             그러나, 이 방식은 어떤 노드의 부모를 찾을 땐 O(1)이지만, 어떤 노드의 자식을 모두 찾을 땐 
             parent배열을 모두 뒤져야 하기 때문에 거의 O(V)가 걸려서 부모를 찾을 때만 좋은 방법이다.

방법3. 이진트리의 경우에는 1차원 배열로 저장할 수 있다. 
              1차원 배열에서 부모의 노드가 x인 경우에 왼쪽자식은 2*x, 오른쪽 자식은 2*x+1로 하여 각각을
               arr[x], arr[2*x], arr[2*x+1]에 저장하면 되는데, 이 방식은 왼쪽 자식 없이 오른쪽 자식만 쭉 있는 경우
               저장 공간의 낭비가 심하여 좋은 방법이 아니다.
               단, 위에서부터 차례로 채워지는 밸런스 맞는 트리의 경우는 이 방법도 좋은 방법이 된다.

방법4. 이진트리의 경우에는 2차원 배열로 저장할 수 있다. 
              arr[i][0]에 i의 왼쪽 자식을, arr[i][1]에 i의 오른쪽 자식을 저장하는 방식으로 인접 리스트와 비슷한 방법이나 
              잘 사용하지는 않는 방식이다. 그러나 앞으로 등장할 트리를 순회하는 문제에서 사용하였음. 나름 간편함.