0

サイズ 1024 のランダムな二分探索木を生成しようとしていて、要素はランダムなソートセットである必要があります。手動で要素を追加することで二分探索木を手動で作成するコードを書くことはできますが、私は ' m サイズ 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);
            }
        }
    }
}
4

2 に答える 2

2

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

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

中央値は、同じ数の数がその数よりも少なくて多い場合の数になります。1,2,3,3,4,18,29,105,123 この場合、平均 (または平均) がはるかに高いにもかかわらず、中央値は 4 です。

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

BuildTreeItem(TreeItem Item, Array Set)  
{
  Array Smalls;
  Array Larges;
  Median = DetermineMedian(Set);
  Item.Value = Median;
  if(Set.Count() == 1)
    return;  
  for (int i = 0; int i < Set.Count(); i++)
  {
    if(Set[i] < Median)
    {
      Smalls.new(Set[i]);
    }
    else
    {
      Larges.new(Set[i]);
    }
  }
  Item.Lower = new TreeItem;
  Item.Upper = new TreeItem;
  BuildTreeItem(TreeItem.Lower, Smalls);
  BuildTreeItem(TreeItem.Upper, Larges);
}
于 2011-01-21T00:13:12.457 に答える
0

宿題でない限り、最も簡単な解決策は、最初にデータを並べ替えてから、真ん中のアイテムをルートとして使用し、各半分を下に向かってツリーを構築することです。Xaadeによって提案された方法は似ていますが、DetermineMedianの複雑さのためにはるかに遅くなります。

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

編集：Xaadeアルゴリズムの速度に関する誤ったステートメントを削除します-実際にはクイックソートと同じくらい高速です（n log n-log nレベルの再帰ですべてのレベルの再帰で各要素をチェックします）、なぜそれが遅いと推定したのかわかりません。

于 2011-01-21T01:42:40.747 に答える