二进制搜索树不能做什么？
这是我不太了解的。当我在堆上阅读文献时，总是说堆的最大优势在于，您拥有立即可用的顶部（Max If Max Heap）元素。但是，您难道不仅可以使用BST并存储指向相同节点（最下最下）并使用插入/删除更新指针的指针？
如果我没记错的话，随着BST的实现，我将描述您会变得
================================================
| Insert | Remove Max
================================================
Special BST | O(log(n)) | O(1)
================================================
Max Heap | O(log(n)) | O(log(n))
================================================
更好。
伪代码：
Insert:
Same as regular BST insert, but can keep track of whether
item inserted is max because traversal will be entirely
in the right direction.
Delete
Set parent of max equal to null. Done.
我在这里缺少什么？
This is something I do not quite understand. When I read literature on heaps, it always says that the big advantage of a heap is that you have the top (max if max heap) element immediately available. But couldn't you just use a BST and store a pointer to the same node (bottom-rightmost) and update the pointer with insertions/deletions?
If I'm not mistaken, with the BST implementation I'm describing you would have
================================================
| Insert | Remove Max
================================================
Special BST | O(log(n)) | O(1)
================================================
Max Heap | O(log(n)) | O(log(n))
================================================
making it better.
Pseudo-code:
Insert:
Same as regular BST insert, but can keep track of whether
item inserted is max because traversal will be entirely
in the right direction.
Delete
Set parent of max equal to null. Done.
What am I missing here?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
是的，你可以。
不，由于以下原因，最大删除不会（始终）为o（始终）：
删除最大值后，您还需要更新指针以引用底部的最右节点。例如，在去除最大之前，请拿这棵树：
您必须找到具有值14的节点，因此要更新最大指针。
可以通过保持树的平衡来使上述操作为o（1），可以根据AVL规则说。在那种情况下，上一个最大节点的左孩子不会有一个正确的孩子，而新的最大节点将是其左子节点，或者如果没有一个父母，则是其父母。但是，由于某些删除会使树不平衡，因此需要进行重新平衡的操作。这可能涉及几次旋转。例如，以这个平衡的BST：
删除节点15后，很容易确定13是下一个最大值，但是扎根于13的子树不会平衡。平衡它之后，整个树是不平衡的，需要另一个旋转。旋转数可能为o（logn）。
最后，您 can 使用带有最大指针的平衡BST，但最大节点的提取仍然是O（logn）操作，使其与二进制堆中的同一操作相同的时间复杂性。
考虑到二进制堆不使用任何指针，因此比自动平衡的BST所拥有的“管理”开销要少得多，因此，插入/删除操作的实际空间消耗和运行时将是一个因素，而它们的渐近复杂性是相同。
此外，在O（n）时间中，可以从非分组的阵列中构建二进制堆，同时构建BST成本o（nlogn）。
但是，当您需要能够按照其正确顺序遍历值或找到值或找到值的前身/后继线时，BST是要走的方法。对于此类操作，二进制堆的时间复杂性较差。
Yes, you could.
No, Max removal wouldn't (always) be O(1), for the following reasons:
After you have removed the Max, you need to also update the pointer to reference the bottom right-most node. For example, take this tree, before the Max is removed:
You'll have to find the node with value 14, so to update the Max pointer.
The above operation can be made to be O(1), by keeping the tree balanced, let's say according to the AVL rules. In that case the left child of the previous Max node would not have a right child, and the new Max node would be either its left child, or if it didn't have one, its parent. But as some deletions will make the tree unbalanced, they would need to be followed by a rebalancing operation. And that may involve several rotations. For instance, take this balanced BST:
After removal of node 15, it is easy to determine that 13 is the next Max, but the subtree rooted at 13 would not be balanced. After balancing it, the tree as a whole is unbalanced, and another rotation would be needed. The number of rotations could be O(logn).
Concluding, you can use a balanced BST with a Max pointer, but extraction of the Max node is still a O(logn) operation, giving it the same time complexity as the same operation in a binary heap.
Considering that a binary heap uses no pointers, and thus has much less "administrative" overhead than a self-balancing BST, the actual space consumption and runtime of the insert/delete operations will be better by a factor -- while their asymptotic complexity is the same.
Also, a binary heap can be built from a non-sorted array in O(n) time, while building a BST costs O(nlogn).
However, a BST is the way to go when you need to be able to traverse the values in their proper order, or find a value, or find a value's predecessor/successor. A binary heap has worse time complexities for such operations.
最大堆和平衡的BST（例如AVL树）在O（log n）时间内执行这些操作。但是，由于指针，BST持续不断地增加了更多的空间，并且它们的代码更加复杂。
Both max heaps and balanced BST’S (eg AVL trees) perform these operations in O(log n) time. But BST’s take a constant factor more space due to pointers and their code is more complicated.
由于您是在谈论BST而不是平衡的BST，因此请考虑以下偏斜的BST：
您可以将指针引用最大值（
n-th）元素，但是如果您要插入一个值<代码>＆lt; n ，在最坏情况下，它需要o（n）插入时间。另外，要查看堆中的最大值，您可以简单地进行heap [0]（假设使用数组实现堆）以获取o（1）<的最大元素/代码>堆的时间。Since you're talking about BST's and not Balanced BST's, consider the following skewed BST:
You can hold a pointer reference to the max (
n-th) element, but if you're inserting a value< n, it will requireO(n)insertion time in the worst case. Also, to see the max value in the heap, you could simply doheap[0](assuming the heap is implemented using an array) to get the max element inO(1)time for heap as well.