用于排序的修改的二进制搜索树？

问题描述：

我必须排序数组。除了现有的已存在的排序类型之外，我想知道这样的算法是否可行，以及它的复杂程度如何。我有一个数组进行排序。我创建了一个二进制搜索树。用于排序的修改的二进制搜索树？

因此，如果我将数组的所有元素插入到BST中，然后在对树进行按顺序遍历时将它们一个一个地分配给数组，那么我将实现一个排序结果。（虽然消耗更多的空间复杂度，因为树的节点，不是就地排序。）

int i=0; 

void sort_by_inorder(node *n) 
{ 
    if(n==NULL) 
    { 
     return; 
    } 
    sort_by_inorder(n->leftchild); 
    array[i++]=n->data; 
    sort_by_inorder(n->rightchild); 
}

我知道BST不允许重复插入，所以也许我们可以考虑修改BST插入算法为< =为左子树或者右子树的> =。

这是一个很好的实现（可行）吗？什么是复杂性？

遍历复杂度平均为O(n)。插入只是O(log n)。所以根据我的理解，这应该是一个有效的算法。

谢谢。

每个插入都是O（log n），所以你实际上以O（n * log n）结尾 – AlexDev 2012-07-13 12:57:03

你应该做一个有序的遍历，而不是一个预置的遍历。 – 2012-07-13 16:20:08

@DylanM。是。抱歉。我的代码是遍历的，但名字是先序遍历的。编辑它。 – 2012-07-13 21:34:34

答

在一般的二叉搜索树中，插入时间实际上是最坏情况下的O（n）。您需要一个平衡的树来使操作成为O（log（n））。

所以在一般的BST中，您的方法允许您在O（n^2）中进行排序。

谢谢。是的，我了解最坏的情况。想知道为什么这种排序从未在任何地方提及过！我以为我发现了一些全新的东西。：D – 2012-07-13 13:17:13

我们在我的数据结构类中讨论过这个问题，但我可以想象，如果人们没有多说这些，那是因为与其他O（nlogn）排序算法相比，它不必要的复杂，并且它可能慢得多在实践中。也就是说，如果您使用AVL树或其他确保了O（logn）插入的树，那么理论上这与合并排序（时间和空间复杂度）相当。类似的东西可能会让你感兴趣的是Heapsort。 – 2012-07-13 16:26:47

用于排序的修改的二进制搜索树？

相关推荐