트리 개관

• 계층 관계를 갖는 객체를 표현하기 위해 만들어진 자료구조
• 계층 관계가 없는 자료를 트리로 표현해서 같은 연산을 빠르게 할 수 있는 경우가 많다.

용어. 개념 정리

• 노드(node)와 간선(edge)로 이루어져 있다.
• 노드 간에는 상/하위 관계가 있다. 두 노드가 연결되었을 때는 한쪽이 상위, 다른쪽이 하위여야 한다.
• 상위는 부모(parent), 하위는 자식(child), 부모가 같은 노드는 형제(sibling)
• 부모와 부모들은 선조(ancestor), 자식과 그 자식들은 자손(descendant)
• 자식은 여러개 가질 수 있어도 부모는 하나만 가질 수 있다.
• 가장 윗쪽 노드는 **루트(**root;뿌리)
• 자식이 하나도 없는 노트는 리프(leaf;잎)
• 깊이(depth) :루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
• 높이(height): 가장 깊숙히 있는 노드의 깊이
• 서브트리 : 어떤 노드 t와 그 자손들로 구성된 트리

특징

• 재귀적인 속성이 있다. → 트리를 다루는 코드들은 대개 재귀 호출을 이용해 구현됨
• 다양한 표현 가능
  • 일반적으로 노드를 구조체/객체로 만들고 서로의 포인터로 연결함
  • 이진 트리는 포인터 배열 대신 left, right 만 속성으로 가져도 됨
  • 힙에서는 노드를 비울 일이 없어(꽉찬 트리) 배열로 표현
  • 상호 배타적 집합 구조 - 각 노드가 부모를 가리키는 포인터만 가짐

연산

• 대부분 재귀적으로 구현
• 자료 순회: 자료구조의 가장 기초적인 연산 중 하나
  • 루트를 방문하는 순서에 따라
    • 전위 순회
    • 중위 순회
    • 후위 순회
• 트리의 높이 구하기
• 최장 경로 찾기 : 최장 경로의 양 끝 노드가 항상 루트 아니면 잎이다!
  • 가진 긴 루트 - 잎 경로의 길이 = 높이
  • 가장 긴 잎-잎 경로의 길이
    • 가장 긴 루트의 서브트리의 높이 를 구한뒤 더해 나감
• 암시적으로 트리를 구성
  • 배열로 만들고 isChild(parent_index, child_index, d) 등 함수로 부모 자식 관계만 확인

종류

• 이진 트리
  • 검색 트리
    • 이진 탐색 트리 - 직접 구현할 일은 거의 없다.
    • 균형 이진 탐색 트리(BBST;Balanced Binary Search Tree)
      • Red black Tree
      • AVL tree
      • Treap (Tree + Heap) - 비교적 구현이 쉬운 BBST
  • 힙 - 최대(혹은 최소) 원소를 빨리 찾을 수 있음.
    • 우선순위 큐를 구현하기 위한 쉬운 방법
  • 구간 트리 - 구간에 대한 정보를 담고 있는 이진 트리. 구간 쿼리에 특화
    • 펜윅 트리 - 구간 트리의 궁극적 진화 (필요 없는 구간 정보 삭제)
• 트라이 - 문자열 특화 트리