많은 수의 키를 저장할 때 해시 테이블에 비해 공간이 절약되지만 쿼리 속도는 약간 떨어집니다.
검색은 log n이고 업데이트는 2 log n입니다.
다음 위키 백과
에서
은 해시 테이블을 통해 시도의 주요 장점은 다음과 같습니다
- 시도합니다 해시 함수로 주어진 의사 랜덤 순서로 결과를 주문한 반복, 해시 테이블에 반면 반복을 지원 (구현에 따라 결정되는 해시 충돌의 순서에 따라 영향을 받음). 시도는 위와 같은 결과로 최장 프리픽스 일치를 용이하게하지만 해싱을 지원하지 않습니다. 이러한 "가장 가까운 적합"찾기를 수행하는 것은 구현에 따라 정확하게 찾을 수 있습니다.
- 해시 테이블이 가득 차면 다시 작성해야하므로 해시 테이블보다 삽입이 평균적으로 빠르다. 이는 매우 비싼 작업이다. 따라서 시도는 최단 시간 제한 비용을 훨씬 더 효율적으로 제한 할 수 있습니다. 이는 대기 시간에 민감한 프로그램에 중요합니다.
- 해시 함수가 사용되지 않으므로 일반적으로 작은 키의 해시 테이블보다 시도가 빠릅니다.
- trie에서 데이터를 조회하는 것은 최악의 경우 O (m) 시간, 불완전한 해시 테이블과 비교하여 보다 빠릅니다. 불완전한 해시 테이블에는 개의 키 충돌이있을 수 있습니다. 키 충돌은 다른 키를 해시 테이블의 동일한 위치에 매핑하는 해시 함수입니다. 불완전한 해시 테이블에서 최악의 경우 인 조회 속도는 O (N) 시간이지만, 은 O (m) 시간이 해시를 평가하는 데 일반적으로 O (1)입니다.
- 트라이에서 다른 키의 충돌이 없습니다.
- 트라이의 버킷은 해시 테이블 버킷과 유사하며 키를 저장하면 하나의 키가 둘 이상의 값을 가진 에 연결되어있는 경우에만 필요합니다. 해시 함수 을 제공하거나 더 많은 키가 트라이에 추가 될 때 해시 함수를 변경할 필요가 없습니다.
- 트라이는 키를 사용하여 항목의 사전 순 정렬을 제공 할 수 있습니다.
시도 횟수뿐만 아니라 몇 가지 단점을 가지고 수행 데이터가 직접 하드 디스크 드라이브에 액세스 할 특히,
- 시도 횟수가 데이터를 찾고에 대한 해시 테이블보다 어떤 경우에는 속도가 느려질 수 있습니다 또는 메인 메모리와 비교하여 랜덤 액세스 시간이 높은 다른 2 차 저장 장치.
- 부동 소수점 숫자와 같은 일부 키는 긴 체인 인 및 특히 중요한 의미가없는 접두어로 이어질 수 있습니다. 그럼에도 불구하고 비트 트라이는 표준 IEEE 단일 및 이중 형식 부동 소수점 숫자를 처리 할 수 있습니다.
Trie on Wikipedia
당신이 만드는 것입니다 어떤 업데이트 및 쿼리의 종류 ? 여기에서 사용해야하는 구조의 유형은 당신이 묻는 질문에 달려 있습니다. – templatetypedef
연락처가 업데이트되었습니다. – Rish