http://cr.yp.to/critbit.html
DJB пишет crit-bit деревья настолько клёвая, простая и быстрая
структура, что ей можно бы было заменить зоопарк примитивов например в
том же Python. Мол штатная практика это использовать хэш таблицы где
нужно находить по точным соответствиям; или кучи (heap), где нужно
искать минимум; или AVL, красно-чёрные деревья для остального.
* хэш таблицы поддерживают вставку, удаление и точный поиск.
crit-bit поддерживают вставку, удаление, точный поиск и упорядоченные
операции типа нахождения минимума. Плюс crit-bit гарантирует хорошую
производительность, в отличии от хэшей где некоторые данные могут
деградировать её
* heap поддерживает вставку, удаление и нахождение минимума. crit-bit,
кроме указанного выше, ещё и поиск по общему суффиксу
* структуры общего назначения, типа AVL или B-деревьев, поддерживают
аналогичные операции что и crit-bit, но crit-bit быстрее и проще,
особенно для строк разной длины. B-деревья представлены в виде очень
удобных блоков памяти для работы с диском, но такое же дружелюбное
"кластеризованное" представление crit-bit деревьев тоже сделать легко
* представьте насколько будут довольны программисты, если ваш встроенный
базовый тип данных не только позволит искать "x", но и упорядочивать
строки после "x". С хэш таблицами этого не сделать, а AVL сложнее и
медленнее
* Most people don't seem to realize how fast crit-bit trees can be;
* Most people don't seem to realize how small crit-bit trees can be;
* Most people don't seem to realize that crit-bit trees support all of
the standard data-structure operations. PATRICIA is often dismissed as
being large and complicated, but pure crit-bit trees are actually
quite small and simple
DJB уже замечен в гениальных изобретениях и творениях. И замечен в
полном отсутствии пиара или популяризации. Может быть и с crit-bit
аналогично?