트리(tree)

트리(tree)란?

• 트리는 계층적 구조를 가지는 비선형 자료구조이다. 순환(Cycle)이 없는 연결 구조이다.
• 트리는 루트(Root) 노드에서 시작하여, 자식(Child) 노드로 연결되는 노드들로 구성된다.
• 각 노드는 자식 노드를 가질 수 있으며, 노드 간 연결은 부모-자식 관계를 나타낸다. 또한, 부모 노드는 한개만 가질 수 있다.
• 노드의 개수가 N이면, 간선의 수는 항상 N-1개이다.

 

 

 

트리의 구성

 

 

• 루트(Root): 트리의 최상단 노드이다. 트리는 루트 노드에서 시작된다.
• 노드(Node): 트리의 각 요소를 나타낸다. 각 노드는 데이터와 자식 노드에 대한 포인터를 포함한다.
• 부모(Parent): 특정 노드의 바로 위에 있는 노드이다.
• 자식(Child): 특정 노드 바로 아래에 있는 노드이다.
• 리프(Leaf): 자식 노드가 없는 노드이다.
• 간선(Edge): 두 노드를 연결하는 선을 의미한다.
• 레벨(Level): 트리의 루트에서 특정 노드까지의 경로 길이를 의미한다. 루트 노드는 레벨 0이다.
• 깊이(Depth): 트리의 루트에서 특정 노드까지의 거리이다.
• 높이(Height): 트리의 가장 깊은 노드까지의 거리이다.

 

 

 

트리의 종류

 

• 이진 트리(Binary Tree):
  • 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 트리.
  • 왼쪽 자식(Left Child)과 오른쪽 자식(Right Child)으로 나뉜다.
  • 종류: 이진 탐색 트리(Binary Search Tree), 완전 이진 트리(Complete Binary Tree), 포화 이진 트리(Full Binary Tree).
• 이진 탐색 트리(Binary Search Tree, BST):
  • 이진 트리와 같이 최대 두개의 자식 노드를 가질 수 있음.
  • 부모-자식 간 대소관계가 있다. 왼쪽 자식 < 부모 < 오른쪽 자식
  • 효율적인 탐색, 삽입, 삭제가 가능하다. 균형잡힌 경우 시간복잡도 O(long n)
• 힙(Heap):
  • 완전 이진 트리.
  • 각 노드의 값이 자식 노드의 값보다 크거나 작은 특성을 가진다.
  • 종류: 최대 힙(Max Heap), 최소 힙(Min Heap)
• N진 트리(N-ary Tree):
  • 각 노드가 최대 N개의 자식 노드를 가질 수 있는 트리.
  • 이진 트리는 N진 트리의 특수한 경우입니다.
• 균형 트리(Balanced Tree):
  • 높이 균형을 유지하는 트리.
  • 균형을 유지함으로써 최악의 경우에도 효율적인 연산을 보장한다.
  • 종류: AVL 트리, 레드-블랙 트리

 

 

 

트리의 순회

• 전위 순회 (Pre-order Traversal): 루트 → 왼쪽 자식 → 오른쪽 자식
• 중위 순회 (In-order Traversal): 왼쪽 자식 → 루트 → 오른쪽 자식
• 후위 순회 (Post-order Traversal): 왼쪽 자식 → 오른쪽 자식 → 루트
• 레벨 순회 (Level-order Traversal): 레벨 단위로 왼쪽에서 오른쪽으로 순회

 

 

 

트리의 활용

• 데이터베이스
  일반적으로 데이터베이스의 인덱스는 B-트리/B+트리와 같은 구조로 구현된다.
  이는 트리 구조로 균형을 유지하며, 데이터 검색/삽입/삭제 연산을 효율적으로 수행할 수 있다.
• 파일시스템
  루트디렉토리에서 시작하여 하위 디렉토리와 파일이 트리 형태로 연결된다.
  계층적 구조로 표현하며, 파일 시스템의 효율적인 탐색/관리를 가능하게 한다.
• DOM 트리
  HTML(또는 XML) 문서는 DOM(Document Object Model) 트리로 표현된다.
  웹 브라우저가 HTML 문서를 이해하고 조작하는데 사용되며, 각 요소와 속성은 트리의 노드로 나타난다.
• 우선순위 큐(Priority Queue)
  힙(Heap)을 사용하여 우선순위 큐를 구현한다.
  작업 스케줄링, 다익스트라 알고리즘, 힙 정렬 등에서 중요한 역할을 한다

위 예시 외에도 트리는 계층적 구조 표현이 필요하거나, 효율적인 검색 / 삽입 / 삭제 연산이 필요할 때 적합하다.