[Data Structure] 트리(Tree)

본 포스트에서는 트리(Tree)에 대해 이야기해보려 합니다.

 

트리(Tree)는 컴퓨터 과학에서 매우 중요한 데이터 구조 중 하나로,

데이터의 저장 및 검색 효율성을 높이기 위해 다양한 응용 프로그램에서 사용됩니다.

 

트리가 무엇인지, 어떻게 구성되어 있는지 살펴보도록 하겠습니다!

---

트리의 개념

• 비선형 구조
• 원소들 간에 1:n 관계를 가지는 자료구조
• 원소들 간에 계층 관계를 가지는 계층형 자료구조
• 상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무)모양의 구조

---

트리 용어 정리

• 노드(node): 트리의 원소 (A, B, C, D, E, F, G, H, I, J, K)
• 간선(edge): 노드를 연결하는 선 (부모 노드와 자식 노드를 연결)
• 루트 노드(root node): 트리의 시작 노드 (A)

---

• 형제 노드(sibling node): 같은 부모 노드의 자식 노드들

---

• 조상 노드: 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들

---

• 서브 트리(subtree): 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리

---

• 자손 노드: 서브 트리에 있는 하위 레벨의 노드들

---

• 차수(degree)
  • 노드의 차수 : 노드에 연결된 자식 노드의 수
  • 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값
  • 단말 노드(리프 노드) : 차수가 0인 노드 (자식 노드가 없는 노드)

---

• 높이
  • 노드의 높이 : 루트에서 노드에 이르는 간선의 수 (노드의 레벨)
  • 트리의 높이 : 트리에 있는 노드의 높이 중에서 가장 큰 값 (최대 레벨)

---

트리의 종류

• 이진 트리(Binary Tree): 각 노드가 최대 두 개의 자식을 가지는 트리입니다.
• 이진 탐색 트리(Binary Search Tree, BST): 이진 트리의 일종으로, 왼쪽 서브트리의 모든 노드 값이 부모 노드보다 작고, 오른쪽 서브트리의 모든 노드 값이 부모 노드보다 큰 특성을 가집니다.
• 균형 이진 트리(Balanced Binary Tree): 이진 트리의 특수한 형태로, 트리의 높이를 최소화하여 삽입, 삭제, 검색 등의 연산이 O(log n)의 시간 복잡도를 가지도록 설계된 트리입니다. (AVL 트리, 레드-블랙 트리)
• 힙(Heap): 완전 이진 트리의 일종으로, 부모 노드가 자식 노드보다 항상 큰(작은) 특성을 가지는 트리입니다. (주로 우선순위 큐를 구현하는 데 사용됨)

 

더 구체적인 내용을 알고 싶으시다면, 아래 포스트를 참고하세요!

 

[Data Structure] 이진 트리 (Binary Tree)

[Data Structure] 이진 트리(Binary Tree)

[Data Structure] 이진 탐색 트리 (Binary Search Tree, BST)

[Data Structure] 이진 탐색 트리(Binary Search Tree, BST)

[Data Structure] 힙 (Heap)

[Data Structure] 힙(Heap)