Расширение дерева до большего количества листьев
Я должен сделать словарь, используя попытки, количество букв в алфавите увеличится с 26 до 120, и, следовательно, число листовых узлов увеличится в геометрической прогрессии. Какие оптимизации можно использовать, чтобы время поиска, вставки и удаления не увеличивалось экспоненциально?
РЕДАКТИРОВАТЬ Чтобы прояснить вопрос, извините за отсутствие деталей, я использую многоканальное дерево, например radix tree, и внесу в него некоторые изменения. Мой вопрос: если я знаю, что размер слова увеличится (наверняка) с 26 до 120, это увеличит глубину дерева. Можно ли уменьшить увеличение глубины, увеличив ключ более чем на 64 бита (регистр может получить максимум 64 бита)?
2 ответа
Хотя в некоторых случаях возможны некоторые оптимизации, но время поиска, вставки и удаления не будет увеличиваться экспоненциально. Увеличение набора алфавитов означает только то, что теперь каждый ваш узел будет больше. Путь к каждому слову будет иметь ту же длину, которая равна буквам в слове.
Часто лучше использовать двоичные попытки со сжатием пути (попытки Патриции), основанные на двоичном представлении ваших ключей. Таким образом, вы получаете преимущества наименьшего возможного алфавита, и у вас все еще есть только 2 узла (один лист и один внутренний) на ключ.