CH02 : 데이터 추상화와 기본적인 자료구조

Abstract Data Type (ADT)

ADT란 추상자료형으로, C++의 class와 비슷한 개념이다. ADT 동작과 그 설명을 기반으로 알고리즘을 설계하고, 정확성을 증명한다.

ADT를 정의하기 위해선 다음의 것들을 명시해야 한다.

1. 자료구조가 저장할 데이터 명시
   • ex. queue면 front, near 등
2. 지원하는 함수 명시
   • ex. insert, delete 등
3. 동작 설명
   • what은 설명하고, how는 설명하지 않는다. 즉 무엇을 수행하는지는 설명하지만, 어떻게 수행되는지는 설명하지 않는다.
4. error 처리 명시

Tree

Tree 용어

• root [루트] : 트리의 최상위 노드. 부모가 없는 노드라고도 한다.
• node의 degree [차수] : 자식의 수. 비어있지 않은 subtree의 수라고도 한다.
• external node(leaf) [외부노드, 리프] : 자식이 없는 노드. degree가 0인 노드라고도 한다.
• internal node [내부노드] : 자식이 있는 노드. degree가 양수인 노드라고도 한다.
• node x의 ancestor [조상] : x에서 root로 가는 길의 모든 노드들. x(본인) 포함.
• node의 descendant [후손] : ancestor의 반대. 
• node x를 root로 갖는 subtree [서브트리] : x를 root로 갖고, x의 descendant를 포함하는 subtree. 
  • root를 꼭 지정해 줘야 함에 유의!
• node의 depth [깊이] : 부모의 depth+1
  • root의 depth는 0
• tree의 level [레벨] : 같은 depth에 존재하는 모든 노드들
• tree의 height [높이]  : depth의 최댓값
  • node의 height : 해당 노드를 root로 갖는 subtree의 height

Binary Tree ADT (이진 트리)

• 이진 트리 T는 노드라 불리는 원소를 포함하고, hierarchical structure(계층적 구조)이며, 아래를 만족하는 집합이다.(혹은 empty 집합이거나.) (참고. 자료구조는 empty여도 자료구조다. 즉 비어있는 자료구조(ex. empty tree)가 존재할 수 있다.)
  1. root라 불리는 노드 r이 있다.
  2. r을 제외한 노드들은 두 개의 독립적인 subset L, R로 나뉜다. 각각은 이진 트리이다. 
     1. L은 T의 left subtree, R은 T의 right subtree이다.
• 이진 트리 T는 다음의 특성을 가진다.
  1. depth d에 대하여 해당 depth의 노드 수 상한은 $2^{d}$이다.
  2. height h에 대하여 총 노드 수 상한은 $2^{h+1} -1$이다. 
  3. n개의 노드를 가질 때, height의 하한은 $ \left \lceil \log \left(n+1 \right)\right \rceil -1$이다.
     • 이에 따라 $h \in \Omega \left( \log n \right)$
       
       • complete binary tree의 height에선, $h \in \theta \left( \log n \right)$

  4. 

Stack ADT

• stack은 linear structure(선형적 구조)로, top이라 불리는 한쪽 끝에서 삽입과 삭제가 이루어진다. LIFO(Last In, First Out)을 따른다.
• 연산
  • push, pop, top, size, empty
• 구현
  • array - O(1) time, O(array size) space가 쓰인다.
  • linked list - O(1) time, O(#element) space가 쓰인다.

Queue ADT

Queue

•  queue는 linear structure로, 삽입은 rear(back)이라 불리는 한 쪽 끝에서, 삭제는 front라 불리는 다른 쪽 끝에서 이루어진다. FIFO(First In, First Out)을 따르며, 엄밀히 말하자면 FIFO Queue이다.
• 연산
  • enqueue, dequeue, size, empty, front
• 구현
  • array - O(1) time, O(array size) space가 쓰인다.
    • 배열로 구현 시 circular array 형태로 구현해야 함에 유의! 
  • linked list - O(1) time, O(#element) space가 쓰인다.

Priority Queue

• 원소의 수가 해당 원소의 우선순위에 따라 결정되는 queue이다.
  • FIFO queue는 그 우선순위를 '삽입 시간'으로 설정한 것.
• 두 개의 관점이 있다.
  • cost viewpoint (비용 측면) : 작은 우선순위가 높다.
  • profit viewpoint (이익 측면) : 큰 우선순위가 높다.
• 연산 
  • insert, removeMin(removeMax), min(Max), size, empty
  • PQ 구현에 따른 연산 수행 시간
    •  

      	unsorted sequence	sorted sequence	heap
      insert	O(1)	O(n)	O(log n)
      removeMin(removeMax)	O(n)	O(1)	O(log n)
      min(Max)	O(n)	O(1)	O(1)

Union-Find ADT for Disjoint Sets

Union-Find, Disjoint Set이라고도 부른다.

• union, find라는 두 개의 핵심 동작으로 구성된다.
  • union operation을 통해 두 개의 독립된 집합은 합쳐질 수 있다. 
    • set id가 s인 집합과, t인 집합에 대하여 $s\neq t$일 때, s 혹은 t의 set id를 가지는 하나의 집합으로 합쳐질 수 있다. 
  • find operation을 통해 특정 원소의 set id를 알 수 있다.
• 보통 원소는 정수이며, set id는 leader라 불리는 원소의 값으로 정해진다. 
• 연산
  • UnionFind create (int n) //n은 입력의 크기
    • 단일 원소로 구성된 독립된(서로소) 집합들을 n개 갖는 하나의 집합을 만든다. → {{1}, {2}, ..., {n}}
  • int find(UnionFind sets, int e)
    • 원소 e가 포함된 집합의 set id를 return
  • void makeSet(UnionFind sets, int e)
    • 단일 원소 e로 구성된 서로소 집합 하나를 sets에 넣는다. 단, {e}는 sets에 이미 있지 않아야 한다.
  • void union(UnionFind sets, int s, int t)
    • set id가 s인 집합과, t인 집합에 대하여 $s\neq t$일 때, s 혹은 t의 set id를 가지는 하나의 집합으로 합친다.
      • 보통 set id는 min(s, t)로 결정된다.

Dictionary ADT

• dictionary는 일반적인 associative storage 구조이다. → key-value pair로 값을 저장한다.
• dictionary의 item은 다음과 같다.
  • identifier → key
  • identifier 관련 정보 → value
• 저장되는 pair에 순서가 있지는 않다.
• 연산
  • 삽입, 삭제, 탐색
• 구현
  • list
  • search table
  • hash table
  • balanced binary search tree → 삽입, 삭제, 탐색 연산에 대해 worst case에서 O(log n) time