二叉树在 O(1) 中获取最小元素
我多次访问二叉树的最小元素。哪些实现允许我在恒定时间内访问最小元素，而不是O(log n)？
I'm accessing the minimum element of a binary tree lots of times. What implementations allow me to access the minimum element in constant time, rather than O(log n)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（8）
根据您的其他要求，min-heap 可能就是您正在寻找的。它为您提供了最小元素的恒定时间检索。
但是，您无法像使用简单的二叉搜索树一样轻松地执行其他一些操作，例如确定值是否在树中。您可以查看 splay 树，一种自平衡二叉树，它提供了改进的最近访问的元素的访问时间。
Depending on your other requirements, a min-heap might be what you are looking for. It gives you constant time retrieval of the minimum element.
However you cannot do some other operations with the same ease as with a simple binary search tree, like determining if a value is in the tree or not. You can take a look at splay trees, a kind of self-balancing binary tree that provides improved access time to recently accessed elements.
在 O(log n) 中找到它一次，然后将要添加的新值与此缓存的最小元素进行比较。
UPD：如果删除最小元素，这将如何工作。您只需要再花费一次 O(log n) 时间并找到新的。
假设您的树中有 10 000 000 000 000 个整数。每个元素在内存中需要 4 个字节。在这种情况下，您的所有树都需要大约 40 TB 的硬盘空间。在这棵巨大的树中搜索最小元素应该花费的时间 O (log n) 大约是 43 次操作。当然，这不是最简单的操作，但无论如何，即使对于 20 年历史的处理器来说，它也几乎没什么。
当然，如果这是一个现实世界的问题，那么这是实际的。如果出于某些目的（也许是学术目的）您需要真正的 O(1) 算法，那么我不确定我的方法是否可以在不使用额外内存的情况下为您提供这样的性能。
Find it once in O(log n) and then compare new values which you are going to add with this cached minimum element.
UPD: about how can this work if you delete the minimum element. You'll just need to spend O(log n) one more time and find new one.
Let's imagine that you have 10 000 000 000 000 of integers in your tree. Each element needs 4 bytes in memory. In this case all your tree needs about 40 TB of harddrive space. Time O (log n) which should be spent for searching minimum element in this huge tree is about 43 operations. Of course it's not the simplest operations but anyway it's almost nothing even for 20 years old processors.
Of course this is actual if it's a real-world problem. If for some purposes (maybe academical) you need real O(1) algorithm then I'm not sure that my approach can give you such performance without using additional memory.
这可能听起来很愚蠢，但如果您主要访问最小元素，并且不改变树太多，那么在添加/删除（在任何树上）时维护指向最小元素的指针可能是最好的解决方案。
This may sound silly, but if you mostly access the minimum element, and don't change the tree too much, maintaining a pointer to the minimal element on add/delete (on any tree) may be the best solution.
遍历树的时间总是 O(log n)。树的实现是你自己写的吗？您始终可以简单地将当前最低值元素的引用与数据结构一起存储，并在添加/删除节点时保持更新。 （如果您没有编写树，您也可以通过将树实现包装在您自己的包装对象中来完成此操作，该对象执行相同的操作。）
Walking the tree will always be O(log n). Did you write the tree implementation yourself? You can always simply stash a reference to the current lowest value element alongside your data structure and keep it updated when adding/removing nodes. (If you didn't write the tree, you could also do this by wrapping the tree implementation in your own wrapper object that does the same thing.)
TAOCP 中有一个实现，它使用非完整节点中的“备用”指针来按顺序沿着节点完成一个双链表（我现在不记得细节，但我想象你必须为每个方向都有一个“has_child”标志才能使其工作）。
有了它和一个起始指针，您就可以在 O(1) 时间内获得起始元素。
该解决方案并不比缓存最小值更快或更有效。
There is a implementation in the TAOCP that uses the "spare" pointers in non-full nodes to complete a double linked list along the nodes in order (I don't recall the detail right now, but I image you have to have a "has_child" flag for each direction to make it work).
With that and a start pointer, you could have the starting element in O(1) time.
This solution is not faster or more efficient that caching the minimum.
如果最小元素是指具有最小值的元素，那么您可以使用
TreeSet带有自定义Comparator它将项目排序为正确的顺序以存储各个元素，然后只需调用SortedSet#first()或#last()尽可能高效地获取最大/最小值。请注意，与其他集合/列表相比，向 TreeSet 插入新项目稍慢，但如果您没有大量不断变化的元素，那么这应该不是问题。
If by minimum element you mean element with the smallest value then you could use
TreeSetwith a customComparatorwhich sorts the items into correct order to store individual elements and then just callSortedSet#first()or#last()to get the biggest/smallest values as efficiently as possible.Note that inserting new items to
TreeSetis slightly slow compared to other Sets/Lists but if you don't have a huge amount of elements which constantly change then it shouldn't be a problem.如果您可以使用一点内存，听起来组合集合可能适合您。
例如，您正在寻找的内容听起来很像链接列表。您始终可以找到最小元素，但插入或查找任意节点可能需要更长的时间，因为您必须执行查找 O(n)
如果将链表和树结合起来，您可能会两全其美。要查找项目以进行获取/插入/删除操作，您可以使用树来查找元素。元素的“持有者”节点必须有办法从树跨越到链表以进行删除操作。此外，链表必须是双向链表。
所以我认为获得最小的项目将是 O(1)，任何任意查找/删除将是 O(logN)——我认为即使是插入也会是 O(logN)，因为你可以找到将它放在树中的位置，查看上一个元素并从那里交叉到链表节点，然后添加“下一个”。
嗯，这开始看起来像一个非常有用的数据结构，可能有点浪费内存，但我不认为任何操作会比 O(logN) 更糟糕，除非你必须重新平衡树。
If you can use a little memory it sounds like a combined collection might work for you.
For instance, what you are looking for sounds a lot like a linked list. You can always get to the minimum element but an insert or lookup of an arbitrary node might take longer because you have to do a lookup O(n)
If you combine a linked list and a tree you might get the best of both worlds. To look up an item for get/insert/delete operations you would use the tree to find the element. The element's "holder" node would have to have ways to cross over from the tree to the linked list for delete operations. Also the linked list would have to be a doubly linked list.
So I think getting the smallest item would be O(1), any arbitrary lookup/delete would be O(logN)--I think even an insert would be O(logN) because you could find where to put it in the tree, look at the previous element and cross over to your linked list node from there, then add "next".
Hmm, this is starting to seem like a really useful data structure, perhaps a little wasteful in memory, but I don't think any operation would be worse than O(logN) unless you have to re balance the tree.
如果您将二叉树升级/“复杂化”为线程二叉树，那么您可以获得O (1) 第一个和最后一个元素。
您基本上保留对当前第一个和最后一个节点的引用。
插入后，如果第一个的前一个非空，则首先更新。最后同样如此。
每当删除时，首先检查要删除的节点是第一个还是最后一个。并适当地更新先存储的、最后存储的。
If you upgrade / "upcomplex" your binary tree to a threaded binary tree, then you can get O(1) first and last elements.
You basically keep a reference to the current first and last nodes.
Immediately after an insert, if first's previous is non-null, then update first. Similarly for last.
Whenever you remove, you first check whether the node being removed is the first or last. And update that stored first, last appropriately.