查找SortedDictionary中項目索引的最有效方法

我正在使用已排序的字典來維護項目列表，其中我經常需要監視頂級x項目的狀態。每次我更新一個項目時，我想快速找出我所指的項目正在使用的索引。我知道我可以枚舉整個列表並計算出我的位置，但是我在查找具有O（log n）或更好時間的東西，畢竟所有已排序的字典都位於RedBlack樹上。每個節點應該能夠跟蹤它的孩子，這應該是一個快速計算。查找SortedDictionary中項目索引的最有效方法

來源

2010-09-07 Superman

你有沒有考慮切換到'SortedList '？它可以通過索引進行'O（1）'檢索。儘管如此，它在插入和刪除方面確實有着不俗的表現。 – Ani 2010-09-07 23:49:24

由於這是一個樹結構，因此沒有索引的概念。只有具有左側和右側子鏈接的節點。 – 2010-09-07 23:51:09

我不明白這個問題 - 樹中的項目沒有索引。 – Lee 2010-09-07 23:53:02

您可以簡單地改變你的SortedDictionary<TKey, TValue>爲SortedList<TKey, TValue>，然後使用IndexOfKey(key)：

var s = new SortedList<string, string> 
    { { "a", "Ay" }, { "b", "Bee" }, { "c", "Cee" } }; 

// Outputs 1 
Console.WriteLine(s.IndexOfKey("b"));

內部使用Array.BinarySearch<TKey>()，所以這將是爲O（log ñ），這是爲O快（ñ）（如果你通過遍歷它從前到後搜索）。

來源

2010-09-08 00:06:51 Timwi

如果你需要一個O（1）插入和除了O（log（n）search？ – 2012-03-29 13:09:46

@eranotzer：那麼你將需要使用一個'字典'（你不能有O（1）插入，如果它應該總是排序），你需要手動排序它進行O（log n）搜索（例如，通過使用'dic.Keys.ToList（）'，接着'Sort'然後'IndexOf'） – Timwi 2012-03-30 13:11:14

可以構建樹結構以通過索引訪問項目或以lgN時間報告現有項目的索引，只需要非常少的額外時間來插入和刪除。一種方法是跟蹤每個節點的左右分支中有多少項（插入或刪除時，更改子節點的計數時更改父節點的節點數）。但是，如果一個以樹爲基礎的結構不提供這樣的設施，我知道沒有簡單的方法來改造它。

來源

2010-09-08 00:10:28 supercat

這是我正在尋找的角度 - 但是我正在尋找一個已經擁有它的結構，或者一個簡單的改造方法。 – Superman 2010-09-08 02:10:05

查找SortedDictionary中項目索引的最有效方法

回答

相關問題