[자료구조] 6. 트리, 힙, 우선순위 큐

선형 자료구조 → linked list(단방향, 양방향), 스택, 큐

• 모든 상황을 표현해 낼 수 없다는 단점

비선형 자료구조 → 그래프, 트리

[선형]이란 데이터 요소들이 순차적으로 나열되어있는 구조

[비선형]이란 상하관계, 계층적 구조

[보행]

특정 정점에서 다른 정점으로 갈 때 거치는 정점과 간선의 나열

[닫힌 보행] - 시작 정점과 종료 정점이 동일한 보행

[열린 보행] - 시작 정점과 종료 정점이 다른 보행

[경로] - 같은 정점 및 간선이 중복되지 않은 보행

[사이클] - 시작 정점과 종료 정점이 동일한 경로

• 닫힌 보행과 경로의 조건 모두 만족

 

[연결 그래프] - 모든 두 정점 사이에 경로가 존재하는 그래프

[그래프] - 정점과 간선으로 이루어짐 (연결되어 있는 대상 간의 관계를 표현하는 자료구조)

[트리] - 연결그래프이자 사이클이 존재하지 않는 그래프

[이진트리] - 모든 노드가 최대 2개의 자식 노드를 갖는 트리

[포화 이진트리] - 모든 레벨의 노드가 꽉 차 있는 이진 트리

• 내부 노드의 자식 노드가 2개여야 함
• 모든 리프 노드의 깊이가 같아야 함

[완전 이진트리] - 트리 높이-1 레벨까지의 노드는 모두 차 있고, 마지막 레벨에서는 노드가 왼쪽부터 순서대로 채워진 이진 트리.

즉, 트리의 최하단을 제외하고 포화 이진 트리를 이루며, 최하단의 모든 노드는 좌측에 몰려 있는 경우

[노드] - 개별 원을 트리에서는 노드라고 하고 그래프에서는 정점이라고 함

[루트 노드] - 부모 노드를 갖지 않는 노드

[리프l(leaf) 노드] - 자식 노드를 갖지 않는 노드

[내부 노드] - 리프 노드 제외한 모든 노드

[깊이 (Depth)] - 자신을 제외한 조상 노드의 개수

[높이 (Height)] - 리프 노드의 경우 : 0, 자식 노드 중 가장 큰 값 + 1

트리의 높이 : 루트 노드의 높이

• 포화이진트리의 높이에 따른 노드 개수 계산

포화이진트리는 모든 노드의 개수가 2개이므로 높이에 따라 노드의 개수를 계산할 수 있다.

→ 2^(n+1) -1

짝수는 될 수 없음. 음수만 가능

• 완전이진트리의 높이에 따른 노드 개수 범위 계산

높이 : h

최소 노드 : 2^h

( 최하단 제외 노드 : 2^h - 1…

( 최하단 노드 최소 1개 이상이어야 해서… 1

( 2^h - 1 + 1 = 2^n…

최대 노드 : 2^(n+1) - 1

• 이진트리의 높이에 따른 노드 개수 범위 계산

높이 : h

최소 노드 : h+1

최대 노드 : 2^(h+1) -1

• 이진트리 노드 수에 따른 높이 범위 계산

노드 : n

최소 높이 : n-1

최대 높이 : [log_2 (n+1) ] -1

• 이진트리 간선의 개수

노드 : n

간선 : n - 1

• 시간분석도
  • 이진트리최악 : O(n)
  • 평균 : O(log n)
  • 탐색, 삽입, 삭제의 경우
  • 완전이진트리
  • 모든 상황에서 O(log n)
  • 포화이진트리
  • 모든 상황에서 O(log n)

---

힙

 

• 완전이진트리 기반의 자료구조
• 인덱스를 이용하여 동적 배열을 통해 구현함

!! 완전 이진트리 기반이기 때문에 가능한 것 !!

[최대 힙] - 모든 부모 노드는 자식 노드보다 큰 값을 가짐

→ Up-heap : 새로운 원소 추가.. 후 부모 노드와 값 비교를 통해 스위치

(힙은 완전이진트리 기반이라, 최초 삽입 위치 고정)

→ Down-Heap : 루트 노드 제거

(완전이진트리의 규칙을 깨지 않도록, 최하단 최우측 노드를 루트 노드로 대체함… 후 더 큰 자식 노드와 값 비교를 통해 스위치)

[최소 힙] - 모든 부모 노드는 자식 노드보다 작은 값을 가짐

• 힙의 시간분석도
  • 삽입 : O(log n)
  • 삭제 : O(log n)
  • 힙 구성 : O(n)
  • 최댓갑/최솟값 탐색 : O(1)

---

우선순위 큐

[큐] - 선입선출(FIFO)의 자료구조

[우선순위큐] - 들어온 순서와 상관없이 우선순위가 높은 원소부터 나감

• 우선순위 큐의 시간복잡도
  • 삽입 : O(1)
  • 삭제 : O(n)
  • 우선순위의 최댓값을 직접 탐색해야 하므로

Q. 그럼 우선순위에 따라 append 하면 문제가 해결되는가?

A. 우선순위에 따른 append도 정렬 과정을 거치므로 O(n)의 시간복잡도를 가짐.. 결론은 아니다

그러나 !! 힙을 이용한 구현을 한다면 빠른 수행의 결과를 이룰 수 있음.

push할 때 올라가면서 높이만큼만 swap… O(h)=O(log n)

pop할 때 내려가면서 높이만큼만 swap… O(h) = O(log n)