10. Symbol tables & Binary search trees(BST)

1. Symbol table

 

Symbol table은 DNS lookup시 참조하는 테이블과 같이, key-value쌍이 mapping된 정보를 가지는 추상화된 테이블이다.

Key값이 주어지면, 우리는 value를 search한다.

 

API는 다음과 같다.

void put(Key key, Value val) 

Value get(Key key)

void delete(Key key)

boolean contains(Key key)

boolean isEmpty()

int size()

Iterable<Key> keys()

 

여기서 Value는 null이 될 수 없고, get연산시 key가 없다면 null이 return 된다. put연산시 기존에 key값이 있다면 해당 key의 value값을 update한다. 

Key값은 immutable한 wrapper type이나 object로 사용한다.

Value값은 모든 타입이 가능하다.

Java에서 Key값의 비교는 Comparable한 객체일 경우, compareTo()를 이용하고, 만약 그렇지 않고 user-defined 객체를 이용할 경우 equals() method를 구현하여 객체간의 비교를 할 수 있도록 한다. Equal method를 구현할 때, 다음의 요구사항을 만족해야 한다.

 

Reflexive : x.equals(x) is true

Symmetric : x.equals(y) iff y.equals(x)

Transtive : if x.equals(y) and y.equals(z), then x.equals(z)

Non-null : x.equals(null) is false

만약, 객체가 서로 다른 class에서 구현되었다면 false로 return해야 한다.

primitive type의 비교는 == 을 사용한다.

두 요소가 같은 type으로 casting되는지 확인한다.

계산된 필드끼리는 비교하지않고, 계산전 원래 필드를 비교한다.

 

2. 구현

 

1) Unordered Linked list

일반 linked-list에 key-value쌍을 한쪽 끝 node에 추가하는 방식

search/insert 모두 worst-case에서 모든 node를 살펴보아야 하기 때문에 ~N의 성능을 보여 좋지 않다.

 

 2) Ordered Array 

정렬된 배열에서 divide-and-conquer방식으로 부분배열로 나누어binary search하고, 값을 serach하고, insert하는 방식

Insert시 해당 키 오른쪽의 모든 키를 shift시켜야 하는 문제점이 있다. 따라서, insert의 성능은 평균적으로 ~N/2이므로 좋지 않다.

 

3) Binary Search Tree

아래서 살펴볼 것이다.

 

3. Binary Search Tree(BST)

 

1) Search, Insert

Binary search tree(BST)는 임의의 node의 key에 대해 left node의 key는 더 작아야 하고, right node의 key는 더 커야함을 만족하는 symmertic order를 가지는 binary tree이다.

따라서, BST의 node는 key, value, left node reference, right node reference 총 4개의 값을 필수적으로 갖는다.

 

Insert는 root node부터 시작해 recursive하게 탐색을 시도한다. 탐색 도중 key가 있을 경우 그 값을 update하고, 만약 없을 경우, 새로운 node를 만들어 leaf로 집어넣는다. 

한 가지 문제점은 worst-case에서 tree가 unbalanced로 성장할 경우 search time이 logarithmic time이 아닌 linear time이 나온다는 것이다. 이를 방지하고자, quick sort에서 했던 것처럼 key들을 random shuffling하고 값을 집어넣으면 quick sort  partitioning과 사실상 완전히 방식이 똑같기 때문에, search/insert의 성능은 distinct key에서 동일한 약 1.38logN의 성능이 나온다.

이러한 방식을 기반으로 key값에 대해 floor, ceiling. subtree size count, rank등을 logarithmic time에 수행할 수 있다.

만약 BST를 Inorder traversal(왼쪽-> key -> 오른쪽 순서로 recursive하게 탐색하는 방식)으로 탐색하여 해당 탐색의 순서로 Queue에 집어넣을 경우, Queue는 오름차순으로 정렬된 key들이 된다.

 

2) Delete

만약 Dynamic symbol table의 경우 delete연산을 통해서 node의 삭제 또한 가능한데, 만약 삭제하려는 node가 tree의 중간에 있을 경우 succesor(계승자)를 찾아서 삭제 후 해당 succesor와 교환하고 일련의 order를 회복하는 과정을 거쳐야 한다.

또한, 여기서 발생하는 문제점은 insert만 하는 것이 아닌 delete를 허용하게 될 경우, 시간이 지날 수록 tree는 unbalanced한 구조가 되어, search/insert/delete는 평균적으로 √N 의 성능이 나오게 되고, BST에서 이를 해결하는 것은 여전히 open-problem이다.