Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
501 views
in Technique[技术] by (71.8m points)

c# - Building a balanced binary search tree

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:])
        )
See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

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

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...