트리

• 트리는 싸이클이 없는 무방향 연결 그래프이다.
  • 각 노드에는 최대 하나의 부모 노드가 존재한다.
  • 두 노드 사이에는 유일한 경로가 존재한다.
• 비선형 구조
  • 원소들 간에 계층관계, 1:N관계를 가진다.
• 차수 : 노드에 연결된 자식 노드의 수
• 높이 : 루트에서 노드에 이르는 간선의 수

1. 이진트리

• 모든 노드가 최대 2개의 서브트리를 갖는 형태의 트리
• 높이가 h인 이진트리의 최대노드 갯수는 2^(h+1)-1이며, 최소 갯수는 h+1이다.

1-1. 포화 이진트리

모든 레벨에 노드가 포화 상태로 채워져 있는 이진 트리

1-2. 완전 이진 트리

높이가 h이고 노드수가 n일때, 포화 인진 트리의 노드번호 1번부터 n번까지 빈자리가 없는 트리

1-3. 이진 탐색 트리

• 탐색 작업을 효율적으로 하기 위한 자료구조, 모든 원소는 서로다른 유일한 키를 갖는다.

• 왼쪽 서브 트리 > 루트노드 < 오른쪽 서브 트리

• 중회 순회하면 오름차순으로 정렬된 값을 얻어올 수 있다.

허프만트리, 세그먼트 트리(인덱스 트리)

힙

• 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위한 자료구조
• max heap : 루트 노드에 가장 큰 값이 저장된다.

• min heap : 루트 노드에 가장 작은 값이 저장된다.

• 힙은 루트에 알고자하는 값을 넣으면서 빼내므로 삭제 연산을 하면 루트부터 일어난다.

• 힙은 특별한 큐의 구현과 정렬이다.
• 우선순위 큐를 구현하는 가장 효율적인 방법은 힙을 사용하는 것이다.