我目前在bit trie中存儲了大量的無符號32位整數（有效地爲32位值中的每個位形成一個帶有節點的二叉樹）。這對快速查找精確值非常有效。是否有可能有效地搜索bit-trie的值小於密鑰？
我現在希望能夠搜索可能存在或不存在於密鑰樹中的密鑰，並找到小於或等於搜索密鑰的第一個密鑰的值。 這是有效的可能與位特里，或者我應該使用不同的數據結構？
由於速度和緩存局部性，我正在使用trie，並且最好也不想犧牲。
例如，假定該線索有兩個密鑰加入：
0x00AABBCC0x00AABB00和我的現在檢索的密鑰不存在，0x00AABB11。我想找到樹中第一個鍵值爲< =搜索鍵，在這種情況下，它將是0x00AABB00的節點。
雖然我已經想到了一個可能的算法如此，我尋求如果是有效的具體信息可能和/或是否有已知算法這一點，這無疑會比我好擁有。
我們可以將位特里思想爲二叉搜索樹。實際上，它是一個二叉搜索樹。以32位字節樹爲例，假設左側子樹爲0，右側子樹爲1.對於根，左側子樹爲小於0x80000000的數字，右側子樹爲不小於0x80000000的數字，依此類推，等等。因此，您可以使用類似的方法來查找不大於二叉搜索樹中的搜索關鍵字的最大項目。不要擔心回溯，它不會回溯太多，也不會改變搜索的複雜性。 當您匹配失敗的位特里，只是回溯找到失敗節點最近的祖先的最右邊的孩子。
32位比特樹要求訪問32個節點以確定是否存在特定值。如果特里包含兩個項目0x80000001和0x7ffffffff，並且查詢第一個值<= 0x800000000，則它必須沿着正確的路徑一路下降到0x80000001，回溯到根目錄，然後沿着左邊的路徑往下爲0x7FFFFFFF。所以，是的，它的複雜度是O（n），其中n是比特數。最壞的情況需要3倍的時間。當然，平均情況下回溯可能只是少數額外的節點。 –
@JimMischel是的，我認爲它會很有效。要比較兩個32位整數，最糟糕的情況需要比較所有32位。爲了使位特徵更有效，也許我們可以使用4叉樹或16叉樹實現，但是實現二叉樹。 –
好的 - 這幾乎是我的想法，謝謝:) –
如果數據是靜態的 - 您不會添加或刪除項目 - 那麼我會仔細看看使用二元搜索的簡單數組。你犧牲了緩存局部性，但這可能不是災難性的。我本身並沒有將緩存局部性看作是終點，而是一種快速構建數據結構的手段。
通過在數組中創建平衡二叉樹，您可能會獲得更好的緩存局部性。位置0是根節點，位置1是左節點，位置2是右節點等。它與用於二進制堆的結構相同。如果您願意爲每個節點分配另外4個字節，則可以將其設置爲左線程二叉樹，以便如果您搜索X並最終以下一個更大的值結束，那麼在該左邊的線程之後會給出下一個更小的值。總而言之，儘管如此，在一般情況下，我不明白這可以超越普通陣列。
很大程度上取決於數據的稀疏程度和範圍。如果您正在查看範圍在0到40億之間的數千個可能值，那麼二分法搜索看起來非常有吸引力。如果你正在談論5億個不同的值，那麼我會考慮分配一個位數組（500兆字節）並使用線性反向掃描進行直接查找。這會給你非常好的緩存局部性。
謝謝吉姆！它不是靜態的，但是它的讀取量遠遠大於它所寫的。我還沒有很好地處理數據量，但我會說一百萬或更多的條目。參賽作品將以16到100萬或2的間隔分隔。請您介紹位陣列的想法嗎？ （每16位增加一位？）（儘管250MB聽起來好像太多了，太多了。） –
@DavidM：假定位陣列的想法是分配一個40億（2^32）位的數組（範圍是一個32位整數）。如果你有很多數字，那麼它們之間的平均距離會相對較小，探頭加順序掃描將會非常快。只有數百萬（或數千萬）的項目，數字間隔太大，順序掃描可能會太昂貴。我犯了一個錯誤。該位陣列需要500 MB，而不是250 MB。 –
當找到該項目時，最佳情況下，位特洛伊走32個節點。
像std::map或java.util.TreeMap這樣的紅黑樹中的一百萬個條目只需要log2（1,000,000）或每個查詢約20個節點，最壞的情況。而且你並不總是需要到達樹的底部，使平均情況有吸引力。
回溯時發現<=的區別更加明顯。
你擁有的項目越少，越好的情況下爲紅黑樹
至少，我會比任何解決紅黑樹。
似乎一般情況下會涉及一些回溯。在最壞的情況下，回溯可能非常昂貴，不是嗎？ –
@JimMischel這就是我所擔心的。是否有更好的具有相似屬性的數據結構（對<=，良好緩存局部性，快速搜索） –