전화 번호부의 효율적인 데이터 구조

Question

AVL 트리를 사용하여 전화 번호부를 구현했습니다. 그러나 많은 사람들이 Trie가 전화 번호부 구현에 가장 적합하다고 말합니다. 프로젝트를 Trie로 변경해야하는지 아니면 전화 번호부의 경우 AVL 트리가 Trie보다 더 효율적인지 다른 좋은 이유가 있습니까?

Answer 1

트라이는 키의 길이가 다른 경우에 특히 유용한 인덱스 구조입니다.

AVL (Adelson-Velskii and Landis) 트리는 균형 조건이있는 이진 검색 트리입니다.

N은 크지 만 L (길이)은 영어 사전을 저장하는 것처럼 크지 않고 단어가 무작위가 아닌 경우 Trie가 좋습니다. 그러나 L이 매우 크고 '단어'가 무작위 인 경우 무작위로 생성 된 개의 긴 암호와 긴 해시 값 등을 저장하는 것처럼 AVL 트리를 선택하는 것이 좋습니다.

자세한 내용은이 두 트리 구조 간의 차이점을 분석 한 pdf을 확인하십시오.

Answer 2

적절한 데이터 구조를 선택하는 것은 가장 중요한 기능을 충족시키기 위해 특정 작업을 최적화하는 것입니다.

예. 전화 번호부가 매우 빠르게 검색되어야하므로 Big-O는 검색 시간 N에 해당하므로 연결된 목록은 끔찍한 옵션입니다.

AVL 트리의 평균 검색 시간은 (log n)이지만, 이는 트리를 정렬 할 수있는 일종의 계층 적 순서가 있음을 의미합니다.

개인적인 제안은 버킷 해시 (연결된 목록의 해시 테이블)가 될 것입니다. 조금 복잡하지만 해시 함수의 키로 이름을 사용할 수 있으며 동일한 키를 가진 사람들을 연결된 목록 (n 검색 시간)에 저장할 수 있습니다. 이것의 큰 O는 여전히 N이지만, 일반적으로 무시되는 상수 요소를 고려할 때 평균 사례 런타임이 크게 감소합니다.