Tree의 정의

1. 비선형 구조로 원소들 간에 1:n 관계를 갖는 자료구조,
2. 한 개 이상의 노드로 이루어진 유한 집합
3. 원소들 간에 계층관계를 가지는 자료구조
4. 상위 원소에서 하위 원소로 내려가면서 확장되는 Tree 모양의 구조

• 루트(Root node): 노드 중 최상위 노드.

• 형제 노드(Sibling node): 같은 부모 노드의 자식 노드들

• 조상(Ancestor node): 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들.

• 부트리(SubTree): 부모 노드와 연결된 간선을 끊었을 때 생성되는 Tree

• 자손 노드(Descendent node): 부트리에 있는 하위 레벨의 노드

• 단말 노드(Leaf node): 차수가 0인 노드, 자식 노드가 없는 노드

  • 7, 8, 6, 5, 11

• Node: Tree의 원소

  • 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11

• Edge: 노드와 노드(부모 노드와 자식 노드)를 연결하는 선

• 차수(degree): 노드에 연결된 사직 노드의 수
  • 1의 차수: 3
  • 3의 차수: 2
  • 9의 차수: 1
• Tree의 차수: Tree에 있는 노드의 차수 중에서 가장 큰 값
  • Tree의 최대 차수는 1의 차수인 3이므로 3

• 노드의 깊이(Depth): 루트에서 노드에 이르는 간선의 수, 노드의 레벨
  • 2의 높이는 1, 8의 높이는 3
• Tree의 높이(Height): Tree에 있는 노드의 높이 중에서 가장 큰 값, 최대 레벨
  • 8과 11의 높이가 3이므로 최대 레벨은 3이다.
• Tree의 레벨(Level): 트리 중 가장 긴 경로의 노드의 개수
  • $Level = Depth + 1$

Binary Tree

1. 모든 노드들이 2개의 부트리를 갖는 특별한 형태의 Tree
2. 노드가 자식 노드를 최대한 2개까지만 가질 수 있는 Tree
   • 왼쪽 자식 노드(Left child node)
   • 오른쪽 자식 노드(Right child node)
3. 레벨 i에서 노드의 최대 개수는 $2^i$개
4. 높이가 h인 Binary Tree가 가질 수 있는 노드의 최소 개수는 $(h+1)$개, 최대 개수는 $(2^{h+1}-1)$개

Full Binary Tree (전 이진 트리)

모든 노드가 0개 또는 2개의 자식을 갖는 Binary Tree

Complete Binary Tree (완전 이진 트리)

Perfect Binary Tree (포화 이진 트리)

모든 레벨의 노드가 포화 상태로 차 있는 Binary Tree

Skewed Binary Tree (편향 이진 트리)

높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만을 가진 Binary Tree

Left Skewed Binary Tree

Right Skewed Binary Tree

Array를 사용한 Binary Tree 구현

1. Tree의 노드 번호를 위와 같이 부여
2. 루트 번호를 1로 함
3. 레벨 n에 있는 노드에 대하여 왼족부터 오른쪽으로 $2^n$ $2^{n+1}-1$까지 번호를 차례로 부여

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

Binary Search Tree

1. 탐색작업을 효율적으로 하기 위한 자료구조.
2. 모든 원소는 서로 다른 유일한 키를 가짐.(중복을 허용하지 않는다.)
3. left child node < parent node < right child node
4. left sub tree와 right sub tree 모두 binary search tree이다.
5. 중위 순회하면 오름차순으로 정렬 된 값을 얻을 수 있다.

성능
1. 일반적으로 $O(h)$ h:height
1. 균형적으로 생성된 평균적인 경우 $O(\log n)$
1. skewed binary search tree와 같은 최악의 경우 $O(n)$

Heap

1. Complete Binary Tree에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해서 만든 자료구조
2. 중복된 값을 허용한다.

Max Heap

1. 키값이 가장 큰 노드를 찾기 위한 Complete Binary Tree
2. Parent node의 key > child node의 key
3. root node: 키값이 가장 큰 노드

Min Heap

1. 키값이 가장 작은 노드를 찾기 위한 Complete Binary Tree
2. Parent node의 key < child node의 key
3. root node: 키값이 가장 작은 노드