c++ - C++ でトライ/サフィックス ツリーを作成する際のメモリ使用量の削減

Question

私はC ++でトライしようとしています.今、私の基本的なデータ構造は次のようになります..

struct node{
    int count; no of times this node has been visited.
    struct node* child[ALPHABET_SIZE]; // Let ALPHABET_SIZE be 26
}

文字列のサイズが大きくなると、割り当てられたメモリの多くが無駄になります。挿入した場合のように、"he" ツリーは次のようになります

root---->h--->e
    |--->e

ルートで2/26thは、割り当てられたメモリのみが使用されていることがわかります。改善方法 ？？.

Answer 1

ノードごとに固定サイズの配列を作成する代わりに、1 つの要素を持つ配列を作成し、子を挿入するときにサイズを変更します (サイズ + 1 の新しい配列に置き換えます)。挿入が遅くなるので、サイズ変更アルゴリズム (サイズ + 1 またはサイズ * 2 またはサイズ + サイズ/2) をテストおよび変更して、遅すぎる場合に割り当てが少なくなるようにすることができます。