<열혈 자료구조>
트리는 계층적 관계를 표현하는 자료구조이다.
자료구조는 근본적으로 무엇을 표현하는 도구이다.
트리의 구조로 이뤄진 무언가를 표현하기에 적절히 정의되어 있는가?
가지를 늘려가며 뻗어나간다.
1. 노드 : 트리의 구성요소 중 간선이 아닌 것
2. 간선 : 노드와 노드를 연결하는 연결선
3. 루트 노드 : 트리 구조에서 최상위에 존재하는 노드
4. 종단 노드 : 아래로 또 다른 노드가 연결되어 있지 않는 노드
5. internal 노드 : 단말노드를 제외한 모든 노드
이진트리
- 루트노드를 중심으로 두 개의 서브트리로 나눠져야 한다.
- 나눠진 두 서브트리도 모두 이진트리여야 한다.
- 노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합 노드가 존재하는 것으로 간주한다.
- 물론 공집합 노드로 이진트리의 판단에 있어서 노드로 인정한다.
모든 레벨이 꽉 찬 이진트리를 포화 이진트리라고 한다.
차고가곡 빈틈 없이 채워진 트리를 완전 이진 트리라고 한다.
트리가 완성된 이후부터는 그 트리를 대상으로 매우 빈번한 탐색이 이뤄진다.
완전 이진 트리 구조를 갖는 힙이라는 자료구조는 배열을 기반으로 구현한다.