[기초] 자료구조 / 트리 (Tree)

 

트리 (Tree)

 

사이클이 없는 그래프를 트리라고 합니다.

 

따라서 정점이 V개 이면 간선은 V-1개를 가지는 성질이 있습니다.

 

 

 

루트 있는 트리 (Rooted Tree)

 

루트가 있는 트리로 아래 그림에서 1이 루트가 됩니다.

루트 부터 아래로 방향을 정할 수 있습니다.

 

이때 1은 2의 부모, 2는 4의 부모

 

2는 1의 자식, 4는 2의 자식, 3의 자식은 6과 7

 

4와 5는 형제, 2와 3도 형제

 

 

 

따라서 루트에 가까운 쪽이 부모가 됩니다.

부모가 없으면 루트, 자식이 없으면 단말정점(Leaf Node)이라 합니다.

같은 부모를 가지면 형제라 합니다.

 

 

깊이(Depth)

 

깊이는 루트부터의 거리를 말합니다. 루트의 깊이를 0으로 하거나 1로 합니다.

 

 

조상(Ancestor), 자손(Descendent)

 

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

 

위 그림에서 보면  1의 자손은 1, 2, 3, 4, 5, 6, 7이고, 5의 조상은 5, 2, 1

자기 자신을 포함하는 점을 주의해야 합니다.

 

 

 

 

 

 

이진 트리 (Binary Tree)

 

자식을 최대 2개만 가지고 있는 트리입니다.

 

---

 

트리의 표현

 

- 트리는 그래프이기 때문에, 그래프의 표현과 같은 방식으로 저장할 수 있다.

(정점이 V개 간선이 V-1개이므로 인접행렬사용은 비효율, 주로 인접리스트 사용)

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

-  부모가 0개인 경우는 트리의 루트인데, 이 경우 부모를 -1이나 0으로 처리하는 방식을 사용한다.

 

 

 

1. 트리의 부모만 저장하는 방식

 

이 방법은 부모를 찾을 때는 매우 좋은 방식, 자식을 찾을 때는 parent배열을 모두 돌아야 합니다.

 

 

2. 배열로 표현

 

이진 트리의 경우 배열로 표현 할 수 있습니다.

부모 노드의 번호가 x인 경우, 자식의 노드는 2x, 2x+1로 나타냅니다.

 

 

위 방법에서 만약 오른쪽 자식만 있는 경우,

 

배열이 256 크기가 필요한 아주 비효율적인 자료구조가 됩니다.

 

그래서 순서대로 다 채우는 이진트리에서만 이 방법을 사용하면 됩니다.

 

그래프의 저장방식을 사용하여 이진트리를 배열로 저장하면

 

A[i][0]에 i의 왼쪽 자식, A[i][1]에 i의 오른쪽 자식을 저장할 수 있습니다.