트리 탐색(DFS), 이진 트리 순회, 힙, 우선순위 큐

-DFS (깊이 우선 탐색)

: 루트 노드에서 출발하여 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 노드로 되돌아와서 다른 방향의 노드로 탐색을 계속 반복하여 결국 모든 노드를 반복하는 순회방법

: 가장 마지막에 만났던 갈림길의 노드로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 재귀적으로 구현하거나 후입선출 구조의 스택을 사용해서 구현한다.

 

-이진트리 순회

순회(traversal) : 트리의 노드들을 체계적으로 방문하는 것.

• 전위순회(preorder) : A - B - D - H - I - E - C - F - G
•      - 부모 노드 방문 후, 자식 노드를 좌, 우 순서로 방문한다.
• 중위순회(inorder) : H - D - I - B - E - A - F - G - C
•      - 왼쪽 자식노드, 부모 노드, 오른쪽 자식 노드 순으로 방문한다.
• 후위순회(postorder) : H - I - D - E - B - F - G - C - A
•     - 자식 노드를 좌우 순서로 방문한 후, 부모 노드로 방문한다.

 

-수식트리(=수식 이진 트리)

: 수식을 표현하는 이진 트리

• 특징
  • 연산자는 루트 노드이거나 가지 노드
  • 피연산자는 모두 잎 노드

이항 연산자 : +, -, *, /

피연산자 : 연산자의 연산의 대상

 

-힙(logN)

:완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 가장 작은 노드를 찾기 위해 만든 자료구조.

• 최대 힙(max heap)
  • 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
  • 부모 노드의 키 값 ≥ 자식 노드의 키 값 (모든 서브 트리 동일)
  • 루트 노드 : 키 값이 가장 큰 노드
• 최소 힙(min heap)
  • 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리
  • 부모 노드의 키 값 ≤ 자식 노드의 키 값
  • 루트 노드 : 키 값이 가장 작은 노드

-힙이 아닌 이진 트리의 예

1. 오른쪽 자식은 있는데 왼쪽 자식이 없을 경우(완전 이진 트리가 아니기 때문에)

2. 서로 다른 서브 트리가 최대힙, 최소힙으로 트리 관리 방법이 다를 경우

 

-우선순위 큐

: 우선순위를 가진 항목들을 저장하는 큐

• 특징
  • FIFO 순이 아니라 우선순위가 높은 순서대로 먼저 나가게 된다.
  • 노드 하나의 추가/삭제의 시간 복잡도가 O(logN)이고, 최댓값과 최솟값을 O(1)에 가져올 수 있다.
  • 우선순위 큐를 구현하는 가장 효율적인 방법은 힙을 사용하는 것이다.
  • 배열을 통해 트리 형태를 쉽게 구현할 수 있다.

-java.util.PriorityQueue()

• 원소들의 natural Ordering에 따라 Heap을 유지한다.(기본 오름차순)
• 따라서, 반드시 모든 원소는 Comparable 인터페이스를 구현해야한다.

-java.util.PriorityQueue(Comparator comparator)

• 명시된 Comparator의 구현에 따라 원소들의 순서를 유지한다.

 

-힙 정렬 - > O(NlogN) (밑2)

: 힙 정렬은 힙 자료구조를 이용해서 이진 트리와 유사한 방법으로 수행된다.

• 정렬을 위한 2단계
  1. 하나의 값을 힙에 삽입(반복).
  2. 힙에서 순차적(오름차순)으로 값을 하나씩 제거.
• 힙 정렬의 시간 복잡도-노드 하나의 삽입/삭제 연산은 O(logN)
• -따라서, 전체 정렬은 O(NlogN)
• -N개의 노드 삽입/삭제 연산