建立一个平衡的二叉搜索树 [英] Building a balanced binary search tree

问题描述

有没有建立一个平衡的二叉搜索树的方法

？例如：

  1 2 3 4 5 6 7 8 9 
 
 $ 5 b $ b / \ 
 3等
 / \ 
 2 4 
 / 
 1 
  

我想有这样做的方法，而不使用更复杂的自平衡树。否则，我可以做我自己，但有人可能已经这样做了：）

---

有关问题的答案谢谢！这是最后的Python代码：

 高清_buildTree（自我，键）：
如果没有密钥：
返回无
 
中间= LEN（键）// 2 
 
返回节点（
键=键[中]，
左=自我。 _buildTree（键[：中]），
右= self._buildTree（键[中等+ 1：]）
）
  

解决方案

对于每个子树：

• 找到中间和子树的要素投入，在树的顶端。


• 找到中间元素之前的所有元素，并使用该算法递归以获得左子树。


• 找到中间元素之后的所有元素，并使用该算法递归以获得右子树。

如果您排序你的元素第一次（在你的例子）找到一个子树的中间元素可以在固定的时间来完成。

这是一个简单的算法构建一个一次性的平衡树。它不是一个自我平衡的树算法

下面是在C＃中的一些源代码，你可以尝试一下：

 公共类节目
 {
类树节点
 {
公共int值; 
公共树节点左; 
公共树节点权利; 
} 
 
树节点constructBalancedTree（列表< INT>的价值观，INT分钟，INT最大值）
 {
如果（最小==最大）
返回NULL ; 
 
 INT中位数= MIN +（最大 - 最小）/ 2; 
返回新的TreeNode 
 {
值=值[中位数]，
左= constructBalancedTree（值，最小值，中位数），
右键= constructBalancedTree（值，中间值+ 1，最大值）
}; 
} 
 
树节点constructBalancedTree（IEnumerable的< INT>的值）
 {
返回constructBalancedTree（
 values​​.OrderBy（X => X）.ToList （），0，values​​.Count（））; 
} 
 
无效的run（）
 {
树节点balancedTree = constructBalancedTree（Enumerable.Range（1,9））; 
 // displayTree（balancedTree）; // TODO：实现这个！ 
} 
 
静态无效的主要（字串[] args）
 {
新计划（）的run（）; 
} 
} 
  

Is there a method to build a balanced binary search tree?

Example:

1 2 3 4 5 6 7 8 9

       5
      / \
     3   etc
    / \
   2   4
  /
 1

I'm thinking there is a method to do this, without using the more complex self-balancing trees. Otherwise I can do it on my own, but someone probably have done this already :)

---

Thanks for the answers! This is the final python code:

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:])
        )

解决方案

For each subtree:

• Find the middle element of the subtree and put that at the top of the tree.
• Find all the elements before the middle element and use this algorithm recursively to get the left subtree.
• Find all the elements after the middle element and use this algorithm recursively to get the right subtree.

If you sort your elements first (as in your example) finding the middle element of a subtree can be done in constant time.

This is a simple algorithm for constructing a one-off balanced tree. It is not an algorithm for a self-balancing tree.

Here is some source code in C# that you can try for yourself:

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

这篇关于建立一个平衡的二叉搜索树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！