ソートセットを使用した平衡バイナリ検索ツリー

Question

サイズ1024のランダムバイナリ検索ツリーを生成しようとしています。要素はランダムソートセットにする必要があります...バイナリ検索を作成するコードを記述できます手動で要素を追加することで手動でツリーを作成することができますが、サイズ1024のランダムなバランスのとれたバイナリツリーを生成するコードを作成することはできません。そのツリーのキーを見つけようとしてください...

編集コメント

屋からのコードを追加し、それは...宿題であり、これは私がコードとして、これまでに得たものである：

using System; 
namespace bst { 
    public class Node { 
     public int value; 
     public Node Right = null; 
     public Node Left = null; 

     public Node(int value) 
     { 
      this.value = value; 
     } 
    } 

    public class BST { 
     public Node Root = null; 
     public BST() { } 

     public void Add(int new_value) 
     { 
      if(Search(new_value)) 
      { 
       Console.WriteLine("value (" + new_value + ") already"); 
      } 
      else 
      { 
       AddNode(this.Root,new_value); 
      } 
     } 
    } 
} 

Answer 1

再帰を使用します。 各ブランチは新しいブランチを生成し、ソートされていないセットの中間アイテム、中央値を選択します。それをツリーの現在のアイテムに入れます。中央値よりも小さいすべての項目を別の配列にコピーし、その新しい配列を同じメソッドの呼び出しに送ります。中央値より大きいすべての項目を別の配列にコピーし、新しい配列を同じメソッドの呼び出しに送信します。\

メインの親ノードが記入されていない限り、バランスツリーには奇数個の項目が必要です。重複が下位ブランチまたは上位ブランチに属しているかどうかにかかわらず、中央値である2つの値があるかどうかを判断する必要があります。私は私の例では上の枝に重複を入れます。

中央値は、等しい数の数値が数値よりも小さく、大きい数値です。 1,2,3,3,4,18,29,105,123 平均（または平均）がはるかに高い場合でも、中央値は4です。

私は中央値を決定するコードを含んでいませんでした。

​​3210

Answer 2

それは宿題でない限り最も簡単な解決策は、最初にデータをソートしてから、rootとして中央のアイテムを使用して、それぞれの半分を下に下降することにより、ツリーを構築することです。 Xaadeによって提案されたメソッドは と似ていますが、DetermineMedianの複雑さのためにはるかに遅い です。

もう1つの選択肢は、バランスの取れたツリー（http://en.wikipedia.org/wiki/Red-black_treeなど）を構築するアルゴリズムを実際に見て、要件に合っているかどうかを確認することです。

EDIT：Xaadeアルゴリズムの速度に関する誤った記述を削除する - 実際には速いソートと同じ速さである（n log n - 再帰のすべてのレベルで各要素をチェックする）もっとゆっくり。