[Data Structure] Trie

Binary Trie

특징

이진 탐색 트리 형태의 불균형 트리 자료구조이다.

완전 매칭과 부분 매칭에 효율적인 자료구조이다.

해시의 대체로 사용된다.

두 타입의 노드를 가진다.

- Branch(link, interior, non-leaf) Node: 데이터 없이 자식 노드의 포인터만 저장

- Element(data, leaf) Node: 데이터 저장

시간복잡도: O(k), k=키의 최대 비트 수

Search(탐색)

탐색할 데이터를 K라고 할 때 i번째 레벨에서

K의 i번째 비트 = 0 → 왼쪽 서브 트리 이동

K의 i번째 비트 = 1 → 오른쪽 서브트리 이동

리프 노드에 저장된 데이터과 탐색할 데이터를 비교한다.

Insertion(삽입)

Insert 00001	Insert 10011
Insert 00101	Insert 10010

Multi-Way Trie

Multi-Way Trie는 차수가 2 이상인 Trie로 문자열을 저장하고 탐색하는데 유용한 자료구조이다.

사전의 단어 저장, 텍스트 자동 완성, 스펠링 체크 등에 주로 사용된다.