목록트라이 (1)

넘치게 채우기

[자료구조] 4-8. 트라이(Trie)

트라이란? 트라이는 문자열의 저장과 탐색을 효율적으로 하기 위한 k진 탐색 트리이다. 단어들이 공동으로 가지는 접두사들을 이용해서 문자열을 저장하고 탐색한다. 트라이의 특징 1. 트라이의 루트에는 빈 문자열을 나타내는 노드부터 시작한다. 루트 노드부서 시작해서 문자열의 접두사부터 따라가기 시작한다. 2. 각 노드는 문자와 자식 노드에 대한 포인터를 가지고 있다. 3. 종료 노드는 해당 문자열이 Trie에 존재함을 나타낸다. 4. 문자열 검색은 루트에서 시작하여 해당 문자열의 모든 문자를 따라 이동한다.(문자열의 접두사를 얻을 수 있다) 트라이의 시간복잡도는 O(n)(문자열의 길이만큼) 이다.트라이는 검색이나 사전 등에서 사용된다. 각 노드는 다음 자손의 포인터와 nil을 모두 포함하는 배열을 가지고 있다..
컴퓨터과학/자료구조 2023. 4. 14. 10:59
이전 Prev 1 Next 다음