[자료구조] Trie 자료구조로 문자열을 빠르게 탐색해 보자! (feat. 검색창 자동 완성)

반응형

 

 

Computer Science 모아보기 👉🏻 https://github.com/seoul-developer/CS

GitHub - seoul-developer/CS: 주니어 개발자를 위한 전공 지식 모음.zip

 

 

💋 Trie란?

✔️ 개념

• 트라이(Trie)는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조
• 검색 자동완성 기능 등 문자열을 탐색하는데 특화되어있는 자료구조
• 주로 문자열을 저장하고 검색하는 데 사용된다.

 

이미지 출처:  https://www.youtube.com/watch?v=-urNrIAQnNo

 

 

Trie 자료구조는 컴퓨터공학 과목에서 본격적으로 다루는 자료구조는 아니다. 하지만, 검색 자동완성 등 많은 서비스에서 필수적으로 사용되는 자료구조이기 때문에 인터뷰에서 자주 등장하는 주제다.

 

✔️ 특징

• 각 노드는 문자열 + 해당 노드까지가 단어인지에 대한 여부를 나타내는 boolean을 가진다.
• 구체적인 구현은 구현체에 따라 달라질 수 있다.
• 문자열 검색을 굉장히 빠르게 할 수 있다.
• 메모리 관점에서는, 각 노드에서 자식들에 대한 포인터들을 배열로 모두 저장하고 있다는 점에서 저장 공간의 크기에 비효율적일 수 있다.

 

💋 Trie의 연산

✔️ insert

• 각 문자열을 한 글자씩 트라이에 추가한다.
• O(L)의 시간 복잡도를 가지며, 여기서 L은 문자열의 길이다.
• 트라이는 각 문자를 노드로 저장하므로, 문자열의 길이만큼만 탐색하면 된다.

 

이미지 출처:  https://www.youtube.com/watch?v=-urNrIAQnNo

 

예시에서 등장한 Trie는 Car, Cat, Do, Done, Trie, Try를 삽입한 Trie 자료구조다.

각 문자마다 노드를 생성하면서, 공통된 부분에서는 prefix처럼 공유하기 때문에 메모리 공간을 효율적으로 활용할 수 있다. 예를 들어, Car, Cat의 공통 부분인 Ca에 대해서는 별도로 저장하지 않고, Ca를 prefix로 공유한다.

 

 

✔️ search

• 각 문자를 순차적으로 탐색하여 문자열이 존재하는지 여부를 판단한다.
• O(L)의 시간 복잡도를 가지며, 여기서 L은 문자열의 길이다.
• 트라이는 각 문자를 노드로 저장하므로, 문자열의 길이만큼만 탐색하면 된다.

 

위의 그림으로 다시 예를 들어, Do를 탐색하려고 한다면, 루트 노드에서 D로 이동하고, 그 뒤에 나오는 O로 이동한 후 O의 자녀 노드 중 단어의 완성을 뜻하는 true를 가지는 자녀가 있기 때문에 Do를 탐색하는데 성공한다.

 

💋 참고자료

• https://www.youtube.com/watch?v=-urNrIAQnNo (킹왕짱 설명)
• https://www.youtube.com/watch?v=zIjfhVPRZCg

 

 

도움이 되었다면, 공감/댓글을 달아주면 깃짱에게 큰 힘이 됩니다!🌟
비밀댓글과 메일을 통해 오는 개인적인 질문은 받지 않고 있습니다. 꼭 공개댓글로 남겨주세요!