哪裏可以找到均衡的樹實現？

我想知道是否有人知道在互聯網上的某個地方，我可以複製和粘貼（用於學習目的）二叉搜索樹的實現，實現均衡和算法以查詢有多少節點少於特定值。我希望能夠查詢這個數據結構並詢問「在這個數據結構中有多少個節點是< x？」整體目的是回答後一類型的查詢，但平衡也很重要，因爲我希望能夠處理大量不平衡的條目序列。哪裏可以找到均衡的樹實現？

我更喜歡Python，C，C++或Java中的實現，但其他人歡迎。

來源

2011-10-12 Gravity

這是功課？ –

不，不是。我正在尋找複製和粘貼這個來理解底層算法。然後，我也可以將它用作我正在編寫的算法的構建塊。 – Gravity

如果它仍然是相關的，你可以在每個節點保持樹的大小，就像在

http://www.codeproject.com/script/Articles/ViewDownloads.aspx?aid=12347&zep=HeightBalancedTree.h&rzp=%2fKB%2farchitecture%2favl_cpp%2f%2favl_cpp.zip

通知的FindComparable功能。如果找到該對象，則返回其索引（小於搜索對象的節點數）。

如果搜索到的對象不在樹中，您希望獲取大於搜索對象的最小節點的索引。

注意找不到對象時會發生什麼。最後節點::的getSize（節點:: GetRight時（節點）））或節點::的getSize（節點:: GetLeft（節點）））將被評估爲0，所以你有兩種情況：

如果最後一個回合是正確的（cmp> 0），您將獲得最小節點的索引，該節點小於搜索對象加上一個 - 這正是您想要的值。
如果剩下最後一個轉彎（cmp < 0），您將得到大於搜索對象減去一個的最小節點的索引。

因此，而不是返回尺寸（）時未找到對象，你可以返回：

index + (cmp < 0)?1:0;

來源

2012-06-15 22:04:04 Oren

哪裏可以找到均衡的樹實現？

回答

相關問題