트리(이진트리)

---

---

트리의 개념

• 비선형 구조
• 원소들 간의 1:N 관계를 가지는 자료구조
• 원소들 간에 계층 관계를 가지는 계층형 자료구조
• 상위 원소에서 하위 원소로 내려가면서 확장되는 나무모양 구조

 

트리 정의

• 노드 (node) - 트리의 원소
• 한개 이상의 노드로 이루어진 유한 집합이며 다음 조건을 만족한다
  • 노드 중 최상위 노드를 루트라 한다
  • 나머지 노드들은 n개의 분리 집합 T1…TN으로 분리될 수 있다.
• 이들 T1…TN은 각각 하나의 트리가 되며(재귀적 정의) 루트의 부 트리(subtree) 라 한다.

---

이진트리

이진 트리란 차수가 2인 트리이고 각 노드가 자식 노드를 최대 2개까지 가질 수 있는 트리이다.

모든 노드들이 최대 2개의 서브트리를 갖는 특별한 형태의 트리

이지트리 예시

 

특성

높이 1에서의 노드의 최대 개수는 2^i 개

높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1)개가 되며, 최대 개수는 (2^h+1-1)개가 된다.

 

포화 이진 트리

모든 레벨에 노드가 포화상태로 있는 이진트리이다 높이가 h일때 최대 노드의 개수를 가지고 있다.

포화이진 트리

 

편향 이진 트리

높이가 h에 대한 최소개수의 노드를 가지는 트리

한쪽 방향의 자식 노드만을 가진다.

편향 이진 트리

---

이진 트리의 표현

 

배열

• 이진 트리의 각 노드 번호는 루트 노드 부터 마지막 노드 까지 그림과 같은 순서로 부여
• 루트 노드는 1부터 시작

 

※ 노드 번호의 성질

• 노드 번호가 i인 노드의 부모 노드 번호 = i / 2
• 노드 번호가 i인 노드의 왼쪽 자식 노드 번호 = 2*i
• 노드 번호가 i인 노드의 오른쪽 자식 노드 번호 = 2*i+1