リストの各要素を最下位のバケットに配置するバイナリサブツリーを見つける

Question

まず、数字'L'のリストがあり、すべての要素に対してのような要素'x'が含まれています。'x'私は上記の特性を満たす最小のサブツリーを見つけるためにアルゴリズムを探してい

1) Each node has three properties: 'min', 'max', and 'vals' (vals is a list of numbers). 
2) The root node has 'max'='M', 'min'=0, and 'vals'='L' (it contains all the numbers) 
3) Each left child node has: 
    max=(parent(max) + parent(min))/2 
    min=parent(min) 
4) Each right child node has: 
    max=parent(max) 
    min=(parent(max) + parent(min))/2 
5) For each node, 'vals' is a list of numbers such that each element 'x' of 
    'vals' is also an element of 'L' and satisfies 
     min < x <= max 
6) If a node has only one element in 'vals', then it has no children. I.e., we are 
    only looking for nodes for which 'vals' is non-empty. 

：

第二に、私は次のように構成されたバイナリツリーを持っています。言い換えれば、私は各子なしのノードが'vals'の1つだけの要素を含むようにノードのリストを取得しようとしています。

私はほとんど真実なバロックのデータ構造を使ってperlでそれを強制することができますが、私が使用しているすべての一時変数を把握するための精神的能力の限界に立ち向かっています。私は助けを求める。

これを行うための効率的なアルゴリズムがわかっているのであれば、さらに涼しいです。

私がやろうとしていることを知りたいのならば、これは次のようなものです。離散ウェーブレットパケット変換のための最小カバーを見つけて、標準的な耳障りな音符の各周波数を一意に分離します。問題は、ウェーブレット変換の各反復が扱う周波数範囲を半分に分けることです（したがって、上記の/ 2を最大と最小に定義します）。音符には指数関数的に上がる周波数がありますので、明白な関係はありませんとにかく私は分析的に（または実験的に、明らかにその問題に関して）派生することはできません。

私は実際にアルゴリズムを見つけようとしているので、プログラムを書くことができます。問題は一般的な言葉で書かれているので、DSPに入れるのは適切ではないと思います。もし一般的な "アルゴリズム"グループがあれば、そこではもっと良いと思うが、これはそうでないアルゴリズムの正しいグループのようだ。

私は何かを明確にすることができますか、または完全な回答がなくても何か助言があれば教えてください。

Answer 1

休憩とコーヒー2杯を取った後、自分の質問に答えました。以下のインデックスは1から始まり、MATLABスタイルで行われ...

L=[] // list of numbers to put in bins 
sorted=[] // list of "good" nodes 
nodes=[] // array of nodes to construct 
sortedidx=1 

nodes[1]={ min = 0, max = 22100, val = -1, lvl = 1, row = 1 } 

for(j=1;j<=12;j++) { // 12 is a reasonable guess 
    level=j+1 
    row=1 
    for(i=2^j;i<2^(j+1);i++) { 
    if(i/2 == int(i/2)) { // even nodes are high-pass filters 
     nodes[i]={ min = (nodes[i/2].min + nodes[i/2].max)/2, // nodes[i/2] is parent 
       max = nodes[i/2].max, 
       val = -1, 
       lvl = level, 
       row = -1 
       } 
    } else { // odd nodes are lo-pass 
     nodes[i]={ min = nodes[(i-1)/2].min, 
       max = (nodes[(i-1)/2].min+nodes[(i-1)/2].max)/2, 
       val = -1, 
       lvl = level, 
       row = -1 
       } 
    } 
    temp=[] // array to count matching numbers 
    tempidx=1 
    Lidx=0 
    for (k=1;k<=size(L);k++) { 
     if (nodes[i].min < L[k] && L[k] <= nodes[i].max) { 
     temp[tempidx++]=nodes[i] 
     Lidx=k 
     } 
    } 
    if (size(temp) == 1) { 
     nodes[i].row = row++ 
     nodes[i].val = temp[1] 
     delete L[Lidx] 
     sorted[sortedidx++]=nodes[i] 
    } 
    } 
} 

は今、アレイsorted[]は私が探していたまさに含まれています！

うまくいけば、これはいつか他の誰かに役立ちます。