목록자료구조 (1)

dh_0e

[자료구조] 트라이(Trie)

트라이(Trie)여러 개의 문자열을 효율적으로 저장, 탐색 및 삭제 할 수 있는 자료구조 Retrieval tree에서 "Trie"를 도출한 이름사전 순 정렬이 자동으로 되며, 해시 충돌이 없기 때문에 해시 테이블보다 stable함자동 완성(검색어 추천 기능), 사전 구현, 문자열 패턴 매칭 등에서 사용됨  구조트라이는 루트 노드(root node)를 가지고 있으며, 각 노드는 알파벳(혹은 문자)별로 자식 노드를 가질 수 있음finish(또는 isEndOfWord) 변수를 두어 문자열의 끝을 나타냄(root) ├── C │ ├── A │ │ ├── T (finish=true) │ │ ├── N (finish=true) 위 예제에선 "CAT"과 "CAN"이 저장되어 있으며, T와 ..
자료구조 2025. 3. 5. 12:30
이전 Prev 1 Next 다음