큐 (Queue)와 트리 (Trees), 힙 (Heaps)

큐 (Queue)

• 자료를 보관할 수 있는 선형 구조
• 스택 (stack)과는 달리, 한 쪽에서 자료를 넣으면 자료를 넣은 쪽이 아닌 반대 쪽에서 자료를 뽑아야 함
  (자료를 넣는 것 : 인큐연산(enqueue), 자료를 빼는 것 : 디큐연산 (dequeue))
• 선입선출 형태의 자료구조 (FIFO : First in First out)
• 구현 방법
  • 배열 : python리스트와 메서드를 사용
  • 연결 리스트 : 양방향 연결 리스트 사용 (Doubly Linked List)
• 기초 연산 동작
  • size() - 현재 큐에 들어가 있는 데이터 원소의 수를 구함
  • isEmpty() - 현재 큐가 비어있는지를 판단
  • enqueue(x) - 데이터 원소 x를 추가
  • dequeue() - 큐의 맨 앞에 저장된 데이터 원소를 반환하고 제거
    • peek() - 큐의 맨 앞에 저장된 데이터 원소를 반환하고 제거하지 않음

---

트리 (Tree)

• 정점 (node)과 간선 (edge)을 이용하여 데이터 배치를 추상화한 자료구조
• 트리를 구성하는 모든 노드들은 부모와 자식 관계를 지니고 있음
• 트리의 높이(Height) = 최대 수준(level) + 1 (깊이라고 부르기도 함 (depth))
• 어떤 노드의 차수 (Degree) = 자식 (서브트리)의 개수
  노드의 degree = 0 이면 해당하는 노드는 leaf node

---

이진 트리 (Binary Tree)

• 모든 노드의 차수가 2이하인 트리
• 재귀적으로 정의할 수 있음 (루트 노드 + 왼쪽 서브트리 + 오른쪽 서브트리)
  (이때 왼쪽, 오른쪽 서브트리가 이진 트리 이면 해당 트리는 이진 트리이다)
• 트리가 빈 트리 (empty tree)이면 이진 트리라고 정의 가능
• 종류
  • 포화 이진 트리 (Full Binary Tree)
    • 모든 레벨에서 노드들이 모두 채워져있는 이진 트리
    • 높이 = k, 노드의 개수 = 2^k - 1인 이진 트리
  • 완전 이진 트리 (Complete Binary Tree)
    • 높이 k인 완전 이진 트리
    • 레벨 k - 2까지는 모든 노드가 2개의 자식을 가진 포화 이진 트리
    • 레벨 k - 1에서는 왼쪽부터 노드가 순차적으로 채워져 있는 이진 트리
  • 기초 연산
    • size() : 현재 트리에 포함되어 있는 노드의 수를 구함
    • depth() : 현재 트리의 깊이 (또는 height)를 구함
    • 순회(traversal)
      • 깊이 우선 순회 (depth first traversal)
        
        • 깊이 우선 순회
           - 중위 순회 (In-order Traversal) : left subtree -> 자기 자신 -> right subtree 순으로 순회
           - 전위 순회 (Pre-order Traversal) : 자기 자신 -> left subtree -> right subtree 순으로 순회
           - 후위 순회 (Post-order Traversal) : left subtree -> right subtree -> 자기 자신 순으로 순회
      • 넓이 우선 순회 (breadth first traversal) - 큐 (queue)를 사용하여 구현!
        • 원칙
           - 수준 (level)이 낮은 노드를 우선으로 방문
           - 같은 수준의 노드들 사이에는 부모 노드의 방문 순서에 따라 방문, 왼쪽 자식 노드를 오른쪽 자식 노드보다 우선 방문
          (level 0 -> level 1 -> level 2 ....)
          
          재귀적 방법이 적합한가? - 적합하지 않다!!

---

이진 탐색 트리

• 모든 노드에 대하여 아래의 성질을 만족하는 이진 트리
  (중복되는 값은 없는 것으로 가정)
  • 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작음
  • 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큼
• 이진 탐색과 비슷하게 배열을 이용
• 장점
  • 데이터 원소의 추가, 삭제가 용이
• 단점
  • 공가 (메모리) 소요가 크다
• 데이터의 표현 : 각 노드는 (key, value)의 쌍으로 구성
  (키를 이용하여 데이터 검색 가능)
• 기초 연산
  • insert(key, data) - 트리에 주어진 데이터 추가
  • remove(key) - 특정 원소를 트리에서 삭제
  • lookup(key) - 특정 원소 검색
  • inorder() - 키의 순서대로 데이터 원소 나열
  • min(), max() - 최소, 최대 키를 가지는 원소를 검색

---

힙 (Heap) 

• 이진 트리의 한 종류 (이진 힙 - binary heap)
• 조건
  • 루트 (root)노드가 언제나 최댓값 또는 최솟값을 가짐
    • 최대 힙 (max heap), 최소 힙 (min heap)
  • 완전 이진 트리여야 함
  • 재귀적으로도 정의가 가능하고, 느슨한 정렬을 하고 있음
    (자식 노드가 크고 작음이 왼쪽, 오른쪽 구분이 없음)
  • 기초 연산
    • __init__() - 빈 최대 힙 생성
    • insert(item) - 새로운 원소 삽입
    • remove() - 최대 원소 (root node)를 반환하고 삭제
  • 배열을 이용하여 트리의 표현이 용이
  • 장점 - 시간 복잡도가 log n을 가짐
  • 최대 / 최소 힙의 응용
    • 우선 수위 큐 (priority queue)
      
      • Enqueue 할 때 느슨한 정렬을 이루도록 함
      • Dequeue 할 때 최댓값을 순서대로 추출
    • 힙 정렬 (heap sort)
      • 정렬되지 않은 원소들을 아무 순서로나 최대 힙에 삽입
      • 삽입이 끝나면 힙이 빈 힙이 될 때까지 하나씩 삭제
      • 원소들이 삭제된 순서가 원소들이 정렬된 순서