堆与二叉树 - 如何实现?
在实现堆结构时,我们可以将数据存储在数组中,使得位置 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)
如果所有子节点的位置都是这样静态预先计算的,那么该数组本质上代表一个完全完整、完全平衡的二叉树。
并非“现实生活”中的所有二叉树都是完全满的和完美平衡的。如果您碰巧有一些特别长的分支,则必须使整个数组更大以容纳最底层的所有节点。
如果数组绑定二叉树大部分为空,则大部分数组空间被浪费。
- 数组的“底部”,那么就会浪费大量空间。
如果树(或只是一个分支)需要比数组允许的大小“更深”,则需要“增长”数组,这通常通过复制到更大的数组来实现。这是一项耗时的操作。
所以:使用指针可以让我们动态、灵活地增长结构。在数组中表示一棵树是一项很好的学术练习,对于小型和简单的情况效果很好,但通常不能满足“真实”计算的需求。
要将元素插入到堆中,您可以将其放置在任何位置并与其父元素交换,直到堆约束再次有效。 Swap-with-parent 是一种保持堆的二叉树结构完整的操作。这意味着大小为 N 的堆将表示为 N 单元数组,并且您可以在对数时间内添加新元素。
二叉搜索树可以使用与堆相同的表示结构(子级 2n 和 2n+1)表示为大小为 N 的数组,但以这种方式插入元素要困难得多,因为与堆约束不同,二分搜索树树约束要求执行旋转以检索平衡树。因此,要么你设法以高于对数的成本将 N 节点树保留在 N 单元数组中,要么通过将树保留在更大的数组中来浪费空间(如果我没记错的话,红背树可以浪费多达 50% 的阵列)。
因此,只有当内部数据恒定时,数组中的二叉搜索树才有意义。如果是,那么您不需要堆结构(子级 2n 和 2n+1):您可以对数组进行排序并使用 二分搜索。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
就个人而言
因为使用指针更容易
增加数据结构的大小
动态
我发现维护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...