バイナリ検索ツリーに最適なルートを探します。

Question

私のバイナリ検索ツリーに最適なルートを見つけようとしています。つまりこれは私のバイナリ検索ツリーです。

  42 
    / \ 
    / \ 
    25  53 
    /\ /\ 
    23 41 49 55 
/\/\/\/\ 

次に、それらをinOrder walkの形式で配列に保存します。

| 23 | 25 | 41 | 42 | 49 | 53 | 55 | .........
........... ↑ ........... ↑ ........... ↑。 ..........

だから、矢印を指しているのは、どれが最良のルート41,42,53であるかを調べるノードです（アレイは大きくて病気になります配列の奇数インデックスとツリーの所与の深さ）。私は木がすでにバランスであるかもしれないことを知っていますが、これは実験ですので、私と一緒に裸にしてください。

私は新しいルートとしてすべての単一の奇数インデックスを試して、前のものとそれぞれの高さを比較し、どのようなものが私の最高の高さであるかを判断できるようにしなければなりません。私は25を決定した場合、すなわち、私は各ので、この

  25       25 
      \        \ 
      \        \ 
      42   or     53 
       \       /
       53       42 
        \      /

のようなツリーを持つことができ、私の新しいルートである私がチェックし、配列内の前のノードとの高さを比較して、私はそれが私に与えるノードを返します最良のノード。 は、これまでのところ、私はこれを試してみました：

void rebalance(){ 

    //this is the size for the array and NumDepth is defined at the constructor 

    int size = (pow (2,(numDepth +1))-1); 
    Node* Array2 [size]; 
    int i = 0; 
    int bestH = 0; 
    Node* temp; 

    for (int i=0; i < size; i++){ 
      Array2[i]= new Node(); 
      Array2[i]= NULL; 
    } 
    //this function will be the one creates the inOrder walk and saves my nodes inside the array 
    storeInOrder(rootBST, Array2, i, numDepth); 

    temp = shortestBST(Array, rootBST, bestH, height); 


} 

Node* shortestBST(Node *root[], Node* root, int &bestHeigth, int sizeA) { 
//root is my main tree basically 

//this is how i know that i have to use the odd numbers in the array 

    for(int i= 1; i< sizeA; i+=2){ 

     //inside here I am supposed to do a recursion to check every node inside the array to check the node that is the best 
     //they gave me a hint saying that i can point the nodes in the array to the ones in my main tree to create the tree with the new testing root in order to check if that node can create a best tree but i don't know how to do that using recursion 
//each of my nodes hold a key, a height and a size of a subtree , left to point to the left and a right to point to the right 

    } 




} 

Node::Node() { 

    sizeSub=0; 
    height=1; 
    key=0; 
    left=NULL; 
    right=NULL; 
} 

Answer 1

あり類似した質問と、ここで求められているものだけのように見えるのアルゴリズムです：

1. 右回転操作を使用しては、リンクリスト にツリーを回す（バックボーンまたはつる別名）
2. バックボーンのすべての第2ノードをその親に関して回転させて、 をバックボーンと完全にバランスのとれたBSTにします。

http://www.geekviewpoint.com/java/bst/dsw_algorithm

Answer 2

あなたはソート順で番号を開始しているので、ルートノードを見つけることは非常に簡単です：理想的なルートは、挿入する数字の中央値です。

これにより、挿入を再帰的に行うことが簡単になります。中央値を見つけてルートとして挿入し、左のサブ配列を左の子として挿入し、右のサブ配列を右の子として挿入します。