Tree

트리

1. 트리는 비선형 자료 구조로 원소들 간에 1: n 의 관계를 가진다
2. 원소들 간에 계층 관계를 가지는 계층형 자료로, 상위 원소에서 하위 원소로 내려가면서 확당되는 트리(나무) 모양의 구조로 이루어진 유한 집합

노드

트리의 원소

트리는 한개 이상의 노드로 이루어진 유한 집합이며 다음 조건을 만족한다

1. 노드 중 최상위 노드를 root 라고 한다
2. 나머지 노드들은 n(≥0) 개의 분리집합으로 T1,...TN으로 분리될 수 있다. 이 T1,,,TN은 각각 하나의 트리가 되며(재귀적 정의) 루트의 부 트리(subtree) 라고 한다

용어정리

1. 형제 노드 : 같은 부모 노드의 자식 노드들
2. 조상 노드: 간선을 따라 루트 노드까지 이르는 경로이 있는 모든 노드들
3. 서브트리: 부모 노드와 연결된 간선을 끊었을 때 생기는 트리
4. 자손노드 : 서브트리에 있는 하위 레벨의 노드들
5. 차수(degree)
   • 노드의 차수: 노드에 연결된 자식 노드의 수(줄을 세면 된다)
   • 트리의 차수: 트리에 있는 노드의 차수 중에서 가장 큰 값 (노드의 차수 다 센다음에 max)
   • 단말노드(리프 노드): 차수가 0인 노드 → 자식이 없는 노드
6. 높이
   • 노드의 높이: 루트~노드의 선의 갯수 → 루트부터 한줄씩 아래로 내려가는 깊이. 노드의 레벨
   • 트리의 높이: 트리에 있는 노드의 높이 중 가장 큰 값. 최대 레벨

이진트리

차수가 2인 트리로, 각 노드가 자식 노드를 최대한 2개까지만 가질 수 있는 트리이다

노드

left child node 와 right child node로 이루어져있다 모든 노드들이 최대 2개의 서브트리를 갖는 특별한 형태의 트리이다

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

종류

1. 포화 이진트리 (Full Binary Tree) 모든 레벨의 노드가 포화상태로 차 있는 이진트리로, 높이가 h 일때, 최대의 노드 개수인 2^(h+1)-1의 노드를 가지며 루트를 1번으로 하여 2h+1 -1까지 정해진 위치에 대한 노드번호를 갖는다
2. 완전 이진트리(Completed Binary Tree) 높이가 h이고 노드의 수가 n개일때, 포화 이진트리의 노드 번호 1번부터 n번까지 빈자리가 없는 이진 트리
3. 편향 이진트리(Skewed Binary Tree) 높이 h에 대한 최소 개수의 노드를가지면서 한쪽 방향의 자식 노드 만을 가진 이진 트리 → 왼쪽 편향 이진트리와 오른쪽 편향 이진트리가 있다

배열을 애용한 이진 트리의 표현

1. 이진 트리에 각 노드번호를 부여
2. 루트의 번호 ==1
3. 레벨 n에 있는 노드에 대하여 오른쪽으로 2n부터 2n+1 -1 까지의 번호를 차례로 부여 규칙: 왼쪽: x2(%2) 오른쪽 x2 +1. 레벨 n의 시작 노드 : 2^n

편향 이진트리

각 노드 : 2^n -1 → 효율성 창렬 메모리 공간 낭비가 발생하고 새 노드를 삽입하거나 기존의 노드를 삭제할 경우배열의 크기가 변경이 어려워서 비효율적이다