트라이 (Trie)

래딕스 트리(Radix Tree), 접두사 트리(Prefix Tree), 탐색 트리(Retrieval Tree)
   >>> 탐색 트리(ReTRIEval Tree)에서 따옴

문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조

---

---

특징

- 접두사(Prefix)를 따라가며 원하는 target 을 찾는 방식
- 보통 트리(Tree)는 노드에 탐색을 위한 Key와, key에 매핑되는 Value 를 가짐 ( = Associative array )
   > 트라이(Trie)에서는 노드들이 key 값을 가지지 않고, 각각의 노드들이 Key를 정의함
       = 노드들의 위치가 Key를 대신

---

장단점

- 장점

• 문자열 검색이 빠름
• 시간 복잡도 측면에서 효율적 = 문자열을 탐색할 때, 하나씩 전부 비교하지 않음
• 공간 복잡도 측면에서 비효율적 = 각 노드들에서 자식들에 대한 포인터들을 배열로 모두 저장

- 단점

• 메모리의 크기가 너무 큼 = O(포인터 포인터 배열 개수 총 노드의 개수

---

복잡도

[ 문자열 길이, 문자열 수 = L, N ]
- 생성 : O( L )
- 탐색 : O( L )

---

[ 활용 예시 ]
- 단어 자동완성
- 사전 검색

---

사진 클릭 시 출처 이동
출처 , 출처2