데이터 구조 - 트리

카테고리

프로그래밍/소프트웨어 개발

서브카테고리

데이터 분석

대상자

• 프로그래밍 초보자 및 중급 개발자
• 데이터 구조와 알고리즘을 학습하는 학생 및 연구자
• 효율적인 데이터 관리와 검색 알고리즘 설계를 필요로 하는 개발자

핵심 요약

• 트리는 노드로 구성된 비선형 데이터 구조로, 루트 노드와 자식 노드 간의 계층적 관계를 통해 데이터를 저장
• 이진 탐색 트리(BST)는 모든 노드가 "왼쪽 자식 ≤ 현재 노드 < 오른쪽 자식"의 조건을 만족하며, 완전 이진 트리는 모든 레벨이 채워져야 하며, 완전 이진 트리는 2ᵏ-1 노드를 가짐
• 힙은 최소 힙과 최대 힙으로 구분되며, extract_min과 insert 연산은 O(log n) 시간 복잡도를 가지며, 트리의 균형은 검색 효율에 직접적인 영향

섹션별 세부 요약

1. 트리의 기본 정의

• 트리는 루트 노드가 있고, 각 노드는 0개 이상의 자식 노드를 가짐
• 사이클이 없으며, 노드의 데이터 타입과 순서는 유연
• 그래프 이론에서 루트 노드는 필수적이지 않지만, 프로그래밍에서는 일반적으로 사용

2. 이진 트리 vs 이진 탐색 트리(BST)

• 이진 트리는 각 노드가 최대 2개의 자식 노드를 가짐
• BST는 모든 노드가 "왼쪽 자식 ≤ 현재 노드 < 오른쪽 자식" 조건을 만족하며, 중복 값 처리 방식은 정의에 따라 달라짐

3. 이진 트리의 종류

• 완전 이진 트리: 모든 레벨이 채워져야 하며, 마지막 레벨은 왼쪽부터 채움
• 완전 이진 트리와 완전 이진 트리는 2ᵏ-1 노드를 가지며, 실제 구현에서는 드물게 사용됨
• 완전 이진 트리는 모든 노드가 0개 또는 2개의 자식을 가짐

4. 트리 순회 방법

• In-Order Traversal: 왼쪽 → 현재 노드 → 오른쪽 순서로 탐색 (BST에서 오름차순 순회)
• Pre-Order Traversal: 현재 노드 → 왼쪽 → 오른쪽 순서로 탐색 (루트가 항상 첫 노드)
• Post-Order Traversal: 왼쪽 → 오른쪽 → 현재 노드 순서로 탐색 (루트가 항상 마지막 노드)

5. 힙(Heap)과 연산

• 최소 힙: 각 노드가 자식 노드보다 작으며, extract_min 연산은 O(log n) 시간복잡도
• insert 연산은 요소를 끝에 삽입 후 부모와 교환하며 O(log n) 시간복잡도
• extract_min은 루트 노드를 제거한 후 마지막 요소를 루트로 이동 후 bubble down 수행

결론

• 트리 구조는 데이터의 계층적 관계를 효율적으로 표현하며, BST와 힙은 검색 및 우선순위 큐 구현에 꼭 필요한 데이터 구조임
• 트리의 균형 유지와 트리 순회 방식 선택은 알고리즘 성능에 직접적인 영향을 미치므로, 실제 구현 시 반드시 고려해야 함