通過增大BST值，找到值在特定範圍內的二叉搜索樹中的節點總數

我想擴充二叉搜索樹，以便在O（h）時間內仍支持搜索，插入和刪除操作，然後我想實現一個算法來查找給定範圍內所有節點值的總和。通過增大BST值，找到值在特定範圍內的二叉搜索樹中的節點總數

2015-10-30 Amir Hossein F

聽起來像一個偉大的目標。你有什麼嘗試？你有哪個部分有問題。已經有很多關於二叉樹的文檔可以參考。 – miltonb

嗯，我環顧四周，唯一接近這個問題，我發現是使用不是一個擴增的分段樹。我還找到了一個基本上使用AVL樹的解決方案。但是我想擴充BST，然後在特定的範圍內找到節點的總和。我試圖從下到上向每個節點添加累積和，但是之後我堅持下去。我真的不知道這件事。 –

如果向BST類添加其他數據結構，特別是Hashmap或Hashtable。您的keys將是您的BST包含的不同數字，以及您的values每個數字的出現次數。 BST search(...)不會受到影響，但insert(...)和delete(...)將需要輕微的代碼更改。

插入

當添加節點到BST檢查，看是否該值在HashMap中存在的一個關鍵。如果它由1存在增量出現次數。如果它不存在，將它添加到HashMap中與1

的初始值刪除

當刪除減量HashMap中的出現次數（假設你沒有被告知要刪除不存在的節點）

總和

現在的和F結

sum(int start, int end)

您可以反覆檢查你的HashMap來看看它在你的地圖和他們的出現次數存在從範圍內的數字。使用這個，您可以通過將地圖中所有值在範圍乘以其出現次數的值相加來構建出您的總和。

複雜性

空間：O（n）的時間總和的方法：O（範圍大小）。
所有其他方法時間複雜度不受影響。

你沒有提到空間限制，所以希望這是好的。我很感興趣，看看你是否可以使用BST的特性來更高效地解決這個問題。

來源

2015-10-30 10:32:33

通過增大BST值，找到值在特定範圍內的二叉搜索樹中的節點總數

回答

相關問題