在实现堆结构时，我们可以将数据存储在一个数组中，使得位置 i 的节点的子节点位于位置 2i 和 2i+1。
我的问题是，为什么我们不使用数组来表示二叉搜索树，而是处理指针等？
谢谢
user246416
问问题
7975 次
7 回答
8
亲自
因为使用指针更容易动态地增加数据结构的大小
我发现维护 bin 树比维护堆更容易
在树中平衡、删除、插入元素的算法将只改变指针，而不像在向量中那样物理移动。
等等...
于 2010-01-08T13:40:02.470 回答
7
如果所有孩子的位置都是这样静态预先计算的，那么这个数组本质上就代表了一个完全完整的、完全平衡的二叉树。
并非“现实生活”中的所有二叉树都是完全完整且完美平衡的。如果您碰巧有一些特别长的分支，则必须使整个数组更大以容纳最底层的所有节点。
如果数组绑定二叉树大部分为空，则大部分数组空间都被浪费了。
如果只有一些树的分支足够深，可以到达数组的“底部”，那么也会浪费很多空间。
如果树（或仅一个分支）需要增长到比数组允许的大小“更深”，这将需要“增长”数组，这通常是通过复制到更大的数组来实现的。这是一个耗时的操作。
所以：使用指针可以让我们动态、灵活地增长结构。在数组中表示一棵树是一项很好的学术练习，适用于小而简单的情况，但通常不能满足“真实”计算的需求。
于 2010-01-08T13:39:21.467 回答
7
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)-1 nodes (. 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.
于 2010-01-08T13:43:33.290 回答
2
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.
于 2010-01-08T13:44:48.833 回答
0
据我所知，我们可以使用 Array 来表示二叉搜索树。但是使用指针更灵活。
于 2010-01-08T13:38:37.090 回答
0
如果您需要在图形算法中用作优先级队列的堆，则基于数组的实现很有用。在这种情况下，堆中的元素是不变的，您弹出最顶部的元素并插入新元素。删除顶部元素（或最小元素）需要重新平衡才能再次成为堆，这可以使数组合理平衡。
对此的参考是 Goldberg 和 Tarjan 的算法，该算法关于有效计算有向图中的最优网络流，iirc。
于 2010-01-08T13:52:35.563 回答
0
与 BST 不同，堆数据结构是完全二叉树。因此，使用数组对 BST 没有多大用处。
于 2020-04-21T10:13:23.397 回答