(23.04.12) 자료구조/알고리즘3 - 큐, 트리, 힙

TIL은 그날 하루 본인이 어떤 공부를 하였는지 파악하기 위함입니다.
상세하게 기록하여 이후 본인이 어떤 공부를 어떻게 하였는지 파악할 수 있도록 하는 것이 중요합니다.

 

 

학습 주제

1. 큐, 환형 큐, 우선순위 큐의 ADT를 구현해본다

- Array 혹은 양방향 연결 리스트를 통해 구현

 

2. 트리,  이진트리, 이진탐색트리 의 ADT를 구현해본다

- 이진트리, 포화 이진 트리, 완전 이진 트리의 특징을 이해한다

- 트리의 재귀적 성격을 통해 이진트리를 활용해 구현

 

3. 힙과 최대/최소 힙의 ADT를 구현해본다

- 배열을 통해 구현

---

주요 메모 사항 

큐(Queues)

• 자료를 보관할 수 있는 선형 구조 (FIFO , 선입선출)
  • 한 쪽에서만 밀어넣고, 반대 편에서만 꺼내쓰는 구조
• 큐의 ADT
  • enqueue(x) - 원소를 큐에 추가 → O(1)
  • dequeue() - 큐의 맨 앞에 저장된 원소를 제거하고 반환
    • 배열로 구현시 O(n)
    • 양방향 연결 리스트로 구현시 O(1)
  • size() - 큐에 들어있는 원소의 수 → O(1)
  • isEmpty() - 규가 비어있는지 → O(1)
  • peek() - 큐의 맨 앞에 원소를 조회 O(1)

환형 큐(Circular Queues)

• 정해진 개수의 공간을 빙 돌려가며 사용하는 큐 구조
• 큐가 가득차면 원소를 넣을 수 없다
  • rear - 데이터를 넣는 공간
  • front - 데이터를 꺼내는 공간

우선순위 큐(Priority Queues)

• 큐가 선입선출을 따르지 않고, 원소의 우선순위에 따라 빠져나오는 큐 구조
• 환형 큐의 구현 방법 2가지
  • enqueue 할 때 우선순위 순서를 유지하는 방법
  • dequeue 시 우선순위 높은 것을 선택하는 방법
  • 후자는 모든 원소를 조회해야하지만, 전자는 모든 원소를 조회할 필요가 없어 보다 유리하다

---

트리(Trees)

• Node와 Edge를 이용하여 데이터의 배치 형태를 추상화한 구조
• 노드는 아래엔 다시 노드를 가질 수 있는 점에서 트리는 재귀적인 성질을 가지고 있다
• 트리의 ADT
  • 노드 관계
    • Root Node , Leaf Node, Internal Node (루트와 리프 노드가 아닌 노드)
    • Parent Node , Child Node, Sibling Node (형제)
    • Ancestor Node(조상) , Decendant Node (후손)
  • 노드의 Level
    • Root Node의 레벨은 0이다
    • Root Node의 Child Node는 레벨 1이다
  • 트리의 높이(Height)
    • 최대 Level + 1
  • 서브트리 (Subtree)
    • 두개의 노드로 이루어진 부분 트리
  • 노드의 차수(Degree)
    • 자식(서브트리)의 수
    • Leaf Node의 차수는 0이다

 

(1) 이진트리(Binary Tree)

• 모든 노드의 차수가 2이하인 트리
• 빈 트리도 이진 트리이다

 

 

(2) 포화 이진 트리(Full Binary Tree)

• 모든 레벨에서 노드들이 모두 채워져 있는 이진 트리
• 높이가 k면 노드의 갯수 → 2^k -1

 

 

(3) 완전 이진 트리(Complete Binary Tree)

• 높이가 k
  • 레벨 k-2 까지는 모든 노드가 2개의 자식을 가진 포화이진 트리
  • 레벨 k-1 에서는 왼쪽부터 순차적으로 채워져있는 이진 트리

 

이진트리의 traversal 순회연산

 1. 깊이 우선 순회 (DFT; )

• 중위 순회 (in-order) : left subtree → 자기자신 → right subtree
• 전위 순회 (pre-order) : 자기자신 → left subtree → right subtree
• 후위 순회 (post-order) : left subtree → right subtree → 자기자신

 2. 넓이 우선 순회 (BFS; Breadth First Traversal)

• 재귀적 방식은 효율적이지 않아 Queue를 통해 구현한다
  • Level 이 낮은 노드를 우선으로 방문한다 (root level)
  • Level 넘어가면 왼쪽부터 순회한다
  • 노드별 방문 직후 수행할 자식 노드의 정보를 기록한다 → Queue
  • Level 이 넘어간 경우 기록을 참고하여 왼쪽부터 순회한다

 

이진 탐색 트리

• 왼쪽 서브트리에 있는 모든 데이터는 현재 노드 값보다 작다
• 오른쪽 서브트리에 있는 모든 데이터는 현재 노드 값보다 크다
• 루트노트에서 탐색을 시작한다
• 이진 탐색 트리가 한쪽으로 쏠려있는 경우 선형탐색과 같은 수준의 복잡도를 가진다

이진 탐색 트리 vs 이진 탐색 배열

• 정렬된 배열보다, 데이터 원소를 추가하고 삭제하기 용이하다
• 왼쪽, 오른쪽 노드 정보를 기록해야 하기때문에 공간 소요가 크다

 

 

힙(Heaps)

• 이진 트리의 종류다 (이진 힙)
• 모든 루트 노드가 언제나 최댓값(최대 힙), 최솟값(최소 힙)을 가진다
• 완전 이진 트리여야 한다
• 완전 이진 트리이므로 노드의 추가/삭제는 마지막 노드에서만 진행한다

 

이진 탐색 트리 vs 힙

• 원소들은 완전히 크기순으로 정렬되어 있다 ↔ 느슨하게 정렬되어 있다
• 특정 키값을 가진 원소를 빠르게 찾는다 ↔ 상대적으로 느김
• 힙은 완전 이진 트리여야 한다는 조건이 따름

 

힙의 ADT

• init() : 빈 최대 힙을 생성
• insert(item) : 새로운 원소를 삽입 → 최악 복잡도 0(logn)
  • 트리의 마지막 자리에 원소를 삽입하고
  • 부모노드와 비교하여 위로 위로 이동한다
• remove() : 최대 원소(root node)를 반환하고 삭제 → 최악 복잡도 0(logn)
  • 루트 노드 제거
    • 트리 마지막 노드를 임시로 루트 노드 자리에 배치한 뒤
    • 자식과 비교해 아래로 이동
    • 자식이 둘 있다면 더 큰 값 아래로 이동
• 완전 이진 트리이므로 노드의 추가/삭제는 마지막 노드에서만 진행한다
• 배열을 통해 구현 가능
  • 0번 자리는 버리고 1부터 root 노드 정보를 담는다
  • 노드 번호 m을 기준으로
    • 왼쪽 자식의 번호 : 2*m
    • 오른쪽 자식의 번호: 2*m + 1
    • 부모 노드의 번호: m // 2

 

최대/최소 힙의 응용

• 우선 순위 큐 - enqueue시 느슨한 정렬을, dequeuqe 할 때 최댓 값 순서대로 추출
• 힙 정렬

 

---

공부하며 어려웠던 내용

힙 정렬 (Heap sort)