잘 알려지지 않은 유용한 자료구조
Source
Evernote/ancom21c's notebook/잘 알려지지 않은 좋은 자료구조.md
Summary
이 문서는 Skip lists, Bloom filters, Tries, Rope, Spatial Indices 등 상대적으로 덜 알려졌으나 특정 용도에서 효율적인 자료구조들을 소개합니다. 각 자료구조의 핵심 특징, 시간 복잡도, 실제 적용 사례(Redis, BigTable, Chrome 등) 및 구현 언어/라이브러리 정보를 간략히 정리하고 있습니다.
Key Points
- Skip lists: 확률적 자료구조로 평균 O(log n) 효율성을 가지며, Redis Sorted Sets 및 Qt에서 사용됨.
- Bloom filters: 해시 함수를 이용한 비트 배열로, 요소의 부재 확인에 매우 빠르며 False-positive 가능성은 있으나 False-negative는 없음. Chrome 안전 브라우징 및 Google BigTable에서 활용.
- Tries(Prefix-trees): 해시 함수와 결합 시 유용하며, 문자열 검색에 특화됨.
- Rope: 문자열의 중간 삽입 및 결합이 효율적인 자료구조로, SGI STL 및 Java/C# 구현체가 존재함.
- Spatial Indices: R-trees, KD-trees 등 공간 데이터(지도 좌표, 최근접이웃 탐색) 처리에 특화됨.
- 기타 언급: 허프만 트리, BSP Tree, 피보나치 힙 등.