структура данных, которая обеспечивает производительность O(2*n) (где `n` — длина ключа; если что, у хэш-таблицы тоже как минимум такое, потому что сам хэш считать-то надо, и делать в лучшем случае ещё одно сравнение; на деле сравнений бывает и больше одного, так что O даже хуже) вне зависимости от количества элементов, гарантировано сортированые ключи, быстрое доставание минимального и максимального ключей, перечисление всех ключей с данным префиксом, и чтобы писать просто? их есть у меня! называется ().
также не требует рехэшинга/ребаланса, и реаллоков.
The qp trie implementation is about 40% bigger. вот примерно на этом месте сразу и неинтересно. криты простые как поленом по колену, и при этом всё ещё дохрена быстрые. специфика в том, чтобы — как и с aatree — код можно было ваще по памяти воспроизвести, не включая мозг, и результат был сравним по эффективности с более сложными решениями. в критах четыре функции по ~15 строчек, 2/3 — копипаста простейшего поиска «идём вниз». быстро, дёшево, сердито.
![[info]](http://lj.rossia.org/img/userinfo.gif){kind=small}