ソート済み配列から BST を構築する

ソート済みデータからバランス BST を構築

ソート済み配列が与えられたとき、常に中央の要素をルートとして選択することで高さバランスの取れた BST を構築できます。この分割統治法は最小の高さの木を保証します。

アルゴリズム

BUILD_BST(array, start, end):
  if start > end: return NULL
  mid = (start + end) / 2
  node = new Node(array[mid])
  node.left  = BUILD_BST(array, start, mid - 1)
  node.right = BUILD_BST(array, mid + 1, end)
  return node

例

入力: [1, 2, 3, 4, 5, 6, 7]

ステップ 1: mid = 3 → ルート = 4
ステップ 2: left = BUILD([1,2,3]) → mid=1, ルート=2
ステップ 3: right = BUILD([5,6,7]) → mid=5, ルート=6

結果:
        4
       / \
      2   6
     / \ / \
    1  3 5  7

なぜ中央の要素なのか？

中央の要素を選ぶことで、残りの要素の約半分が左部分木に、半分が右部分木に配置されます。各レベルでのこの均等な分配がバランスの取れた木を作ります。

時間・空間計算量

• 時間: O(n) — 各要素を1回訪問
• 空間: 再帰スタックに O(log n)、木自体に O(n)

偶数長配列の処理

配列長が偶数の場合、2つの有効な中央要素があります。左中央（floor）または右中央（ceil）のどちらを選んでも、同じ高さの有効なバランス BST が生成されます。