建立一個平衡二叉搜索樹

有沒有一種方法來建立一個平衡二叉搜索樹？建立一個平衡二叉搜索樹

例子：

1 2 3 4 5 6 7 8 9 

     5 
    /\ 
    3 etc 
    /\ 
    2 4 
/
1

我想沒有做到這一點，而無需使用更復雜的自平衡樹的方法。否則我可以自己做，但有人可能已經這樣做:)

感謝您的答案！這是最後的Python代碼：

def _buildTree(self, keys): 
    if not keys: 
     return None 

    middle = len(keys) // 2 

    return Node(
     key=keys[middle], 
     left=self._buildTree(keys[:middle]), 
     right=self._buildTree(keys[middle + 1:]) 
     )

來源

2010-05-23 Znarkus

對於每個子樹：

查找子樹的中間元素，並把那在樹的頂端。
查找中間元素之前的所有元素，並遞歸地使用此算法來獲取左側子樹。
查找中間元素之後的所有元素，並遞歸地使用此算法來獲取正確的子樹。

如果你先排序你的元素（如你的例子），找到一個子樹的中間元素可以在不變的時間內完成。

這是構建一次性平衡樹的簡單算法。它不是一個自平衡樹的算法。

這是在C＃中的一些源代碼，你可以自己嘗試：

public class Program 
{ 
    class TreeNode 
    { 
     public int Value; 
     public TreeNode Left; 
     public TreeNode Right; 
    } 

    TreeNode constructBalancedTree(List<int> values, int min, int max) 
    { 
     if (min == max) 
      return null; 

     int median = min + (max - min)/2; 
     return new TreeNode 
     { 
      Value = values[median], 
      Left = constructBalancedTree(values, min, median), 
      Right = constructBalancedTree(values, median + 1, max) 
     }; 
    } 

    TreeNode constructBalancedTree(IEnumerable<int> values) 
    { 
     return constructBalancedTree(
      values.OrderBy(x => x).ToList(), 0, values.Count()); 
    } 

    void Run() 
    { 
     TreeNode balancedTree = constructBalancedTree(Enumerable.Range(1, 9)); 
     // displayTree(balancedTree); // TODO: implement this! 
    } 

    static void Main(string[] args) 
    { 
     new Program().Run(); 
    } 
}

來源

2010-05-23 20:37:08

本文將詳細介紹：

樹再平衡的最佳時間和空間
http://www.eecs.umich.edu/~qstout/abs/CACM86.html

另外這裏：

單時間二進制搜索樹平衡：日/粗壯/沃倫（DSW）算法
http://penguin.ewu.edu/~trolfe/DSWpaper/

如果您真的想在飛行中做到這一點，您需要一個自平衡樹。

如果你只是想構建一棵簡單的樹，而不必去平衡它的麻煩，只需在元素插入到樹中之前隨機化元素。

來源

2010-05-23 20:34:23

數據，保證數據的中位數（或更準確地說，你的陣列中位數最近的元素）的根樹。等遞歸。

來源

2010-05-23 20:37:11

中位數不太正確的術語。首先，中位數可能不存在於原始數據中。例如，3和4的中位數是3.5。見http://en.wikipedia.org/wiki/Median – 2010-05-24 21:44:55

你是對的。顯然（從你參考的維基百科頁面）這個詞是medoid。我做了一個編輯。 – 2010-05-24 22:02:05

建立一個平衡二叉搜索樹

回答

相關問題