Временная сложность структуры данных Trie

Question

Предполагая, что строки, которые будут сохранены в Trie, имеют длину 'n' символов. Какое будет время выполнения для insert (), search () и remove ()?

Я посмотрел в Интернете, но я не получил четкого ответа. Кто-нибудь может вкратце упомянуть, пожалуйста, сложность времени для этих трех операций.

Answer 1

Как указано в этой статье Википедии, и вставка, и поиск выполняются в пределах наихудшего времени выполнения, ограниченного O(n), где n - длина аргумента для вставки или поиска.Насколько я понимаю, удаление строки не является типичной особенностью структуры данных Trie.