balanced binary search tree using sortedset

Please help I've been trying to generate a random binary search tree of size 1024 and the elements needs to be random sortedset ... I'm able to write a code to c开发者_如何学编程reate a binary search tree manually by adding elements manually but I'm unablele yo write a code that would generate a random balanced binary tree of size 1024 then use try to find a key in that tree ... please please and thank u ahead ....

Edit added code from comments

ya it is homework... and this is what i got so far as code:

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);
            }
        }
    }
}

---

Use recursion. Each branch generates a new branch, select the middle item in the unsorted set, the median. Put it in the current item in the tree. Copy all items less than the median to another array, send that new array to the call of the same method. Copy all items greater than the median to another array, send that new array to the call of the same method.\

Balanced trees have to have an odd number of items, unless the main parent node is not filled in. You need to decide if there are two values that are the Median, whether the duplicate belongs on the lower branch or upper branch. I put duplicates on the upper branch in my example.

The median will be the number where an equal amount of numbers is less than and greater than the number. 1,2,3,3,4,18,29,105,123 In this case, the median is 4, even though the mean (or average) is much higher.

I didn't include code that determines the median.

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);
}

---

Unless it is homework the easiest solution would be to sort data first and then build a tree by using middle item as root and descending down each half. Method proposed by Xaade is similar , but much slower due to DetermineMedian complexity.

The other option is to actually look at algorithms that build balanced trees (like http://en.wikipedia.org/wiki/Red-black_tree ) to see if it fits your requirements.

EDIT: removing incorrect statement about speed of Xaade algorithm - it is actually as fast as quick sort (n log n - check each element on every level of recursion with log n levels of recursion), not sure why I estimated it slower.