Tries

트라이

• 트라이는 문자열에서 검색을 빠르게 해주는 트리구조를 말한다.

• 보통 정수형 이진트리에서 숫자를 검색할 경우, O(logn)의 시간복잡도를 가진다.

• 하지만 문자열의 경우는 다르다. 노드 내부에 문자열 각각을 다시 순회해야하므로, 문자열의 길이가 M이라고 했을 때, 최대 O(MlogN)의 시간복잡도를 갖게 된다.

• 이러한 문자열 검색을 좀 더 빠르고 효율적으로 할 방법이 없을까? 하던 고민에서 나온 것이 바로 트라이이다.

[유튜브] 엔지니어 대한민국

[유튜브] 엔지니어 대한민국

• 트라이에서 문자열 검색을 하게 되면, 최대 문자열의 길이 M정도의 시간복잡도밖에 걸리지 않는다. -> O(M)