Não sei se este é o lugar para perguntar sobre algoritmos. Mas vamos ver se eu recebo respostas ...:)

Se algo não estiver claro, fico muito feliz em esclarecer as coisa

Acabei de implementar um Trie em python. No entanto, um pouco parecia ser mais complicado do que deveria (como alguém que ama a simplicidade). Talvez alguém tenha tido um problema semelhante?

Meu objetivo era minimizar o número de nós armazenando o maior prefixo comum de um subtrie na raiz. Por exemplo, se tivéssemos as palavras stackoverflow, stackbase e stackbased, a árvore ficaria assim:

              [s]tack
[o]verflow ______/ \_______ [b]ase
                                  \___ [d]

Observe que ainda é possível pensar nas bordas com um caractere (o primeiro do nó filho

Encontra -query é simples de implementar.Inserçã não é difícil, mas um pouco mais complexo do que eu quero ..:

A minha ideia era inserir as chaves uma após a outra (começando em uma tentativa vazia), procurando primeiro pela chave a ser inserida k Encontra (k)) e, em seguida, reorganizando / dividindo os nós localmente no local em que o procedimento de localização para. Existem quatro casos: (Seja k a chave que queremos inserir e k 'a chave do nó em que a pesquisa terminou)

k é idêntico a k 'k é um prefixo "adequado" de k 'k 'é um prefixo "adequado" de kk e k 'compartilham algum prefixo comum, mas nenhum dos casos (1), (2) ou (3) ocorr

Parece que cada um dos casos é único e, portanto, implica diferentes modificações no Trie. MAS: é realmente tão complexo? Estou esquecendo de algo? Existe uma abordagem melhor

Obrigado :