algorithm - ソートされた配列を二分探索木に挿入する

Question

ソートされた配列をバイナリ検索ツリーに挿入するアルゴリズムを実装したいのですが、片側だけに成長するツリーになってしまいたくありません。

あなたはなにか考えはありますか？

ありがとう。

Answer 1

これにより、バランスの取れたツリーが得られます（O（n）で）：

1. 配列の中央の要素のノードを構築し、それを返します
   (これは基本ケースのルートになります)。
2. 配列の左半分で 1. から繰り返し、戻り値をルートの左の子に割り当てます。
3. 配列の右半分で 1. から繰り返し、戻り値をルートの右の子に割り当てます。

Java ライクなコード:

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);
}

hereから派生したコード。

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;
}