これは、実際に通常行われていることについての質問です。
エントリが 1 つの基数ツリーがあるとします (何らかの理由で、これをデモ用の単一のエントリと見なしてください)。
"tests are really hard, no one likes taking tests, they're the worst"
そして、2 番目のエントリを挿入します。
"team"
ルートからのエッジで終了したい
"te"
そしてそこから2つのエッジがあり、1つは
"sts are really hard, no one likes taking tests, they're the worst"
そして1つ
"am"
単純に、"te" と "sts are really..." の新しい文字列 (文字配列など) を作成できます。新しい単語「チーム」は短いものですが、これには多くの操作が必要です。
あるいは、「te」と「sts are really...」ラベルに、同じ元の文字列への参照と、開始/終了値を含めることができます。つまり、次のようになります。
[0, 2] for "te"
と
[2, <whatever it is>] for "sts are really..."
このようにして、コピーを回避し、「チーム」の挿入時間は「チーム」の長さにのみ依存し、他の文字列の長さには依存しません。つまり、この場合は「テストは本当に...」です。
kしたがって、 inO(k)が挿入される文字列の長さを意味するのか、それともこれまでで最も長い文字列を意味するのかの問題です。
明らかに後者の実装はより難しく、実際には (エンドポイントの保存のため) より多くのメモリを使用する可能性がありますが、理論上の最悪の場合の時間は改善されているようです。
実際に一般的に行われていることを誰かが知っているかどうか疑問に思っていますか?
ありがとう
編集: 後者の実装に関する 1 つの問題は、削除によって発生すると思います。後で "telepathy" を挿入してから "tests are really hard..." を削除した場合、"te" エッジが残り、必要以上に長い文字列への参照が残ります。