バランスの取れたバイナリ検索ツリーを作成するための入力

バランス/完全なバイナリツリーを生成するためにバインドされた整数の入力パターンはありますか？バランスの取れたバイナリ検索ツリーを作成するための入力

2016-09-16 Haseeb Javed

たとえば、a - 長さがnの入力の並べ替えられた配列を考えてみましょう。次に、a[mid]でBSTを構築し始めます。ここではmid - 中間要素（n/2）です。 a[mid]をBSTにプッシュすると、私たちの配列は、 a [0：mid-1]と[mid + 1、n-1]の2つの新しいソート配列に分割されます。

サブアレイが空でない場合は、両方とも同じロジックを実行します。サブアレイごとに新しいmid要素を選択し、BSTにプッシュします。これで4つの新しい配列が生成されます。

すべてのサブアレイに対してこのプロセスを完了すると、その入力に対して最もバランスのとれたBSTが得られます。

出典

2016-09-16 14:41:40 serhiyb

これは、BSTの挿入機能を変更して、ノードに再帰的にノードを追加させることを意味します。私は、データ構造の実装に変更を加えずにバランスの取れたBSTを生成する入力シーケンスを探していました。 –

@HaseebJaved挿入機能を変更する必要はありません。並べ替えられた配列からBSTを構築する関数を追加するだけです。その後、別の要素を追加する場合は、通常の挿入関数を使用してください。 –

@A。十分なフェアリー。しかしそれは、BSTに挿入されたときにバランスのとれたBSTを生み出す、すなわちヘルパー機能を使用しないシーケンスパターンがそれ自身存在しないことを意味するか？ –

バランスの取れたバイナリ検索ツリーを作成するための入力

答えて

関連する問題