ボキャブラリ ツリー、k-ary深さのあるツリー データ構造を使用しています。Lこれは、階層的k-meansクラスタリングを繰り返し実行した結果です。クラスターに割り当てられたデータ ポイントの数がクラスターの数よりも少ない場合、クラスター化プロセスが停止する可能性があるため、これは不均衡な構造です。
私の問題は、このツリーをマトリックス形式で保存する必要があることです。
単純に幅優先の順序で格納することを考えましたが、実際のノード数 (たとえばn) とバランス ツリー内の理論上のノード数との差が大きくなると、メモリの浪費が大きくなりすぎる可能性があります。つまり、次のようになります。
n << (1-k^L)/(1-k)
メモリを無駄にしたり、可能な限り無駄にしたりすることなく、不均衡なツリーをマトリックス形式で効率的に格納する方法はありますか?
スペースを無駄にしないようにするのはかなり難しいようです。ただし、非常に単純なアプローチの概要を以下に示します。リーフのスペースが常に割り当てられている場合は、O(N log_k N) スペースまたは O(k N log_k N) のみが必要です (場合によっては便利です)。ここで、N はリーフの数です。ツリー内の要素。コストは、要素へのアクセスに O(log_k N) が必要なことです。
正確な実装は、多くの要因に依存するため、かなり異なります。アイデアは、バランスのとれたバイナリ ツリーの表現を配列として単純に一般化し、アンバランスな n 分ツリーを行列として機能させることです。これは、マトリックス セルをノードとして機能させることによって行われます。ノードに含まれる情報は、データ構造を持つ単一のセルに配置するか、次のいくつかのセルに分散させることができます。重要なことは、各ノードには、その特定のノードの情報と、ノードが持つ子の場所に関する情報が含まれている必要があるということです。次に、インクリメンタル ポインターを使用して、子の次の空きスポットがどこにあるかを追跡します。
全体として、これは r*c 以下の要素を持つ単なる配列であり、r 行 c 列の行列に分割されています。行 L には深さ L のノードが含まれるため、リストのリストの方が便利な場合があります。それ以外の場合は、あまり役に立ちません。