返回一個二叉樹中的項目的排序子集

我有很多節點以通常的方式存儲在二叉樹中，以便它們根據存儲在每個節點中的某些值進行排序;也就是說，可以通過樹從左到右遞歸併按照排序順序獲得總集。返回一個二叉樹中的項目的排序子集

但是，我有一個很大的單獨的數組指針，指向樹中的一個節點子集，並且此數組中的順序是隨機的。

我希望能夠快速排序這個數組。有什麼方法可以回溯到二叉樹結構以使其更快？如有必要，我可以將成員添加到任何節點。

謝謝！

來源

2013-02-26 Robotbugs

通過在節點中添加一個標誌，您可以獲得運行時爲O(t+a)（t是樹的大小，a是數組的大小）。這是通過首先設置數組中的標誌，然後遍歷樹並選取標記的值來完成的。

這隻有在您的樹僅比陣列大log a倍時纔有利。如果t >> quicksort肯定是首選的方法，因爲它的運行時間爲O(a * log a)。

來源

2013-02-26 23:32:36

謝謝，我在想，我將不得不退後快速排序。 – Robotbugs 2013-02-27 00:27:35

實際上，如果我最初在-1樹中存儲索引號，它可能比O（t * a）更快。然後，我可以讓數組中的一個通過，並將數組偏移量寫入樹結構的索引編號成員中，然後遍歷該樹並將大於等於0的索引列表寫入輔助數組（設置它們在使用後回到-1），最後我可以使用索引列表對數組進行排列。如果O（t）是>> O（a），那麼它會到達O（t）。 – Robotbugs 2013-02-27 00:32:40

但是在我的情況下t >> a，所以quicksort看起來是最好的選擇。 – Robotbugs 2013-02-27 00:33:56

返回一個二叉樹中的項目的排序子集

回答

相關問題