用於後繼查找的最佳二叉搜索樹？

給定一組密鑰並選擇這些密鑰的相關概率，有許多算法可用於查找optimal binary search trees。以這種方式生成的二叉搜索樹將具有查找這些元素的最低預期時間。但是，這種二叉搜索樹在其他方面可能不是最優的。例如，如果您嘗試查找樹中未包含的鍵，查找時間可能非常大，因爲樹可能不平衡以優化對某些元素的查找。用於後繼查找的最佳二叉搜索樹？

我目前有興趣瞭解如何從一組鍵中構建二叉查找樹，其目標是最大限度地減少找到具有某種特定價值的後繼所需的時間。也就是說，我希望該樹的結構可以通過給定一些隨機密鑰k來儘可能有效地找到k的後繼者。我碰巧預先知道給定的隨機密鑰落入樹的任何兩個密鑰之間的概率。

有沒有人知道這個問題的算法？或者我錯誤地認爲，構建最優二叉搜索樹的標準算法不會爲此用例生成有效的樹？

來源

2011-12-28 templatetypedef

'後繼者'將成爲一個糟糕的新標籤。如果你堅持爲此創建一個新的標籤，我們可以找到一些不太通用和可濫用的東西嗎？ – Charles 2011-12-29 06:13:29

@查爾斯 - 是的，讓我擺脫這一點。對於那個很抱歉！ – templatetypedef 2011-12-29 06:18:11

非常感謝。您今天很高興新標籤刪除論者卡巴爾。 – Charles 2011-12-29 06:20:44

所以現在我覺得很傻，因爲這個問題很簡單。 :-)

您可以使用標準的現成算法構建最優二叉搜索樹，以構建該組鍵的二叉搜索樹。然後，您對每個節點進行註釋，以便在其之前存儲其密鑰和密鑰之間的整個範圍。這意味着您可以通過對最佳構建的樹進行標準搜索來高效地找到後繼者。如果在任何時候發現你正在查找的密鑰都包含在某個節點的範圍內，那麼你就完成了。換句話說，找到後繼者就相當於只搜索BST中的值。

來源

2011-12-28 23:44:18 templatetypedef

難道這只是找到* a *後繼者，不一定是*後繼者？ – 2011-12-29 00:18:51

@Lasse V. Karlsen-如果每個節點只存儲其關鍵字和前一個關鍵字之間的範圍，則只有當找到與新值落入的兩個關鍵字之間的特定範圍對應的節點時，搜索纔會終止。這意味着當你找到任意的後繼者時你不會停下來，因爲搜索關鍵字在範圍內的唯一時間就是該範圍在關鍵的後繼結束時。那有意義嗎？或者我錯過了什麼？ – templatetypedef 2011-12-29 00:25:03

對不起，你是對的，我沒有完全理解其含義。 – 2011-12-29 00:26:49

用於後繼查找的最佳二叉搜索樹？

回答

相關問題