堆与二叉树 - 如何实现？
在实现堆结构时，我们可以将数据存储在数组中，使得位置 i 处的节点的子节点位于位置 2i 和 2i+1 处。
我的问题是，为什么我们不使用数组来表示二叉搜索树，而是处理指针等？
谢谢
when implementing a heap structure, we can store the data in an array such that the children of the node at position i are at position 2i and 2i+1.
my question is, why dont we use an array to represent binary search trees and instead we deal with pointers etc.?
thanks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
就个人而言
因为使用指针更容易
增加数据结构的大小
动态
我发现维护bin更容易
树比堆
在树中平衡、删除、插入元素的算法只会改变指针，而不是像在向量中那样物理移动。
在树中平衡、删除
等等...
Personally
Because using pointers its easier to
grow the data structure size
dynamically
I find It's easier to maintain bin
tree than a heap
The algorithms to balance, remove, insert elements in the tree will alter only pointers and not move then physically as in a vector.
and so on...
如果所有子节点的位置都是这样静态预先计算的，那么该数组本质上代表一个完全完整、完全平衡的二叉树。
并非“现实生活”中的所有二叉树都是完全满的和完美平衡的。如果您碰巧有一些特别长的分支，则必须使整个数组更大以容纳最底层的所有节点。
如果数组绑定二叉树大部分为空，则大部分数组空间被浪费。
如果树（或只是一个分支）需要比数组允许的大小“更深”，则需要“增长”数组，这通常通过复制到更大的数组来实现。这是一项耗时的操作。
所以：使用指针可以让我们动态、灵活地增长结构。在数组中表示一棵树是一项很好的学术练习，对于小型和简单的情况效果很好，但通常不能满足“真实”计算的需求。
If the position of all children is statically precomputed like that, then the array essentially represents a completely full, completely balanced binary tree.
Not all binary trees in "real life" are completely full and perfectly balanced. If you should happen to have a few especially long branches, you'd have to make your whole array a lot larger to accomodate all nodes at the bottom-most level.
If an array-bound binary tree is mostly empty, most of the array space is wasted.
If only some of the tree's branches are deep enough to reach to the "bottom" of the array, there's also a lot of space being wasted.
If the tree (or just one branch) needs to grow "deeper" than the size of the array will allow, this would require "growing" the array, which is usually implemented as copying to a larger array. This is a time-expensive operation.
So: Using pointers allows us to grow the structure dynamically and flexibly. Representing a tree in an array is a nice academic exercise and works well for small and simple cases but often does not fulfill the demands of "real" computing.
主要是因为递归树允许非常简单的代码。如果将树展平为数组，代码就会变得非常复杂，因为您必须做大量的簿记工作，而递归算法会为您做这些工作。
此外，高度为 N 的树可以有 N 到
2^(N+1)-1节点之间的任何节点（。只有实际节点才需要内存。如果使用数组，则必须始终分配内存除非您使用稀疏数组（这会使代码变得更加复杂），否则尽管在内存中保留高度为 100 的稀疏树很容易，但找到一个高度为 100 的稀疏树将是有问题的。可以分配 20282409603651670423947251286008 字节 RAM 的计算机。Mainly because the recursive tree allows for very simple code. If you flatten the tree into an array, the code becomes really complex because you have to do a lot of bookkeeping which the recursive algorithm does for you.
Also, a tree of height N can have anything between N and
2^(N+1)-1nodes (. Only the actual nodes will need memory. If you use an array, you must always allocate space for all nodes (even the empty ones) unless you use a sparse array (which would make the code even more complex). So while it is easy to keep a sparse tree of height 100 in memory, it would be problematic to find a computer which can allocate 20282409603651670423947251286008 bytes of RAM.要将元素插入到堆中，您可以将其放置在任何位置并与其父元素交换，直到堆约束再次有效。 Swap-with-parent 是一种保持堆的二叉树结构完整的操作。这意味着大小为 N 的堆将表示为 N 单元数组，并且您可以在对数时间内添加新元素。
二叉搜索树可以使用与堆相同的表示结构（子级 2n 和 2n+1）表示为大小为 N 的数组，但以这种方式插入元素要困难得多，因为与堆约束不同，二分搜索树树约束要求执行旋转以检索平衡树。因此，要么你设法以高于对数的成本将 N 节点树保留在 N 单元数组中，要么通过将树保留在更大的数组中来浪费空间（如果我没记错的话，红背树可以浪费多达 50% 的阵列）。
因此，只有当内部数据恒定时，数组中的二叉搜索树才有意义。如果是，那么您不需要堆结构（子级 2n 和 2n+1）：您可以对数组进行排序并使用 二分搜索。
To insert an element into a heap, you can place it anywhere and swap it with its parent until the heap constraint is valid again. Swap-with-parent is an operation that keeps the binary tree structure of the heap intact. This means a heap of size N will be represented as an N-cell array, and you can add a new element in logarithmic time.
A binary search tree can be represented as an array of size N using the same representation structure as a heap (children 2n and 2n+1), but inserting an element this way is a lot harder, because unlike the heap constraint, the binary search tree constraint requires rotations to be performed to retrieve a balanced tree. So, either you do manage to keep an N-node tree in an N-cell array at a cost higher than logarithmic, or you waste space by keeping the tree in a larger array (if my memory serves, a red-back tree could waste as much as 50% of your array).
So, a binary search tree in an array is only interesting if the data inside is constant. And if it is, then you don't need the heap structure (children 2n and 2n+1) : you can just sort your array and use binary search.
据我所知，我们可以使用Array来表示二叉搜索树。
但使用指针更加灵活。
As far as I know, we can use Array to represent binary search trees.
But it is more flexible to use pointers.
如果您需要在图算法中用作优先级队列的堆，则基于数组的实现非常有用。在这种情况下，堆中的元素是不变的，您弹出最顶部的元素并插入新元素。删除顶部元素（或最小元素）需要进行一些重新平衡才能再次成为堆，这样可以使数组合理平衡。
对此的参考是 Goldberg 和 Tarjan 的关于高效计算有向图中最优网络流的算法 iirc。
The array based implementation is useful if you need a heap that is used as a priority queue in graph algorithms. In that case, the elements in the heap are constant, you pop the top most element and insert new elements. Removing the top element (or min-element) requires some re-balancing to become a heap again, which can be done such that the array is reasonably balanced.
A reference for this is the algorithm by Goldberg and Tarjan about efficiently computing optimal network flow in directed graphs, iirc.
与 BST 不同，堆数据结构是完全二叉树。因此，使用数组对于 BST 没有多大用处。
Heap data structure is a complete binary tree unlike BST. Hence, using arrays is not of much use for BST.