哪里可以找到均衡的树实现？

我想知道是否有人知道在互联网上的某个地方，我可以复制和粘贴（用于学习目的）二叉搜索树的实现，实现均衡和算法以查询有多少节点少于特定值。我希望能够查询这个数据结构并询问“在这个数据结构中有多少个节点是< 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

哪里可以找到均衡的树实现？

回答

相关问题