[CS] Tree

노드로 이루어진 자료구조

꼭대기부터 아래로 갈 수록 점점 커지는 계층형 구조

- 반드시 하나의 root 노드를 가짐 -> 시작점

- 노드는 0개 이상의 자식 노드를 가짐 -> root만도 가능

- 트리는 노드와 노드를 연결하는 간선으로 구성됨

- 사이클 없는 비선형 구조 / 계층적 관계

- 노드는 특정 순서로 나열 될 수도 아닐 수도 있음

- 루트 노드를 중심으로 두 개의 서브 트리로 나누어지며 나누어진 두 서브 트리도 모두 이진 트리 (노드 없을 수 있음)

- 각 층별로 숫자를 매겨 트리의 레벨이라고 하는데, 루트 노드에서 1부터 시작하며 트리 최고 레벨을 트리의 높이라고 함

포화 이진 트리 Full Binary Tree
모든 레벨이 꽉 찬 이진 트리
- 레벨 별로 노드의 개수가 2의 n승으로 늘어나 일반적인 이진 트리에서 각 레벨 별 최대 노드 개수는 2^(k-1)이다
- 레벨 별 노드는 공비가 2인 등비 수열이라고 볼 수 있으므로 등비수열의 합으로 생각하면 높이가 h인 이진트리가 가질 수 있는 최대 노드 수는 2^(h-1)이라고 할 수 있다.
완전 이진 트리 Complete Binary Tree
왼쪽에서 오른쪽으로 순서대로 차곡차곡 채워진 이진 트리
- 마지막 레벨을 제외하고 모든 노드가 꽉 차있는 트리 (마지막 레벨이 꽉 안차더라도 왼쪽이 우선 채워져 있어야 함)
- 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리로 왼쪽이 비어있고 오른쪽이 들어가있는 트리는 완전 이진 트리가 아니다.
- 마지막 레벨의 노드 총 갯수는 1 ~ (2h-1)개
편향 이진 트리 Skewed Binary Tree
모든 노드가 부모의 왼쪽(이나 오른쪽) 자식이기 때문에 왼쪽(이나 오른쪽)으로 편향되어 있는 이진 트리

* 단어 설명

pear's devlog