<열혈 자료구조>

트리는 계층적 관계를 표현하는 자료구조이다.

자료구조는 근본적으로 무엇을 표현하는 도구이다.

트리의 구조로 이뤄진 무언가를 표현하기에 적절히 정의되어 있는가?

가지를 늘려가며 뻗어나간다.

 

1. 노드 : 트리의 구성요소 중 간선이 아닌 것

2. 간선 : 노드와 노드를 연결하는 연결선

3. 루트 노드 : 트리 구조에서 최상위에 존재하는 노드

4. 종단 노드 : 아래로 또 다른 노드가 연결되어 있지 않는 노드

5. internal 노드 : 단말노드를 제외한 모든 노드

 

이진트리

- 루트노드를 중심으로 두 개의 서브트리로 나눠져야 한다.

- 나눠진 두 서브트리도 모두 이진트리여야 한다.

- 노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합 노드가 존재하는 것으로 간주한다.

- 물론 공집합 노드로 이진트리의 판단에 있어서 노드로 인정한다.

 

모든 레벨이 꽉 찬 이진트리를 포화 이진트리라고 한다.

차고가곡 빈틈 없이 채워진 트리를 완전 이진 트리라고 한다.

 

트리가 완성된 이후부터는 그 트리를 대상으로 매우 빈번한 탐색이 이뤄진다.

 

완전 이진 트리 구조를 갖는 힙이라는 자료구조는 배열을 기반으로 구현한다.

+ Recent posts