[자료구조] 트리 (Tree)

트리란?

---

트리는 노드들로 구성된 자료구조로, 주로 계층적 구조를 표현하는 데 사용한다. 노드들간에 부모-자식 관계를 통해 트리를 구성한다.

트리: 이진트리

위 그림에서 선으로 연결된 관계를 부모-자식 관계라고 부른다.

 

트리 용어 정의

---

• 노드 (Node): 정보 항목과 다른 노드로의 가지(branch)로 구성된다.
• 루트 노드 (Root Node): 트리의 최상위 노드이며, 트리는 단 하나의 루트 노드만을 가질 수 있다.
• 부모 노드 (Parent Node): 특정 노드의 상위 노드를 말한다.
• 자식 노드 (Child Node): 특정 노드의 하위 노드를 말한다.
• 형제 노드 (Sibling Node): 동일한 부모 노드를 가지는 노드들을 말한다.
• 잎 노드 | 말단 노드 (Leaf Node | Terminal Node): 자식 노드가 없는 노드를 말한다. 즉, 차수가 0인 노드.
• 노드의 차수 (Degree of Node): 각 노드가 가진 가지의 개수
• 트리의 차수 (Degree of Tree): 노드들의 차수 중 최댓값을 말한다.
• 조상 (Ancestor): 루트 노드에서 해당 노드까지의 경로 상에 있는 모든 노드들을 말한다.
• 노드 레벨 (Node Level): 루트 노드는 레벨 0, 자식 노드의 레벨은 부모 노드의 레벨 + 1이다.
• 트리의 높이 | 트리의 깊이 (Height | Depth of Tree): 노드 레벨 중 최대값을 말한다.

 

트리의 특징

---

• 트리는 계층적 구조를 가진다.
• 트리 안에 트리가 존재한다.(서브트리가 존재)
• 하나의 루트 노드와 0개 이상의 하위 트리(또는 노드)로 구성되어 있다.
• 순환을 가지지 않는다.(순환을 가지면 그래프가 된다.)
• 모든 자식 노드는 하나의 부모 노드만을 가진다.
• 노드가 n개인 트리는 항상 n-1개의 간선을 가진다.

 

트리의 연산

---

• 삽입(Insertion): 새로운 노드를 트리에 추가한다.
• 삭제(Deletion): 트리에서 특정 노드를 삭제한다.
• 검색(Search): 트리에서 특정 값을 찾는다.
• 순회(Traversal): 트리의 노드를 특정 순서대로 방문한다. 전위 순회(Pre-order Traversal), 중위 순회(In-order Traversal), 후위 순회(Post-order Traversal), 레벨 순회(Level-order Traversal) 등이 있다.

 

트리의 응용 및 종류

---

• 파일 시스템: 디렉토리 구조는 트리 형태로 조직된다.
• 데이터베이스: 데이터베이스 인덱싱 구조는 B-트리 또는 B+트리를 사용한다.
• 컴퓨터 그래픽: 장면 그래프는 트리 구조로 표현된다.
• 네트워크: 라우팅 테이블은 트리 구조로 구성될 수 있다..
• 문서 객체 모델 (DOM): HTML 문서 구조는 트리 형태로 표현된다.
• 힙 (Heap): 힙 또한 트리로 된 자료구조이다.

트리의 종류는 포스팅이 길어지는 관계로 다음 포스팅에 올리도록 하겠다.

 

궁금한 것이나 잘못된 것이 있다면 댓글에 남겨주세요!