用於排序的修改的二進制搜索樹？

我必須排序數組。除了現有的已存在的排序類型之外，我想知道這樣的算法是否可行，以及它的複雜程度如何。我有一個數組進行排序。我創建了一個二進制搜索樹。用於排序的修改的二進制搜索樹？

因此，如果我將數組的所有元素插入到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)。所以根據我的理解，這應該是一個有效的算法。

謝謝。

來源

2012-07-13 Arjun Abhynav

每個插入都是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）中進行排序。

來源

2012-07-13 13:10:28 Dino

謝謝。是的，我瞭解最壞的情況。想知道爲什麼這種排序從未在任何地方提及過！我以爲我發現了一些全新的東西。：D – 2012-07-13 13:17:13

我們在我的數據結構類中討論過這個問題，但我可以想象，如果人們沒有多說這些，那是因爲與其他O（nlogn）排序算法相比，它不必要的複雜，並且它可能慢得多在實踐中。也就是說，如果您使用AVL樹或其他確保了O（logn）插入的樹，那麼理論上這與合併排序（時間和空間複雜度）相當。類似的東西可能會讓你感興趣的是Heapsort。 – 2012-07-13 16:26:47

用於排序的修改的二進制搜索樹？

回答

相關問題