根據分數對用戶排序的數據結構的建議

根據得分計算與用戶ID和等級相關的得分。應支持以下功能。

鑑於這些要求，有沒有關於哪些數據結構最適合這些要求的建議？

2011-03-24 smahesh

我想你可以非常有效地使用訂單統計樹和散列表的組合。

訂單統計樹是一個增強二叉搜索樹，除了按排序順序存儲元素外，還允許通過樹中的索引查找元素。也就是說，該結構支持O（lg n）插入，刪除和按鍵查找值，以及O（lg n）查找給定其索引的元素。如果將分數存儲在此結構中，則可以輕鬆插入或更新新分數，並跟蹤樹中每個元素的排名。

爲了將用戶與他們的分數相關聯，您可以將此結構與從用戶ID映射到持有該用戶分數的順序統計樹中的節點的輔助哈希表映射。除了O（lg n）分數排名的查找之外，這會給你O（1）個玩家的分數。

希望這會有所幫助！

2011-03-24 04:47:30 templatetypedef

謝謝您的建議。我傾向於使用紅黑樹，它保存着孩子的數量（因此也是排名），但是在插入和刪除RB樹時（特別是在旋轉時）似乎存在一些併發問題。 – smahesh 2011-03-24 16:31:53

我沒有unserstand是否有方法來更新用戶使用順序統計樹的排名？ – 2018-01-25 10:37:41

使用內存中的SQLite數據庫。

2011-03-24 11:11:14

優先隊列怎麼樣？

每個人都會有一個分數，把它扔到優先級隊列中，然後它會按升序/降序優先級/值/等級/等級進行排序。

2011-03-24 23:23:48

二叉搜索樹，一種實現方式 - http://en.wikipedia.org/wiki/AA_tree

Space O(n)   O(n) 
Search O(log n) O(log n) 
Insert O(log n) O(log n) 
Delete O(log n) O(log n)

2011-03-24 23:47:10 Joyce

回答