Search Structures

1. Symbol Table

(키,값)쌍의 모임을 symbol table이라고 한다.

사전에서 특정 단어(키)를 이용하여 뜻(값)을 알아내는 것도 심볼테이블의 응용분야이다.

 

 

symbol table

public class SymbolTable<Key,Value>
{
	void put(Key k,Value v);
    Value get(Key k)
    boolean contains(Key k)
    void delete(Key k)
    boolean isEmpty()
    int size()
    Iterator<Key> keys()
}

심볼테이블은 보통 위와같은 메소드들을 가진다.

 

여기서는 Generics 지원하며, 

중복키는 허용하지 않는다. 만약 중복키가 입력될 경우 기존의 값을 새 값으로 변경한다.

키와 값은 null이 될 수 없고, 테이블에 없는 키값으로 검색할 경우 null을 반환한다.

 

---

1.3 연결 리스트를 이용하는 경우

 

(키,값)의 쌍으로 구성된 연결 리스트를 유지.

검색시 모든 키를 순회하며 입력키와 일치여부를 확인한다.

삽입시 모든 키를 순회하며 입력키와 일치여부를 확인(이미 있는지 순회하며 찾음), 일치하는 키가 없으면 리스트의 제일 앞에 키,값 쌍을 추가한다.

 

/*소스코드*/

 

구현이 쉬운 편이나, 그만큼 성능이 구리다

검색,삽입시 O(N)의 시간복잡도.

 

---

1.4 정렬된 배열을 이용한 이진 검색

 

이진검색을 위해서는 배열에 저장해야하고, 정렬이 되어있어야 한다.

key 배열과 value배열을 따로 만들어 사용하고,

한 쌍의 (key,value)는 각각의 배열에서 같은 위치에 있도록 한다.

 

---

2. Binary Search Tree(BST)

이진검색트리.

배열을 이용하는 방법은, 매번 배열의 원소 위치를 한 칸씩 밀거나 당기는 문제가 있었다.

이런 비효율을 줄일 수 있는 방법.

그러나, BST는 완전이진트리가 아니므로 depth가 높아지면 효율이 떨어진다.