트리

정의

노드들이 에지를 통해 서로 연결되어 두 노드 사이의 경로가 정확히 하나만 존재하는 계층적 데이터 구조

용어

• 노드
  • Parent node
    • 노드의 상위 노드
  • Child node
    • 노드의 하위 노드
  • Root node
    • 트리의 최상위 노드 또는 부모 노드가 없는 노드
  • Leaf node
    • 트리의 최하위 노드 또는 자식 노드가 없는 노드
  • Sibling
    • 동일한 부모 노드를 같는 노드
• Edge
  • 두 노드를 연결하는 경로
• Level
  • 루트 노드에서 해당 노드까지의 경로의 간선(edge) 수
• degree
  • 각 노드의 자식 노드의 수
• Neighbour of a node
  • 해당 노드의 부모 또는 자식 노드

트리 구조의 동작

• 삽입(insert)
• 탐색(search)
• 삭제(delete)
• 순회
  • 전위 순회(preorder traversal)
  • 중위 순회(in order traversal)
  • 후위 순회(post order traversal)

장점

• 자료 검색에 효율적
  • O(log n)의 시간 복잡도
• 빠른 삽입/삭제
  • O(log n)의 시간 복잡도
• 많은 양의 정보를 쉽게 정렬 및 탐색
  • 계층적 데이터 구조
  • 재귀적 특성 (BFS)

단점

• 불균형 트리
  • 한 쪽으로 데이터가 치우친 트리의 경우 검색 시간이 O(n) 까지 증가
• 트리의 크기가 커질 경우 많은 메모리를 요구

참고자료

geeksforgeeks-tree