[C++ Data Structure] 트리(Tree)

트리

트리(Tree)는 계층적(hierarchical) 데이터 구조로 여러 개의 노드(node)가 부모-자식 관계로 연결되어있는 비선형 자료구조입니다.
그래프의 한 종류입니다.

트리는 루트 노드(Root Node)에서 시작하며, 한 노드가 여러 개의 자식 노드(Child Node)를 가질 수 있지만, 하나의 부모 노드(Parent Node)만을 가질 수 있습니다.

트리에서 탐색은 어떠한 값을 발견하기 위한 행위이고, 순회는 어떻게 생겼는지 전체 구조를 파악하기 위해 모든 노드를 방문하는 것이라는 차이점이 있습니다.
트리의 순회에는 전위, 중위, 후위가 있습니다.

구성 요소

구성 요소는 다음과 같습니다.

• 노드(Node): 데이터와 자식 노드에 대한 정보를 가지는 요소입니다.
• 루트 노드(Root Node): 트리의 최상위 노드로, 부모가 없습니다.
• 부모 노드(Parent Node): 특정 노드의 상위 노드입니다.
• 자식 노드(Child Node): 특정 노드에서 가지를 뻗어 연결된 하위 노드입니다.
• 리프 노드(Leaf Node): 자식이 없는 노드입니다.
• 형재 노드(Sibling): 같은 부모를 가진 노드입니다.
• 간선(Edge): 노드 간의 관계를 나타내는 선입니다.
• 깊이(Depth)/레벨(Level): 루트에서 특정 노드까지의 거리입니다.
• 높이(Height): 특정 노드에서 가장 깊은 리프 노드까지의 거리입니다.
• 차수(Degree): 한 노드가 가진 자식 노드의 개수입니다.

트리의 종류

트리의 종류는 다음과 같습니다.

• 이진 트리(Binary Tree)
  • 포화 이진 트리(Full Binary Tree)
  • 완전 이진 트리(Complete Binary Tree)
  • 균형 이진 트리(Balanced Binary Tree)
• 이진 탐색 트리(Binary Search Tree, BST)
• AVL 트리(균형 탐색 트리)
• 힙(Heap)
• 트라이(Trie)