트리의 기본 개념부터 이진 탐색 트리, 힙까지: 핵심 구조와 연산 심층 분석

핵심 기술

이 문서는 프로그래밍에서 필수적인 자료 구조인 트리의 근본적인 개념부터 시작하여, 특정 속성을 가진 이진 탐색 트리와 효율적인 데이터 관리를 위한 힙(특히 최소 힙)의 구조와 주요 연산(삽입, 최소값 추출)에 대해 깊이 있게 설명합니다.

기술적 세부사항

• 트리의 기본 정의: 노드로 구성되며, 루트 노드(일반적으로 존재하나 필수는 아님)를 중심으로 계층적인 구조를 이룹니다. 사이클이 없으며, 노드는 다양한 데이터 타입을 가질 수 있고 부모 노드에 대한 링크가 있을 수도 없을 수도 있습니다.
• 이진 트리 vs. 이진 탐색 트리 (BST):
  • 이진 트리: 각 노드가 최대 두 개의 자식 노드를 가질 수 있습니다.
  • 이진 탐색 트리 (BST): 모든 왼쪽 자손 노드의 값은 현재 노드 값보다 작거나 같고, 모든 오른쪽 자손 노드의 값은 현재 노드 값보다 큽니다. (동등 값 처리 방식은 정의에 따라 다를 수 있습니다.)
• 트리 종류:
  • 완전 이진 트리: 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있으며, 마지막 레벨은 왼쪽부터 채워집니다.
  • 포화 이진 트리: 모든 노드가 0개 또는 2개의 자식을 갖습니다. 즉, 자식 노드가 1개인 노드는 없습니다.
  • 완전 포화 이진 트리: 포화 이진 트리이면서 완전 이진 트리입니다. 모든 리프 노드가 동일한 레벨에 있으며, 해당 레벨은 최대 노드 수를 가집니다.
• 트리 순회 (Traversal):
  • In-Order: 왼쪽 자식 -> 현재 노드 -> 오른쪽 자식. BST에서 오름차순으로 노드를 방문합니다.
  • Pre-Order: 현재 노드 -> 왼쪽 자식 -> 오른쪽 자식. 루트 노드가 항상 첫 번째로 방문됩니다.
  • Post-Order: 왼쪽 자식 -> 오른쪽 자식 -> 현재 노드. 루트 노드가 항상 마지막으로 방문됩니다.
• 힙 (Heap):
  • 최소 힙 (Min-Heap): 완전 이진 트리 형태이며, 각 노드의 값은 자식 노드의 값보다 작거나 같습니다. 따라서 루트 노드가 최소값입니다.
  • 주요 연산:
    • 삽입 (Insert): 마지막 레벨의 가장 오른쪽 빈 공간에 새 요소를 추가한 후, 부모 노드와 비교하여 최소 힙 속성을 만족할 때까지 위로 올립니다(bubble up). O(log n) 시간 복잡도를 가집니다.
    • 최소값 추출 (Extract-Min): 루트 노드(최소값)를 제거하고, 마지막 노드를 루트 위치로 옮긴 후, 자식 노드들과 비교하여 최소 힙 속성을 만족할 때까지 아래로 내립니다(bubble down).