목록트라이 (1)

기어가더라도 제대로

[알고리즘 스터디 with 케이시] 비선형 자료구조 - 트라이(Trie)

트라이 검색 엔진에서 자동 완성을 하는 자료구조 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료 구조 특징 검색어 자동완성, 사전 찾기 등에 응용될 수 있다. 문자열을 탐색할 때 단순하게 비교하는 것보다 효율적으로 찾을 수 있다. L이 문자열의 길이일 때 탐색, 삽입은 O(L) 만큼 걸린다. 대신 각 정점이 자식에 대한 링크를 전부 가지고 있기 때문에, 저장공간을 많이 사용한다. 구조 루트는 비어있다. 각 간선(링크)은 추가될 문자를 키로 가진다. 각 정점은 이전 정점의 값 + 간선의 키를 값으로 가진다. 해시 테이블과 연결 리스트를 이용하여 구현할 수 있다.
CS/자료구조 2022. 7. 24. 16:05
이전 Prev 1 Next 다음