二叉树，数组与链接 [英] Binary Trees, arrays vs linked

问题描述

通常，可以使用实际的链接节点对象(其中每个节点都有指向其两个子节点的指针)或数组(其中索引k中节点的子节点为2k和2k + 1)来实现基于二叉树的抽象./p>

除了节点的少量额外内存开销外，总体复杂度似乎是相同的.

一个人相对于另一个人有什么具体优势吗?有趣的是，我已经看到二进制堆倾向于使用数组实现，而二进制搜索树倾向于使用链接节点的实现.有什么原因吗?

解决方案

数组不能有效地表示任意形状的二叉树，只能表示 complete 树.完整的二叉树是其中所有级别已满，或者除最深级别以外的所有级别都已满，并且最深级别的所有节点都尽可能位于左侧的一棵二叉树. (您可以想象这些级别从左到右都填充有节点，并且必须在下一个级别开始之前填充一个级别.)

根据定义，堆是完整的二叉树-因此，由于其优越的内存效率，因此使用了数组实现.另一方面，必须支持在任意位置进行插入和删除的二叉搜索树(因此可能不是完整的树)不能使用数组实现.

In general, binary tree based abstractions can be implemented either using actual linked node objects, where each node has pointers to it's two children, or an array, where the children of node in index k are 2k and 2k+1.

Other than the small extra memory overhead of nodes, the complexity in general seems to be identical.

Are there any concrete advantages of one over the other? Anecdotally, I've seen that binary heaps tend to use the array implementation, while binary search trees tend to use linked nodes implementation. Any reason for this?

解决方案

Arrays cannot efficiently represent arbitrarily-shaped binary trees, only complete trees. A complete binary tree is one in which all levels are full, OR all levels except the deepest level are full and the deepest level has all of its nodes as far to the left as possible. (You can imagine that the levels are filled with nodes from left to right, and one level has to be filled before the next level can begin.)

Heaps are, by definition, complete binary trees - hence the array implementation is used due to its superior memory efficiency. On the other hand, binary search trees that must support insertion and removal at arbitrary locations (and thus may not be complete trees) cannot use the array implementation.

这篇关于二叉树，数组与链接的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！