SortedContainers 中的 SortedList 到底是如何工作的？它真的是一个平衡的 BST 吗？
对于平衡二叉树来说，除了二叉树本身的属性外，它还多了一个属性，即任意两个叶子深度的最大差值不大于1，从而实现O(logn)的范围查询，并且是可变的（允许元素添加、删除）在 O(logn) 中）。
来自sortedcontainers.SortedList docs，它只说
Sorted list is a sorted mutable sequence.
在add函数中，它首先找到一个子列表，然后对该子列表进行 bisect.insort，据称其时间复杂度约为 O(logn)。如果错误请纠正我，在我看来 SortedList 更多的是排序子列表的数组。它将列表拆分为 n/(logn) 个子列表，每个子列表的大小为 logn。定位一个子列表需要 O(logn - loglogn)。子列表上的排序需要 O(logn)，总共大约为 O(logn)。
对此更了解的人可以帮助解释 SortedList 的真正工作原理吗？它真的是一个平衡的 BST 吗？谢谢。
for a balanced BST, it has an additional property of max difference of any two leaves' depth are no greater than 1, in additiona to BST property itself, thus achieving range query in O(logn) and is mutable (allowing element add, del in O(logn) ).
from sortedcontainers.SortedList docs, it only says
Sorted list is a sorted mutable sequence.
In the add function, it first find a sublist, then does bisect.insort on that sublist, which is claimed to be O(logn) in approx. Correct me if wrong, it seems to me SortedList is more of an array of sorted sublists. It splits list into n/(logn) sublists, each of size logn. locating one sublist takes O(logn - loglogn). and insort on sublist takes O(logn), in total approx O(logn) as claimed.
could someone more knowledgable on this help explain how SortedList really works? and is it really a balanced BST or not? thanks.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论