トライとハッシュマップの組み合わせにより、O（log n）ルックアップ/挿入/削除が可能になります。
trieの各ノードには、このノードと最大2つの子ポインターをルートとする有効な要素のIDとカウンターが含まれます。トライをルートから特定のノードに移動するときに左（0）または右（1）に曲がることによって決定されるビット文字列は、値の一部であり、対応するidのハッシュマップに格納されます。
削除操作は、トライノードを無効としてマークし、削除されたノードからルートへのパス上の有効な要素のすべてのカウンターを更新します。また、対応するハッシュマップエントリを削除します。
挿入操作では、各トライノードの有効な要素の位置パラメーターとカウンターを使用して、新しいノードの先行ノードと後続ノードを検索する必要があります。先行ノードから後続ノードへの順序どおりの走査に削除されたノードが含まれている場合は、ランクが最も低いノードを選択して再利用します。それ以外の場合は、先行または後続のいずれかを選択し、それに新しい子ノードを追加します（先行の場合は右の子、後続の場合は左の子）。次に、このノードからルートへのパス上の有効な要素のすべてのカウンターを更新し、対応するハッシュマップエントリを追加します。
ルックアップ操作は、ハッシュマップからビット文字列を取得し、それを使用して、このパスの左側にある有効な要素のすべてのカウンターを合計しながら、トライルートから対応するノードに移動します。
これにより、挿入/削除のシーケンスが十分にランダムである場合、各操作のO（log n）予想時間が可能になります。そうでない場合、各操作の最悪の場合の複雑さはO（n）です。O（log n）の償却済み複雑度に戻すには、ツリーのスパース性とバランス係数を監視し、削除されたノードが多すぎる場合は、完全にバランスの取れた密な新しいツリーを再作成します。ツリーの不均衡が大きすぎる場合は、最も不均衡なサブツリーを再構築します。
ハッシュマップの代わりに、バイナリ検索ツリーまたは任意の辞書データ構造を使用することができます。トライ内のパスを識別するために使用されるビット文字列の代わりに、ハッシュマップはトライ内の対応するノードへのポインタを格納する場合があります。
このデータ構造でtrieを使用する他の代替手段は、インデックス可能なスキップリストです。
各操作のO（log N）時間は許容範囲ですが、完全ではありません。Kevinによって説明されているように、他の操作のより複雑なO（sqrt（N））と引き換えに、O（1）ルックアップの複雑さを持つアルゴリズムを使用することが可能です。しかし、これは改善することができます。
ルックアップ操作ごとにいくつかのメモリアクセス（M）を選択した場合、他の操作はO（M * N 1 / M）時間で実行される可能性があります。このようなアルゴリズムのアイデアは、関連する質問へのこの回答に示されています。そこに記述されているトライ構造により、位置を配列インデックスに簡単に変換したり、元に戻したりすることができます。この配列の空でない各要素にはidが含まれ、ハッシュマップの各要素はこのIDを配列インデックスにマップします。
このデータ構造に要素を挿入できるようにするには、連続する配列要素の各ブロックを空のスペースでインターリーブする必要があります。ブロックの1つが使用可能なすべての空きスペースを使い果たしたら、50％を超える空きスペースがある、トライの一部の要素に関連するブロックの最小グループを再構築する必要があります。空きスペースの総数が50％未満または75％を超える場合は、構造全体を再構築する必要があります。
このリバランススキームは、ランダムで均等に分散された挿入/削除に対してのみ、 O（M N 1 / M ）の償却された複雑さを提供します。最悪の場合の複雑さ（たとえば、常に左端の位置に挿入する場合）は、M> 2の場合にはるかに大きくなります。O（M N 1 / M）の最悪の場合を保証するには、より多くのメモリを予約し、リバランススキームを変更して維持する必要があります。このように不変：構造全体に少なくとも50％の空きスペースを予約し、上位のトライノードに関連するすべてのデータに少なくとも75％の空きスペースを予約し、次のレベルのトライノード（87.5％）に予約します。
M = 2の場合、ルックアップにはO（1）時間、その他の操作にはO（sqrt（N））時間があります。
M = log（N）の場合、すべての操作に対してO（log（N））時間があります。
ただし、実際には、Mの値を小さくする（2 .. 5など）ことが望ましいです。これはO（1）ルックアップ時間として扱われ、この構造（通常の挿入/削除操作を実行している間）がキャッシュに適した方法で最大5つの比較的小さな連続したメモリブロックを処理し、ベクトル化の可能性が高くなります。また、最悪の場合の複雑さが必要な場合は、これによりメモリ要件が制限されます。