使用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的平衡二叉搜索樹

回答

相關問題