使用sortedset的平衡二叉搜索树

请帮助我一直在试图生成一个大小为1024的随机二叉搜索树，并且元素需要随机排序...我可以编写代码来创建二分查找通过手动添加元素手动，但我无法哟写一个代码，将生成一个大小为1024的随机平衡二叉树，然后使用尝试找到该树中的一个键...请请，并感谢你提前...使用sortedset的平衡二叉搜索树

编辑添加代码注释

雅它是家庭作业......这是我得到了什么，只要代码：

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

来源

2011-01-20 Sam Omar

使用递归。每个分支都会生成一个新分支，在未排序集合中选择中间项目的中位数。将它放在树中的当前项目中。将小于中位数的所有项目复制到另一个数组，将该新数组发送到相同方法的调用。将大于中位数的所有项目复制到另一个数组，然后将该新数组发送到相同方法的调用。\

平衡树必须具有奇数个项目，除非主父节点未填写。需要确定是否有两个值是中位数，重复属于下分支还是上分支。在我的示例中，我在上面的分支上添加了重复项。

中位数将是等于数量小于和大于数字的数字。 1,2,3,3,4,18,29,105,123 在这种情况下，即使平均值（或平均值）高得多，中位数也是4。

我没有包含确定中位数的代码。

3210

来源

2011-01-21 00:13:12

所以我所需要的只是添加中位数的代码，并且会生成树。 – 2011-01-21 02:06:57

除非是功课最简单的解决办法是将数据排序第一，然后通过中间产品为根，降下来各占一半建在树上。 Xaade提出的方法类似于 ~~，但由于确定媒体复杂性~~ 而速度较慢。

另一种选择是实际查看构建平衡树的算法（如http://en.wikipedia.org/wiki/Red-black_tree）以查看它是否符合您的要求。编辑：删除有关Xaade算法速度的不正确陈述 - 它实际上与快速排序一样快（n log n - 用递归的log n级别检查每个递归级别上的每个元素），不确定为什么我估计它比较慢。

来源

2011-01-21 01:42:40

雅是功课...这是我到目前为止的代码。使用系统的 – 2011-01-21 01:52:45

使用sortedset的平衡二叉搜索树

回答

相关问题