오늘 한 일
- 트리 자료구조 전체 개념 정리
- 이진 트리 종류, 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)
- 힙(heap): 완전 이진 트리. 최댓/최솟값 빠르게 찾기, O(log n)
- 최대 힙: 부모 ≥ 자식 / 최소 힙: 부모 ≤ 자식
- 우선순위 큐는 최대 힙으로 구현 → 루트가 항상 최고 우선순위
균형 트리 — BST 편향 문제 해결
- 자가 균형 BST: 좌우 서브트리 높이 균형 유지 (AVL, RB트리)
- RB트리 4가지 조건
- 루트 = 블랙
- 리프 = 블랙
- 레드의 자식 = 블랙 (레드 연속 불가)
- 임의 노드 → 리프 경로의 블랙 수 동일
- 삽입: 새 노드를 레드로 BST처럼 삽입 → 조건 위반 시 회전/색상 재지정으로 복구
대용량 입출력용 트리
- B트리: 다진 탐색 트리. M차 = 최대 자식 M개, 최소 ⌈M/2⌉개(루트·리프 제외)
- 파일시스템/DB에서 디스크 입출력 횟수 최소화 목적
- B+트리: 실제 데이터는 최하위 리프에만 저장, 내부 노드는 범위 분할용
- 리프끼리 연결리스트로 연결 → 범위 탐색에 유리
- 트라이(trie): 문자열 탐색/저장, 세그먼트 트리: 구간 연산, 펜윅 트리
내일 할 것
- 그래프 개념 학습 (인접 행렬/리스트, DFS/BFS)