Naiive dictionary : Struct

• 다른 종류의 데이터 타입을 array처럼 가질 수 있음
• size를 고정시키는건 문제가 있음

Hashtable

각 vocabulary term은 hash된 integer을 갖는다.

장점 : 개 빠르다 O(1)

단점

• judgment, judgement 같은 minor한 변형은 잡아내기 힘들다.
• prefix search를 못한다. (co-education, co-habitation은 co로 안묶임)
• vocabulary가 계속 많아지면 (ㅋㅋ루삥뽕같은 신조어) re-hash하기가(hash function을 다시 찾기가) expensive하다.

Binary Tree

장점 : 쉽다. 우리에게 익숙한 모양이다.

단점 : Re-blancing 문제 (한쪽에만 tree가 생성되는걸 방지하는게 비용이 비쌈)

B-Tree

자식의 범위가 정해져 있는 Tree 구조. Standard ordering을 요구함 (정렬을 유지)