[Data Structure] Tree 기본

트리의 개념

• 비선형 자료구조
• 계층적 관계를 표현하는 자료구조

트리의 특징

• 하나의 루트 노드를 가짐
• 루트 노드와 자식 노드는 0개 이상의 자식 노드를 가짐
• 트리는 노드를 연결하는 간선으로 이루어짐
• n개의 노드를 갖는 트리는 항상 2n - 1개의 간선을 가짐
• 모든 자식 노드들은 한개의 부모 노드만을 가짐
• 트리는 재귀가 존재하면 안됨

재귀 노드

• 트리는 사이클이 존재하면 안됨

사이클(cycle)

트리의 종류

1. 이진 트리

• 각 노드가 최대 두개의 자식을 갖는 트리

2. 완전 이진 트리

• 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리
• 마지막 레벨은 완전히 채워 있지 않아도 되나, 노드가 왼쪽에서 오른쪽으로 채워져야 함
• 마지막 레벨(L)에서 1 ~ 2L - 1개의 노드를 가질 수 있음

3. 전 이진 트리

• 모든 노드가 0 or 2개의 자식 노드를 갖는 트리

4. 포화 이진 트리

• 모든 레벨에 노드들이 전부 차 있는 트리
• 모든 노드가 0 or 2개의 자식 노드를 갖는 트리
• 트리의 노드 수가 2^h - 1 개여야 함 (h: hight)

5. 이진 탐색 트리

• 부모의 값이 왼쪽 자식 노드의 값보다 크다.
• 부모의 값이 오른쪽 자식 노드의 값보다 작다.
• 왼쪽, 오른쪽 서브 트리도 이진 탐색 트리다.
• 이진 탐색 트리의 노드의 값은 유일하다.

* 이진 탐색 트리는 추가로 따로 설명

 

 

해당되는 트리

이진 트리

완전 이진 트리

전 이진 트리

 

해당되는 트리

이진 트리

완전 이진 트리

 

 

해당되는 트리

이진 트리

완전 이진 트리

전 이진 트리

포화 이진 트리

 

해당되는 트리

이진 트리

 

 

 

트리 용어

• 루트 노드
  • 부모가 없는 노드. 트리에는 단 하나의 루트 노드만 존재
• 단말 노드
  • 자식이 없는 노드
• 내부 노드
  • 단말 노드가 아닌 노드
• 노드의 깊이
  • 루트 노드에서 특정 노드에 도달하기까지의 간선의 수
• 노드의 레벨
  • 트리의 특정 깊이를 가지는 노드의 집합
• 노드의 차수
  • 자식 노드의 개수
• 형제
  • 같은 부모를 가지는 노드들
• 간선
  • 노드를 연결하는 선