[Algorithm Part 1] 5. Symbol Table

탐색(search)는 수 많은 applications의 중요 기능 중 하나다.

이번 글에서는, search 연산을 제공해주는 symbol table에 대해 살펴볼 것이다.

---

Symbol Table

Definition

A symbol table is data structure for key-value pairs that supports two operations:

insert (put) a new pair into the table and search for (get) the value associated with given key.

 

Symbol table은 key-value 쌍의 집합을 가지고 있는 동시에, 추가/탐색 연산을 지원하는 ADT다.

이때, key는 비교 연산(e.g., 등호 혹은 부등호 연산)이 있는 불변 객체어야 한다.

---

1. Implementation 1: sequential search 

data structure: 각 노드가 key-value쌍을 저장하고 있는 linked-list를 사용한다.

 

1. search: 특정 key를 찾을 때까지 모든 key를 scan한다.

2. insert: 추가하고자 하는 key가 있는지 확인한다. 없으면 맨 앞에 추가한다.

2. Implementation 2: binary search

data structure: 각 item이 key-value인 정렬 배열을 사용한다.

 

1. search: 이진 탐색으로 탐색 key가 배열에 있는지 확인한다.

2. insert: 이진 탐색으로 추가하고자 하는 key가 배열에 있는지 확인한다. 없으면 정렬 순서에 맞게 key-value를 추가한다.

---

3. Binary Search Tree

Definition of BST

A BST is a 1). binary tree in 2). symmetric order.

1. 이진 트리: 2개 이하의 서브 트리를 갖고 있는 트리
2. symmetric order: 모든 노드의 key는
   1. 왼쪽 서브 트리의 모든 노드 key보다 작아 한다.
   2. 오른쪽 서브 트리의 모든 노드 key보다 커야 한다.

Data Structure

Linked-list 기반의 BST를 사용한다.

Operations

1. search

서브 트리의 root 노드 key와 탐색 key를 비교한다

1. root 노드 key가 탐색 key보다 크면 오른쪽 서브 트리로 이동한다.
2. root 노드 key가 탐색 key보다 작으면 왼쪽 서브 트리로 이동한다.
3. root 노드 key와 탐색 key가 같으면, root 노드 value를 반환한다.

root 노드부터 시작해 leaf 노드까지 도달할 때까지 반복한다.

반복문이 끝날 때까지, 탐색 key를 찾지 못했으면, 탐색 key가 트리(객체 집합)에 없다는 것의 의미한다. 

 

2. insert 

서브 트리의 root 노드 key와 탐색 key를 비교한다

1. root 노드 key가 탐색 key보다 크면 오른쪽 서브 트리로 이동한다.
2. root 노드 key가 탐색 key보다 작으면 왼쪽 서브 트리로 이동한다.
3. root 노드 key와 탐색 key가 같으면, root 노드 value를 수정한다.

root 노드부터 시작해 leaf 노드까지 도달할 때까지 반복한다.

반복문이 끝날 때까지, 탐색 key를 찾지 못했으면, 다음과 같이 key-value를 추가한다.

1. leaf 노드 key보다 탐색 key가 작으면, leaf 노드 왼쪽 아래에 노드를 추가한다.
2. leaf 노드 key보다 탐색 key가 작으면, leaf 노드 오른쪽 아래에 노드를 추가한다.

---

Tree shape

이진 탐색 트리의 모양은 key-value 삽입 순서에 따라 달라질 수 있다.

즉, 삽입 순서에 따라 트리 깊이가 달라지며, 이는 연산 비용이 달라진다는 것을 의미한다.

best case는 $N \lg N$이 될 수 있지만, worst case는 N이 될 수 있다.

 

 key가 무작위로 삽입되면, 평균적으로 트리 깊이가 $\lg N$가 된다.

이는 quick sort partition 연산과 BST insert 연산간의 유사성을 파악하면, 직관적으로 이해할 수 있다.

 

하지만, key들이 무작위로 주어지지 않고, 정렬 순서로 혹은 역순으로 주어질 경우가 상당히 많다.

다음 글에서는, 이러한 문제(트리 깊이 문제)를 해결할 수 있는 자료 구조에 대해 알아볼 것이다.

---

Deletion in BSTs

4.1. Lazy approach

해당 key의 value를 null을 대체한다.

 

위 방법은 적은 연산 비용이 장정이지만, 메모리 과부화 문제가 발생할 수 있다.

4.2. Hibbard deletion

해당 key-value 노드를 트리에서 없앤다.

1. 해당 노드의 자식 노드가 없을 경우, 삭제시킨다.
2. 해당 노드의 자식 노드가 1개일 경우, 부모 노드와 자식 노드를 연결시킨다.
3. 해당 노드의 자식 노드가 2개일 경우, 
   1. 해당 노드의 후계자 즉, 오른쪽 서브 트리의 최소 노드를 찾는다.
   2. 서브 트리의 최소 노드 정보를 해당 노드에 저장한다.
   3. 서브 트리의 최소 노드를 삭제시킨다.

이 방법은 메모리 과부화 문제를 막아 주지만,

트리를 점점 비대칭적으로 만든다. 자세히 말하자면, 무작위 삭제 시 트리 깊이가 $\sqrt N$이 된다.

---

Performance

	worst case		average
	search	insert	search hit	insert
sequential search	N	n	N/2	N
binary search	$\lg N$	N	$\lg N$	N/2
BST	N	N	$1.39\lg N$	$1.39 \lg N$

---

다음 글에서는, 모든 연산 비용이 $\lg N$을 보장해주는 자료 구조에 대해 살펴볼 것이다.