用於表示和查詢未來時間間隔的數據結構

Question

我想表示未來系統中某個元素的預測狀態。元素可以處於狀態S1或S2。 S1預測是<t_start, t_end>形式的非重疊區間，其中t_是未來的相對時間。間隔的缺失意味着狀態是S2並且只有S1預測。主要的操作是添加預測的時間間隔和查詢任意未來時間的狀態。狀態查詢將比查詢更頻繁地發生幾個數量級。可以在有限範圍內的任何時間添加間隔，相對於現有時間間隔，可以以任何順序添加。另一個重要的操作是時間的進步，這意味着預測越來越接近並最終進入過去，在那裏他們可以被遺忘。預測可能很少被刪除，但這不是必需的。時間的基本模型可以是連續的，也可以離散爲整數時間步長。

我已經有一個使用鏈接列表的實現，其中列表中的位置表示時間（使用分散到整數的時間）並且節點內容是S1或S2。這隨着時間的推移而更新（您只需放棄第一個節點），並且查詢速度相當快（未來時間步數的線性）。但是，由於您列舉了所有可能的時間片，所以在添加預測方面它有點難看，並且隨着您增加時間範圍或時間片的精度而縮小。因此，我正在尋找一種替代方法（例如基於間隔以某種方式）。

Answer 1

一種可能性是將間隔存儲在二叉搜索樹中。如果您可以忍受其線性時間最壞的情況行爲，我會建議您使用splay tree，因爲它會自行調整以處理攤銷後的恆定時間內有利的查詢模式。

由於間隔不重疊，搜索BST非常簡單。如果查詢點包含在當前時間間隔中，那麼我們就完成了。如果它位於左側，則搜索左側子樹。如果它位於右側，則搜索右側子樹。