본문으로 건너뛰기

2026-06-10 학습 일지

오늘 한 일​

  • 트리 자료구조 전체 개념 정리
  • 이진 트리 종류, BST, 힙, 균형 트리(RB트리), B트리/B+트리 학습

배운 내용​

트리 기본​

  • 계층적 구조 표현용 자료구조. 노드 + 간선(edge/link), 노드 간 상하 관계
  • 차수(degree): 노드가 갖는 자식 노드 수
  • 레벨(level): 루트에서 특정 노드까지 거치는 간선 수

순회 — 루트를 언제 방문하느냐 기준​

  • 전위(pre-order): 루트 → 왼쪽 → 오른쪽
  • 중위(in-order): 왼쪽 → 루트 → 오른쪽
  • 후위(post-order): 왼쪽 → 오른쪽 → 루트

이진 트리 종류​

  • 이진 트리: 자식 노드 2개 이하
  • 정이진 트리(full): 자식이 0개 또는 2개 (1개는 없음)
  • 완전 이진 트리(complete): 마지막 레벨 제외 모두 꽉 참, 마지막 레벨은 왼쪽부터

BST와 힙​

  • 이진 탐색 트리(BST): 왼쪽 서브트리 < 노드 < 오른쪽 서브트리 → 탐색 O(log n)
    • 단, 편향 트리(일렬)가 되면 최악 O(n)
  • 힙(heap): 완전 이진 트리. 최댓/최솟값 빠르게 찾기, O(log n)
    • 최대 힙: 부모 ≥ 자식 / 최소 힙: 부모 ≤ 자식
    • 우선순위 큐는 최대 힙으로 구현 → 루트가 항상 최고 우선순위

균형 트리 — BST 편향 문제 해결​

  • 자가 균형 BST: 좌우 서브트리 높이 균형 유지 (AVL, RB트리)
  • RB트리 4가지 조건
    1. 루트 = 블랙
    2. 리프 = 블랙
    3. 레드의 자식 = 블랙 (레드 연속 불가)
    4. 임의 노드 → 리프 경로의 블랙 수 동일
  • 삽입: 새 노드를 레드로 BST처럼 삽입 → 조건 위반 시 회전/색상 재지정으로 복구

대용량 입출력용 트리​

  • B트리: 다진 탐색 트리. M차 = 최대 자식 M개, 최소 ⌈M/2⌉개(루트·리프 제외)
    • 파일시스템/DB에서 디스크 입출력 횟수 최소화 목적
  • B+트리: 실제 데이터는 최하위 리프에만 저장, 내부 노드는 범위 분할용
    • 리프끼리 연결리스트로 연결 → 범위 탐색에 유리

기타​

  • 트라이(trie): 문자열 탐색/저장, 세그먼트 트리: 구간 연산, 펜윅 트리

내일 할 것​

  • 그래프 개념 학습 (인접 행렬/리스트, DFS/BFS)