Related to: Data Structures
개요
Tree의 한 종류로, Child Node가 최대 두 개인 node들로 구성된 특수한 트리 구조입니다. 정이진트리(full binary tree), 완전이진트리(complete binary tree), 균형이진트리(balanced binary tree) 등이 있습니다.
핵심 개념
Binary Tree
Child Node가 최대 두 개인 node들로 구성된 Tree
Full Binary Tree
모든 레벨에서 노드들이 꽉 채워진(=잎새노드를 제외한 모든 노드가 자식노드를 2개 가짐) 이진트리
Complete Binary Tree
마지막 레벨을 제외한 모든 레벨에서 노드들이 꽉 채워진 이진트리
Balanced Binary Tree
모든 잎새노드의 깊이 차이가 많아야 1인 트리, 균형이진트리는 예측 가능한 깊이(predictable depth)를 가지며, 노드가 n개인 균형이진트리의 깊이는 log(n)을 내림한 값이 됩니다.
관련 개념
- Tree — 트리 자료구조 전반 개요
- Heap — 완전 이진트리 기반의 우선순위 큐
- Data Structure — 자료구조 전반
- 그래프와 트리(Tree and Graph) — 그래프와 트리의 비교
참조
https://ratsgo.github.io/data structure&algorithm/2017/10/21/tree/