Имя для структуры данных «префиксный список»?

Question

Я ищу хорошее имя для моей структуры данных, которая содержит все «начинается-с» суб списки списка, например:

Given list: [A, B, C] 
My data structure: [ [A], [A, B], [A, B, C] ] 

Заметим, что моя структура данных действительно включает только заказал комбинации (например, не [C, B, A]) и не включает все комбинации (например, не [B, C]). Только все префиксы (в некотором смысле).

Существует ли правильный математический/программный термин для такого рода структуры данных?

Answer 1

TRIE. Вы можете больше узнать об этой структуре данных о ресурсах, доступных в Интернете.

Если нам нужны обе операции, поиск и префикс поиска, подходит Trie. Он в основном используется в словаре и проверке орфографии. С помощью Trie мы можем поддерживать все операции, такие как вставка, поиск, удаление в O(n), где n - длина обрабатываемого слова.

Другим преимуществом Trie является то, что мы можем печатать все слова в алфавитном порядке.

Недостаток использования Trie заключается в использовании большего объема памяти. Для работы над этим вы можете прочитать о Ternary Search Tree