- 트리는 계층적 구조를 표현하는 데 사용되는 가장 중요한 자료구조입니다. 🌳
- 트리는 노드(데이터 단위)와 간선(연결)으로 구성되며, 사이클이 존재하지 않습니다. 🔗
- 주요 용어로는 부모/자식 노드, 루트 노드(최상단), 리프 노드(최하단), 차수(자식 수), 레벨(깊이), 높이 등이 있습니다. 🏷️
- 메모리에는 연결 리스트처럼 노드와 자식 노드의 위치 정보를 연속적으로 저장하여 구현할 수 있습니다. 💾
- 트리 순회는 모든 노드를 한 번씩 방문하는 연산으로, 전위(루트-왼쪽-오른쪽), 중위(왼쪽-루트-오른쪽), 후위(왼쪽-오른쪽-루트) 순회가 대표적입니다. 🚶♀️
- 이진 트리는 자식 노드가 최대 두 개인 트리로, 편향, 정, 포화, 완전 이진 트리 등 다양한 형태가 있습니다. ✌️
- 이진 탐색 트리(BST)는 왼쪽 자식은 작고 오른쪽 자식은 큰 값을 가지며, 탐색에 효율적이지만 편향될 경우 성능이 저하될 수 있습니다. 🔍
- 힙(Heap)은 완전 이진 트리의 일종으로, 최대/최소값 탐색에 특화되어 있으며 우선순위 큐 구현에 활용됩니다. ⛰️
- 자가 균형 이진 탐색 트리는 이진 탐색 트리의 편향 문제를 해결하기 위해 자동으로 균형을 맞추는 트리로, AVL 트리와 레드-블랙 트리(RB-Tree)가 대표적입니다. ⚖️
- 레드-블랙 트리는 노드에 색상(빨강/검정)을 부여하고 특정 규칙을 통해 트리의 균형을 유지하며, 운영체제, 프로그래밍 언어, 데이터베이스 등 광범위하게 사용됩니다. ❤️🖤
- B-트리는 다진 탐색 트리로, 한 노드가 여러 자식을 가질 수 있으며 파일 시스템이나 데이터베이스 인덱싱 등 대용량 입출력에 최적화되어 있습니다. 📚
- B+ 트리는 B-트리의 변형으로, 모든 실제 데이터는 리프 노드에만 저장되고 리프 노드들이 연결 리스트로 구성되어 범위 연산에 특히 유리합니다. ➕
Recommanded Videos
