查找中位數訂單統計樹在O（1）時間

Question

我被要求創建一個數據結構，其功能類似於插入節點，尋找具有一定的鍵值取O（LOGN）的節點。 我被要求在O（1）時間內找到中位數。

我一直在想使用順序統計樹，將選擇具有N/2級節點找到位數？

我在這裏看到了類似的問題，但我想:(Find median in O(1) in binary tree一個更好的解釋）

任何想法？

謝謝。

Answer 1

是的，在小區（N/2）的位置（從1開始）的元件確實是中位數（假定序列的大小爲奇數）。但是，使用順序統計樹來查找某個第k個位置上的元素是O（lg n），而不是O（1）。

你應該知道的是：給定一個完美的二叉搜索樹（二叉搜索樹，其中所有的內部節點有兩個孩子，所有的樹葉具有相同的深度或相同級別），中位數是完全根。更一般地說，如果您有一個二叉搜索樹結構，其中每個節點也存儲其子樹中的節點數，並且它發生的情況是，根的左邊和右邊的孩子都有相同的數字，那麼根就是中位數。這種情況是相當有限的，所以一個想法是平衡二叉搜索樹以增加根的概率爲中位數。

另一個想法是：保持二叉搜索樹和指示一個額外的變量（指針）的中位數是現在。然後，對於每個插入/刪除操作，更新此指針。

希望有幫助！

Answer 2

我相信恩佐中村所說的發現第k個位置是O（log n）是使用red-black binary search tree與certain twist。在每個節點上，您還存儲該節點子樹的大小。這樣，您可以利用二叉查找樹的屬性來查找哪個值是O（log n）中的第k個值。然而，如果二叉搜索樹的根節點是a）奇數個節點並且b）完美的平衡樹，並且紅黑二叉搜索樹不一定是完美平衡的，則二叉搜索樹的根節點僅保證爲中間值，所以即使上述方法也不能保證這一點。

有一種着名的問題叫做「running median」，你從中位數開始，然後在每次給予新元素時必須計算新的中位數。你可以通過創建一個堆，它的根是中位數，左邊的子樹是一個小堆，右邊的子樹是一個最大堆來解決這個問題。插入到堆中的時間是O（log n）時間，但是一旦樹被創建，中位複製總是O（1），因爲結構保證根節點在所有情況下都是中位數。

我覺得應該可以概括這個問題找到在固定時間內的第k個值，只要k沒有改變。在運行中值問題中，每當一個節點比另一個大2個節點時，我們需要重新平衡左右子樹。我們可以概括這個問題，說我們在每次大小超過k時重新平衡左邊的子樹（如果它是第k個最小的）或右邊的子樹（如果它是第k個最大的），插入時間和重新平衡時間仍然都是O（log n ）。現在我們不能使用這種方法來找到任何第k個值，就像我們可以使用RB樹一樣，但是對於一個特定的k值，您將在不變的時間內恢復其值。這個過程也在這個paper中被引用，它具體說明了在恆定時間內檢索第k個值的能力。