如何在O(N)时间构建二叉树? [英] How to build a binary tree in O(N ) time?

问题描述

接着上一个问题

Following on from a previous question here I'm keen to know how to build a binary tree from an array of N unsorted large integers in order N time?

推荐答案

确定，仅出于完整性考虑...有问题的二进制树是从数组构建的，每个数组元素都有一个叶子.它使它们保持原始的 index 顺序，不值顺序，因此，它不能神奇地使您按线性时间对列表进行排序.它还需要保持平衡.

OK, just for completeness... The binary tree in question is built from an array and has a leaf for every array element. It keeps them in their original index order, not value order, so it doesn't magically let you sort a list in linear time. It also needs to be balanced.

要在线性时间内构建这样的树，您可以使用像这样的简单递归算法(使用从0开始的索引):

To build such a tree in linear time, you can use a simple recursive algorithm like this (using 0-based indexes):

//build a tree of elements [start, end) in array
//precondition: end > start
buildTree(int[] array, int start, int end)
{
    if (end-start > 1)
    {
        int mid = (start+end)>>1;
        left = buildTree(array, start, mid);
        right = buildTree(array, mid, end);
        return new InternalNode(left,right); 
    }
    else
    {
        return new LeafNode(array[start]);
    }
}

这篇关于如何在O(N)时间构建二叉树?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！