Radixツリーノード

Question

私はradixツリー（文字列/ char配列用）の実装に取り​​組んできましたが、特定のツリーノードの子であるツリーノードをどのように格納するかを考えています。

私は、Trieの（幾分基数の木に似ています）、おそらくいくつかの基数のツリー（これは最後にこのトピックを研究してからしばらくありました）で使用されているリンクリストの実装を見ましたが、あなたが多くの共通の接頭辞を含む一連のデータを持っている場合は特に不十分です。

もう1つのデータ構造（バイナリ検索ツリーなど）を使用することをおすすめします。多数の共通接頭辞を持つデータがある場合、単純なリンクリスト（O(log(n))対対O(n)）よりも大幅な速度向上が見られると思いますが、他の場所ではパフォーマンスにかなりの妥協が見られますか？

特に、共通接頭辞が多数ある場合、またはバイナリ検索ツリーでリンクリストを選択する可能性のあるその他の障害がある場合が心配です。

また、子ノードを格納するために、より良い（つまり、より高速なメモリを使用する）方法がありますか？

Answer 1

あなたはカートトライを探したいと思っています。カートトライは、単純なハッシュでBSTのようなデータ構造を使用します。あなたはここで説明を見つけることができます：http://code.dogmap.org/kart。

Answer 2

BSTまたはリストの代わりにトライを使用できます。 BSTの場合、ハッシュを計算する必要があります。ハッシュはトライを走査するのと同じくらい高価になる可能性があります（文字をインデックスとして使用する子供向けのポインタの配列でトライを考えています）。あなたは試練のトライで終わるでしょう。より良い解決策は、トライを構築し、分岐していないリンクを圧縮することです。