如何查找排序集中元素的索引？

Question

我可以在O(logN)的排序集中找到一個元素（由BST支持）。現在我想要這個元素的索引。例如，在集合{1, 3, 4, 10}中，4的索引是2，並且1的索引是0。

顯然，我可以迭代該集合，所以這個簡單的解決方案是O(N)。我們可以使用可能的BST屬性和/或輔助數據結構來做得更好嗎？

Answer 1

通過一個簡單的BST，其中隨機插入元素的順序，您可以確定有多少元素確切地小於給定元素，而無需走樹。

如果你有一棵平衡的樹，比如紅黑樹，那麼由於樹的高度限制，你至少可以在索引上設置一個下限和上限。 如果向BST插入元素的順序不是隨機的，那麼您可以再次說出有關樹高度的內容，而無需走過它並給出近似索引的一些估計值。

至於輔助數據結構，您可以創建一個輔助字典，將元素映射到其索引。但是，構建該索引需要O（N），並且在將新元素添加到BST時索引變得陳舊，因此這僅適用於不頻繁更新的BST。

另一種解決方案是擴展具有兩個屬性的BST節點：索引和計數。該索引說明樹中有多少比此節點中的元素小的元素。伯爵說，當您上次更新該節點的索引時，BST中有多少元素。通過在BST上插入，刪除和搜索相對簡單的變化，不會影響超過一定時間的基本操作，並且可以直接在O（1）中獲取元素的索引。基本上，當您插入一個新節點時，對於您向下傳遞路徑的每個節點，如果新元素較小（即您的下一步是左側子節點），則增加該節點的索引和計數。當您找到新元素的位置時，您會根據其父項和基於其父項和左項目的子項爲其計數。 這會使元素大於新索引的索引，但當您通過引用父項的計數值來搜索元素時，您可以輕鬆更新這些元素 - 父項和子項的計數之間的差異會告訴您自您上次更新孩子的索引後發生了多少次小元素的插入，因此您只需將該差異添加到索引。