(자료구조) 트리

*트리

정점: V개

간선: V-1개

그렇다면 위 두 조건을 만족하는 것은 트리다???NO

O-O   O-O

O

이 처럼 왼쪽 세개는 다 연결되어 사이클을 이루고 나머지 두개는 따로 인경우가 있을 수 있다.

결국 3가지조건을 만족해야 한다.
1. 정점이 V개
2. 간선 V-1개
3. 모두 연결되어 있다.

<조상, 자손 개념>

자기자신도 조상,자손이 된다.

예를들어 5가 단말노드고 5->2->1(루트노드)일때,
5의 조상노드느 5,2,1 3개 모두 해당된다.


<이진트리 종류>
1. 포화 이진트리(Full Binary Tree)

잎 노드를 제외한 모든 노드가 자식을 둘씩 가지고, 또한 모든 잎 노드들이 높이가 같다.
가장 안정적인 구조이다.

2. 완전 이진 트리(Complete Binary Tree)

잎 노드들이 왼쪽부터 차근차근 채워지는 것이 특징.
트리를 이용한 검색에서는 완전한 모습에 가까울 수록 높은 성능을 보인다. 그러니 데이터를 배치할 때는 최대한 완전이진트리에 가깝게 배치한다.

3. 높이 균형 트리(Height Balanced Tree)

루트노드를 기준으로 왼쪽 하위트리와 오른쪽 하위트리의 높이가 1이상 차이나지 않는 트리

4. 완전 높이 균형트리

왼쪽 하위트리의 높이와 오른쪽 하위 트리의 높이가 같은 것