이 레슨과 관련된 학습 키워드
컴퓨터 과학 & 프로그래밍 — 문제 해결의 도구 → 자료구조 — 효율적인 데이터 관리의 핵심 → 자료구조 — 효율적인 데이터 관리의 핵심 → 트리와 그래프
Binary trees, BST operations (search/insert/delete), four traversal methods, tree validation, serialization, and balance importance.
오늘은 트리라는 자료구조를 배워볼 거예요.
트리는 계층적 관계를 표현하는 비선형 자료구조예요.
그림 왼쪽 용어 정리 박스를 먼저 보세요.
루트는 최상위 노드로, 부모가 없는 유일한 노드예요.
노드는 데이터를 담는 단위이고, 간선은 노드 사이의 연결이에요.
부모와 자식 관계가 트리의 핵심이에요.
리프 노드는 자식이 하나도 없는 끝 노드를 말해요.
그림 가운데 트리 구조를 보세요.
A가 루트이고, B와 C가 A의 자식이에요.
D, E, F, G는 리프 노드로, 트리의 가장 아래에 있어요.
오른쪽 박스를 보면 깊이와 높이라는 중요한 개념이 있어요.
깊이는 루트에서 해당 노드까지의 거리예요.
높이는 해당 노드에서 가장 먼 리프까지의 거리예요.
A의 깊이는 0이고 높이는 2, D의 깊이는 2이고 높이는 0이에요.
트리의 핵심 성질은 N개 노드면 간선이 정확히 N-1개라는 거예요.
그리고 사이클이 없고, 루트에서 임의 노드까지 경로가 유일해요.
하단 박스를 보면 파일 시스템, HTML DOM, 조직도 모두 트리예요.
왜 트리가 중요할까요?
계층적 데이터를 배열이나 연결 리스트로 표현하면 관계가 사라져요.
트리를 쓰면 부모-자식 관계를 자연스럽게 유지할 수 있어요.
앞으로 배울 BST, 힙, 트라이 모두 트리의 변형이에요.
트리 용어를 확실히 외우는 것이 첫 번째 단계예요.
선생님: 노드가 7개인 트리의 간선 수는 몇 개일까요?
학생: 7-1이니까 6개요!
선생님: 맞아요. 그렇다면 루트 노드의 깊이는 항상 얼마일까요?
학생: 루트는 시작점이니까 0이요.
선생님: 정확해요. 그럼 리프 노드의 높이는요?
학생: 자식이 없으니까 0이요. 깊이와 높이가 반대 방향이네요!
선생님: 바로 그 점이 중요해요. 깊이는 위에서 아래로, 높이는 아래에서 위로 측정해요.