ソートされた配列をバイナリ検索ツリーに挿入する

Question

ソートされた配列をバイナリ検索ツリーに挿入するアルゴリズムを実装したいが、片側にしか成長しないツリーで終わることは望ましくない。

ご意見はありますか？

ありがとうございました。

Answer 1

をこれはあなたに（O（n）の中に）バランスの取れたツリーを与える必要があります：

1. を真ん中要素のノードを構築配列の中で
   （これはベースケースのルートになります）を返します。
2. アレイの左半分に1.を繰り返し、ルートの左の子に戻り値を割り当てます。
3. アレイの右半分に1.を繰り返し、ルートの右の子に戻り値を割り当てます。

Javaに似コード：here由来

TreeNode sortedArrayToBST(int arr[], int start, int end) { 
    if (start > end) return null; 
    // same as (start+end)/2, avoids overflow. 
    int mid = start + (end - start)/2; 
    TreeNode node = new TreeNode(arr[mid]); 
    node.left = sortedArrayToBST(arr, start, mid-1); 
    node.right = sortedArrayToBST(arr, mid+1, end); 
    return node; 
} 

TreeNode sortedArrayToBST(int arr[]) { 
    return sortedArrayToBST(arr, 0, arr.length-1); 
} 

コード。

Answer 2

ここのように、擬似ランダムな順序でそれらを挿入します。

#include <stdio.h> 

int array[] = {1,2,3,4,5,6,7,8,9,10}; 

#define COUNT 10 
#define STEP 7 /* must be relatively prime wrt COUNT */ 
#define START 5 /* not important */ 

int main(void) 
{ 
unsigned idx; 

idx=START; 
while(1) { 
     printf("[%u] = %u\n", idx, array[idx]); 
     // do_insert(array[idx]); 
     idx = (idx + STEP) % COUNT; 
     if (idx == START) break; 
     } 
return 0; 
} 

Answer 3

public class SortedArrayToBST { 
    public TreeNode sortedArrayToBST(int[] num) { 
     if (num == null) { 
      return null; 
     } 
     return buildBST(num, 0, num.length - 1); 
    } 

    private TreeNode buildBST(int[] num, int start, int end) { 
     if (start > end) { 
      return null; 
     } 
     int mid = start + (end - start)/2; 
     TreeNode root = new TreeNode(num[mid]); 
     TreeNode left = buildBST(num, start, mid - 1); 
     TreeNode right = buildBST(num, mid + 1, end); 
     root.left = left; 
     root.right = right; 
     return root; 
    } 
}