트리(Tree)

트리(Tree)

---

노드(node)와 간선(edge)로 연결되어 있고 비선형 자료구조

 

트리의 용어

---

• 노드 (node)
  • 트리를 구성하고 있는 기본 요소
  • 노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있음
• 간선 (edge)
• 트리를 구성하기 위해 노드와 노드 사이를 연결하는 선
• 루트노드 (Root Node)
  • 트리 구조에서 최상위에 있는 노드
• 단말 노드(Leaf Node)
  • 하위에 다른 노드가 연결되어 있지 않은 노드
• 내부 노드 ( Internal Node)
  • 단말 노드를 제외한 모든 노드, 루프 노드도 포함
• 부모노드 (Parent Node)
  • 자식 노드를 가진 노드
  • I,J의 부모노드는 D 이다
• 자식노드 (Child Node)
  • 부모 노드의 하위 노드
  • 노드 D의 자식 노드는 I,J
• 형제 (Sibling)
  • 같은 부모 노드를 가지는 노드
• 깊이 (Depth)
  • 루트 노드에서 어떤 노드까지의 간선 수
• 높이 (Height)
  • 어떤 노드에서 리프 노드까지 가장 긴 경로의 간선 수

 

트리의 특징

---

• 하나의 루트 노드와 0개 이상의 하위 트리로 구성되어 있다
• 데이터를 순차적으로 저장하지 않기 때문에 비선형 자료구조이다
• 트리 내 또 다른 트리가 있는 재귀적 자료구조
• 임의의 노드에서 출발하여 자기 자신으로 되돌아 올 수 없다 비순환성

 

트리의 순회 방식

---

• 전위 순회 (Pre Order)
  • 각 루트를 순차적으로 먼저 방문 (Root -> 왼쪽 자식 -> 오른쪽 자식)
  • A -> B -> D -> I -> J -> E -> K -> C -> F -> G -> H
• 중위 순회 (in Order)
  • 왼쪽 하위 트리를 방문 후 루트를 방문 (왼쪽 자식 -> Root -> 오른쪽 자식)
  • I -> D -> J -> B -> K -> E -> A -> F -> C -> G -> H
• 후외 순회 (Post Order)
  • 왼쪽 하위 트리부터 하위를 모두 방문 후 루트 방문 (왼쪽 자식 -> 오른쪽 자식 -> Root)
  • I -> J -> D -> K -> E -> B -> F -> G -> H -> C -> A

 

트리의 종류

---

• 편향 트리 (Skew Tree)
• 이진 트리 (Binary Tree)
• 이진 탐색 트리 (Binary Search Tree)
• m원 탐색 트리 (m-way search Tree)
• 균형 트리 (Balanced Tree, B - Tree)