트리

<트리 계층구조>

 

트리란

트리는 간선과 정점으로 이루어진 자료구조이다.

 

 

트리를 아주 간단하게 요약하자면 다음과 같다...

트리는 꼭대기부터 아래까지 계층을 이루고 있고 루트를 제외하고 나머지 정점들은 나머지 노드와 하나씩으로만 연결이 되어있는 구조를 볼 수 있다.

 

 

트리의 구조를 자세히 살펴보면 다음과 같다...

제일 최상단에 존재하는 노드의 정점은 루트라고 부른다. 또한, 간선으로 이루어지는 노드의 정점들을 부모와 자식이라고 부른다. 자식이 없는 정점은 리프( leaf)이다.

 따라서, 상단의 그림의 리프는 총 4개이다.

Depth는 루트와 노드 사이의 거리를 뜻하며, Depth가 1인경우에는 상단의 자료에 따르면 총 3개가 존재한다는 것을 알 수 있다.

 

---

 

즉, 트리를 간단 명료하게 한번 더 정리를 하면, 무방향이면서 사이클이 없는 연결 그래프로 정의할 수 있다.

 

 

트리(Tree)의 다양한 명제는 다음과 같이 정리할 수 있다.

- 무방향이면서 사이클이 존재하지 않는 연결 그래프(Undirected Acyclic Connetced Graph)

- 연결 그래프이면서 임의의 간선을 제거하면 연결 그래프가 아니게 되는 그래프

- 임의의 두 점을 simple path(정점이 중복해서 나오지 않는 경로)가 유일한 그래프

- V개의 정점을 가지고 V-1개의 간선을 가지는 연결 그래프

- 사이클이 없는 연결 그래프이면서 임의의 간선을 추가하면 사이클이 생기는 그래프

- V개의 정점을 가지고 V-1개의 간선을 가지는 Acyclic(=사이클이 없는) 그래프

 

 

트리의 간단한 소개는 이정도로 마무리 하며, 트리를 활용한 DFS, BFS, 이진 트리의 구현은 다음 공부 시간에 더욱 알아보도록 하자!