BST配列表現を完成させるためにソートされたリスト

Question

ソートされた配列（[1,2,3,4,5,6]など）と、配列を構成するときに得られる表現このソートされた配列から完全なバイナリ検索ツリーを生成し、このバイナリ検索ツリーを配列（例えば、[4,2,6,1,3,5]、下の図を参照）として表現しますか？

 4 
    2  6 
1 3 5 

は、ここではいくつかのより多くのコンテキストです：よく1は、ソー​​トされた配列を取ると、それから、完全なバイナリ検索ツリーを構築することが知られている（独特の表現があります）。再帰アルゴリズムは、適切な中間（これは実際は非常に難しい）を見つけて、それをルートとして扱い、次に左のサブアレイと右のサブアレイに を繰り返します。結果として生じるBSTから、完全なBSTの配列表現を構築するために、レベルオーダートラバーサル（基本的に幅優先の検索）を実行することができる。

私がこれを尋ねる理由は、このマッピングが配列の内容とは無関係であることです。その長さだけに依存します。したがって、私は、互いの関数として両方の配列を簡潔に表現することが可能でなければならないと感じています。

どのような考えですか？

Answer 1

木の高さは予測可能ですroundUp(log2(nodes))。右のサブツリーがでないこともわかっています。は、左のサブツリーよりも大きい - |LS| >= |RS|です。さらに、ツリーを完璧にするために欠けているノードの数を計算することができます：2^(height - 1) - arr.length。これは、私たちは、サブツリーの中のノードをどのように分配するかを予測することができます：

findRoot(int[] arr , int maxLeaves , int maxLevelL) 
    //maxLeaves is the number of leaves on the maximum-level 
    int l = min(maxLevelL/2 , maxLeaves) 
    return (arr.length - maxLeaves)/2 + l 

node buildTree(int[] arr , int maxLeaves , int maxLevelL) 
    if maxLevelL == 0 
     return null 

    node result 
    int rootidx = findRoot(arr , maxLeaves) 

    result.val = arr[rootidx] 

    result.left = buildTree(arr.subarray(0 , rootidx) , Math.min(maxLeaves , rootidx - 1) , maxLevelL/2) 
    result.right = buildTree(arr.subarray(rootidx + 1 , arr.length) , Math.max(0 , maxLeaves - rootidx - 1) , maxLevelL/2) 

    return node 

基本的な考え方は以下の通りです：すべての完全な分探索木は、BSTの再帰的定義については、一つの特性を共有：LSとRSが残っている(LS , R , RS) OR null、右サブツリーはBSTとしても定義されています。 LSとRSは完全であり、少なくとも1つは完璧でなければなりません。我々は2つのどれが完璧であるかを簡単に予測することができます：最高レベルではmノードに適合しますが、配列内には完全なツリーを構築するためにノードxがありません。したがって：

if m - x == m/2 then both are complete and the height of RS is height(LS) - 1 
if m - x < m/2 RS is perfect, LS only complete but not perfect 
if m - x > m/2 LS is perfect, RS only complete but not perfect 
if m - x == 0 both LS and RS are perfect and of equal height 

我々は、次のルールを使用して、ツリーのルートを見つけることができる： 左（l）上のノードの数を計算しheighestレベルに配置される右（r）サブツリー。今、私たちは簡単に、木からそれらのノードを削除し、完璧なBSTのルートを計算し、後で暗黙的に戻ってツリーに左と右のノードを追加することができますroot = (arr.length - (l + r))/2 + l

E.g.: 
Input: 1 2 3 4 5 
Nodes on maxLevel: 2 
maxLevelL: 4 

l = 2 
r = 0 

root_idx = (arr.length - (l + r))/2 + l = 
    = (5 - 2)/2 + 2 = 
    = 3 

Apply this algorithm recursively to define subtrees: 
... 

result: 
        4 
       / \ 
       2  5 
      / \ 
      1  3 

注： 私がテストしていませんこのコード。修正する必要がある数学的な不十分さがまだ含まれている可能性があります。しかし、論理は正しいです。これは、ある配列から別の配列へのインデックスの再マッピングの方法を表すにすぎない。実際の実装は、私が提供したコードとかなり異なって見えるかもしれません。

二度目のこの議論を持った後、ここでは完全なBSTの定義です：完全なバイナリツリーで

あらゆるレベルで、おそらく最後を除いて、完全に充填され、そして最後のすべてのノードレベルはできるだけ遠くにある。

from wikipedia

コンプリート分探索木は、ソートされた配列とその逆に、完全なBSTのユニークなマッピングを許可するいくつかの追加の制約、で、バランスの取れた分探索木のサブクラスです。完全なBSTは均衡のとれたBSTのサブクラスなので、はでバランスの取れたBSTを構築するのには十分ではありません。

EDIT：
上記のアルゴリズムは、直接アレイを構築するため、以下のように変更することができる。

• ツリーのルートインデックスn持つノードの左の子をインデックス0
• を有しますインデックス(n + 1) * 2 - 1
• インデックスnを持つノードの右の子はインデックス(n + 1) * 2

を持っています

通常、これらのアクセス操作は1ベースのアレイ上で行われますが、私はこのように、我々は直接配列を生成するためにbuildTreeを再実装することができ利便

ための0ベースの配列に一致するようにそれらを変更しました：

node buildTree(int[] arr , int maxLeaves , int maxLevelL , 
      int[] result , int nodeidx) 
    if maxLevelL == 0 
     return 

    int rootidx = findRoot(arr , maxLeaves) 

    //insert value into correct position of result-array 
    result[nodeidx] = arr[rootidx] 

    //build left subtree 
    buildTree(arr.subarray(0 , rootidx) , Math.min(maxLeaves , rootidx - 1) , maxLevelL/2 , 
       result , (nodeidx + 1) * 2 - 1) 

    //build right subtree 
    buildTree(arr.subarray(rootidx + 1 , arr.length) , Math.max(0 , maxLeaves - rootidx - 1) , maxLevelL/2 , 
       result , (nodeidx + 1) * 2) 

arrとは異なり、resultというサブアレイは決して使用しません。どのメソッド呼び出しでも、各ノードのインデックスは決して変更されません。

Answer 2

いいえ直接的表現バイナリツリー検索（BST）と直接ソート配列を表現する間。並べ替えられた配列間の唯一の関係は、BSTで順序通りのトラバーサルを実行して配列に格納する場合です。

Answer 3

ここで私が思いついたのです。それは私が心に持っていた機能ではないという点で理想的ではありませんが、ツリーを構築してそれから配列を作成する労力を節約します。

find_idx(n) { 
    if n == 1 { return 0; } 

    h = ceil(lg(n+1)) // height of the tree 
    f_h = floor(lg(n+1)) // height of the full portion (h or h-1) 
    m_n = 2^h - 1 // # of nodes if tree were full 
    f_n = 2^f_h -1 // # of nodes of full portion 

    return floor(f_n/2) + min(n - f_n, floor((m_n - f_n)/2) 
} 

to_bst_array(array) { 
    q = new empty queue 
    res = resulting vector 

    q.push(array) 

    while !q.is_empty() { 
    subarray = q.pop() 
    idx = find_idx(subarray.len()) 

    res.push(subarray[idx]) 

    if subarray.len() > 1 { 
     q.push(subarray[..idx]) // slice from 0 to idx 
    } 

    if subarray.len() > idx + 1 { 
     q.push(subarray[idx + 1..]) // slice from idx+1 till end of subarray 
    } 
    } 

    return res 
}