Trie
2019. 3. 4. 16:04
ch13-tries.md 본 글은 Udemy의 자바 자료구조 강의를 듣고 개인적으로 학습한 내용 복습하기 위해 작성된 글로 내용상 오류가 있을 수 있습니다. 오류가 있다면 지적 부탁 드리겠습니다. Trie 1. HashMap 장단점 1.1 장점 HashMap은 매우 효율적인 자료구조로 중요한 연산(삽입, 탐색)들에 O(1) 시간복잡도를 가진다. 1.2 단점 HashMap은 정렬을 지원하지 않는다. Hash함수는 왼벽하지 않기 때문에 충돌이 발생하게 된다. 위의 단점을 보완할 수 있는 자료구조는 Trie로 HashMap에서 발생하는 충돌을 제거하고, 정렬을 지원한다. 2. Trie 기본 개념 Tire / Radix Tree / Prefix Tree 라고 부른다. 배열을 통해 자료구조를 구현할 수 있다. k..