접두사 트리의 조회 비용은 얼마이며 그 이유는 무엇입니까?

Question

접두사 트리와 키가 주어진다. 트리에서 키를 찾는 비용은 얼마입니까?

내가 O (1)이라는 논문을 읽었습니다. 제가 아는 한 그것은 O (LogM)입니다. 여기서 M은 키의 길이입니다. 나는 이것이 왜 O (1)인지에 대한 해답을 찾지 못했지만, 우리가 키를 스캐닝하는 것을 무시한다면 그것은 O (1) 일 수 있다는 것을 언급했다. 누군가가 우리에게 키 스캐닝을 무시하면 O (1) 인 방법을 그래픽으로 설명 할 수 있습니까?

Answer 1

트라이 내부의 키를 조회하는 데 드는 비용이 O(1)이 아닙니다.

총 시간은 O(l)입니다. 여기서 l은 일치시키려는 단어의 최소 길이 또는 트리의 깊이입니다. 많은 사람들이 이것을 O(log n)이라고 쓰는데, 여기서 n은 트리의 전체 요소입니다.

트리 루트에서 시작합니다. 현재 단어와 일치하는 노드 1 개를 탐색하면됩니다. 단어와 일치하거나 단어가 트리 안에 있지 않을 때까지이 통과를 계속합니다. 노드 당 1 명의 자식 만 검색하면 O(l)이됩니다.