バイナリ検索ツリーへの配列クイック

Question

整数の配列を考えると、バイナリ検索ツリー（アンバランス）に素早く変換できますか？私は各要素ごとに1つずつ挿入しようとしましたが、これは挿入のたびに最初から移動する必要があることを意味します。それは完璧に機能しますが、最悪の場合はO（N^2）がアンバランスであると考えられます。配列がソートされます。大きなNを考えると、時間がかかると思う。

私の質問に戻って、私が述べたアルゴリズムよりも速くこれを行う方法はありますか？

たとえば、配列[4,5,2,3,1]を指定すると、これを高速に作成できますか？

4 
/\ 
    2 5 
/\ 
1 3 

Answer 1

のような自己平衡バイナリ検索ツリーを使用する必要があります。はい、O（nlogn）の整数配列から平衡型バイナリ検索ツリーを構築する簡単な方法があります。整数の

1. Sort配列を以下のように

   アルゴリズムです。これはO（nlog（n））時間を要する。

2. O（n）時間でソートされた配列からBSTを構築する。配列の中間要素をrootとして作成し、この操作を配列の左+右半分に再帰的に実行してください。

---

EDIT：あなたは、本質的に（比較を使用して）ソートされていない配列をソートしていたので、

1. まず、あなたはO（nlog（n））はよりも、この優れた操作を行うことはできませんO（nlogn）よりも複雑である。これはimpossibleです。
2. 最初にソートする必要がない場合は、配列の各要素に対してバイナリツリー挿入アルゴリズムを使用してバイナリツリーを構築できます。

Self-balancing BSTの標準実装を参照してください。配列をスキャンしている間、i番目の反復では、arr [1 ... i]のBSTが得られます。ここで、arr [i + 1]をBSTに追加します（挿入アルゴリズムを使用）。

Answer 2

整数の配列を考えると、すぐに（アンバランス）バイナリ 検索ツリーに変換する方法はありますか？

確かに。 O（n logn）で配列をソートし、配列の中間要素をルートとして選択し、左側の中間要素の前にあるすべての要素をルートに挿入し、右側（O（n）の時間） 。全体の複雑さはO(n logn)です。たとえば、配列を持っている場合：1, 2, 3, 4, 5に並べ替えます。1, 2, 3, 4, 5のように並べ替えます。中間の要素はあなたが中央の要素への2つのポインタを持つことができ、あなたが左に第一および右に他の移動を開始し、ただで指さ要素を挿入するので、あなたは木

 3 
    /\ 
    2 4 
/ \ 
    1  5 

を作成3であります左と右のサブツリーへのポインタ。

問題は、ツリーの高さがn/2であることです。これは、検索操作が遅いことを意味します（O(n)）。より良いパフォーマンスを得るには、red-black treeまたはAVL tree