如何在O（N）时间构建二叉树？

继续前面的问题here我很想知道如何从N个未排序的大整数的数组中构建一个N次的二叉树？如何在O（N）时间构建二叉树？

2016-03-07 Shane MacLaughlin

这很好。祝你好运。你有问题吗？ –

据我所知，这是不可能的，因为这意味着你可以在O（n）时间排序列表。 –

是的。如何在O（n）时间从未排序的整数构建二叉树？ –

好吧，只是为了完整性...问题中的二叉树是从一个数组构建的，并且每个数组元素都有一个叶。它使它们保持原有的索引的顺序，的值不是的顺序，所以它不会让你神奇地让你在线性时间排序。它也需要平衡。

打造线性一次这样的树，你可以用一个简单的递归算法是这样的（使用基于0的索引）：

//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]); 
    } 
}

来源

2016-03-07 21:30:23

谢谢，我误解了不需要排序的树。 –

@MattTimmermans：我将帽子重新格式化为粗体，因为帽子（至少在SO上）被认为是粗鲁的。 –

除非在列表中有一些前提条件允许您在常量时间内为每个项目计算树中的位置，否则无法'构建'，即按顺序将项插入到O中的树中（N）时间。每个插入必须最多与Log M次进行比较，其中M是树中已有项目的数量。

来源

2016-03-07 19:23:20 tt9

这就是我的理解，。这就是说，仅仅因为我们没有看到算法并不意味着它不存在。 –

二叉搜索树是计算机科学中研究最多的主题之一。他们建立在比较原则的基础上。已经证明，基于BST的最快插入比较是O（log n）。要获得比这更快的速度，你需要在数据集中有一些预先存在的结构。例如，如果你知道你的数据集已经被排序了，你可以想出一个更快的方法来构建树。 – tt9

@ user2313300是真实的，但这意味着能够解决O（n）中的'SORT'，这已被证明是不可能的。 –

我同意，这在一般的似乎是不可能的（假设我们有一个一般的，全序集小号的ñ项目。）下面是一个非正式的说法，我本质上降低BST建设上小号到排序问题S。

非正式的论点。让S是一组N元素。现在构建二进制搜索树T，其存储来自S的项目O（N）时间。

现在，当您访问它们时，请执行树的逐步走动并打印叶子的值。您基本上对S中的元素进行了排序。这带你O（| T |）步骤，其中| T |是树的大小（即节点的数量）。（在BST的大小是O（N日志N）在最坏的情况下。）

如果| T | = O（N日志N）那么你只解决了普通的排序问题在O（ N日志N）这是一个矛盾的时间。

来源

2016-03-07 19:33:31 blazs

我同意这是不可能的一般情况下，有大量的可能值的项目正在排序。如果要排序的项目有少量可能的值，并且这些值可以枚举，则可以使用类似计数排序的东西在O（N）中进行排序，请参阅https://en.wikipedia.org/wiki/。 Counting_sort如果我们可以在这种情况下在O（n）中排序，我想我们也可以构造一棵树。 –

**如果**给出了一个排序数组，那么你可以在线性时间内构建一个二叉搜索树，但是只有当表达式需要* O（N）*空间时（即你使用类似于堆的方式使用数组）。我认为问题在于这是否可能。 – blazs

含糊的想法：1.排序数组; 2.将排序数组的中间元素放入根中; 3.对子阵列进行递归（第一和最后一半），即将它们的根分别作为第二和第三个元素。（索引i处元素的左边孩子是2 * i;右边孩子是2 * i + 1。） – blazs

我有一个想法，它是如何可能的。

使用RadixSort排序数组，这是O（N）。此后，用递归程序插入到叶子，如：

node *insert(int *array, int size) { 
    if(size <= 0) 
    return NULL; 
    node *rc = new node; 
    int midpoint = size/2; 
    rc->data = array[midpoint]; 
    rc->left = insert(array, midpoint); 
    rc->right = insert(array + midpoint + 1, size - midpoint - 1); 
    return rc; 
}

由于我们没有从上往下遍历树，但总是将节点连接到当前叶子，这也是O（1）。

来源

2016-03-07 20:55:24 maxihatop

如果对整数没有上限，则不能在O（N）中使用RadixSort。 – Mickey

如何在O（N）时间构建二叉树？

回答

相关问题