TIL 2026-03-12

3/12 - 오늘 학습 정리(챕터 3-7)

생성일: 2026년 3월 12일 오후 8:11

챕터 3-7 트리 개념 및 탐색

학습 목표

• 트리의 계층 구조와 핵심 용어(루트/부모/자식/리프)를 이해했다.
• 배열/인접리스트 기반 트리 표현 방식을 비교하며 구현 감각을 익혔다.
• 전위/중위/후위 순회를 문제 유형과 함께 정리했다.

핵심 개념 요약

• 트리는 비선형 자료구조로 계층적 데이터를 표현한다.
• 전위: 루트-왼-오 / 중위: 왼-루트-오 / 후위: 왼-오-루트
• 중위 순회는 BST에서 정렬된 순서 추출과 직결된다.

구현 관점

• 배열 기반: 완전이진트리 형태에서 인덱스 계산이 단순하다.
• 인접리스트 기반: 일반 트리/희소 구조에 유연하다.

vector<vector<int>> tree(n+1);
tree[parent].push_back(child);

이진 탐색 트리(BST) 요약

• 현재 노드 기준: 작은 값은 왼쪽, 큰(또는 크거나 같은) 값은 오른쪽에 배치.
• 균형이 잡히면 탐색/삽입/삭제가 빠르지만, 편향되면 성능이 떨어질 수 있다.

연산	평균	최악
탐색	O(log N)	O(N)
삽입	O(log N)	O(N)
삭제	O(log N)	O(N)

오늘 복기

• 순회 순서를 암기보다 “문제 목적”과 연결해서 이해하니 훨씬 정리가 쉬웠다.
• 전위/중위/후위 순회 템플릿 손코딩 1회
• BST 삽입+탐색 미니 문제 1개 풀이