[자료구조] 트리

1. 트리

---

트리(Tree)는 계층적인 구조를 표현하는 자료 구조로, 노드와 간선으로 이루어져 있습니다. 트리는 다양한 분야에서 활용되며, 중요성은 데이터 구조와 알고리즘 이론을 이해하는 데 필수적입니다.

2. 트리의 정의

---

1. 비어 있거나(노드의 개수가 0개), 노드의 개수가 1개 이상이며 방향 간선이 존재함.

2. 사이클이 없음

3. 모두 연결된 연결 그래프임

 

풀어쓰면 노드 끼리 모두 연결된 그래프이면서 사이클이 존재하지 않고 노드가 V개 일때, 간선이 V - 1인 것이 트리이다.

 

3. 트리의 구성 요소

---

노드(Node)

트리의 기본 단위로, 데이터를 저장하는 요소입니다. 각 노드는 값과 부가적인 정보를 가질 수 있습니다.

 

간선(Edge)

노드들을 연결하는 선으로, 부모 노드와 자식 노드를 연결합니다. 간선은 방향성을 가지며, 부모에서 자식으로 향하는 방향을 가집니다.

 

루트 노드(Root Node)

트리의 가장 상위에 위치한 노드로, 다른 모든 노드에게 상위 계층을 제공

 

부모 노드(Parent Node)

어떤 노드(자식 노드)의 바로 상위에 위치한 노드

 

자식 노드(Child Node)

어떤 노드(부모 노드)의 바로 하위에 위치한 노드

 

잎 노드(Leaf Node)

자식이 없는 노드로, 트리의 가장 끝에 위치한 노드

 

서브 트리(Subtree)

부모 노드로 부터 끊어진 노드로 이루어진 하부 트리

 

4. 트리의 특성

---

계층 구조

트리는 자연스러운 계층 구조를 형성하며, 부모와 자식 간의 관계를 통해 데이터를 효과적으로 표현합니다.

 

방향성

트리의 간선은 방향성을 가집니다. 즉, 간선은 한 방향으로만 이동할 수 있습니다.

5. 트리의 종류

---

트리는 여러 종류로 나눌 수 있습니다. 일반적인 트리, 이진 트리, 이진 탐색 트리 등이 있으며, 각각의 특성에 따라 적절한 용도에 사용됩니다.

 

나머지 종류에 대해서는 굳이 설명하지 않겠습니다.