如何评估通过链表或数组列表实现的二叉树的性能？
如何评估通过链表或数组列表实现的二叉树的性能？
提问于 2015-02-06 06:57:26
这属于https://stackoverflow.com/help/on-topic的“软件算法”。
这是IP2.htm的采访问题，
特别是“如果通过数组或链接列表实现二叉树的性能”
如何通过数组或链接列表实现二叉树？
我被教导这样做的方法是有一个具有两个指针(左和右)的结构的链接节点类型，即(来自https://courses.cs.washington.edu/courses/cse143/12wi/lectures/02-22/programs/IntTreeNode.java)。
public class IntTreeNode {
public int data;
public IntTreeNode left;
public IntTreeNode right;
public IntTreeNode(int data) {
this(data, null, null);
}
public IntTreeNode(int data, IntTreeNode left, IntTreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
}然后在实际的二叉树中
public class IntTree {
IntTreeNode overallRoot;
public IntTree() {
overallRoot = null;
}
....
}如果您只是使用数组或链接列表(一个指针)，您将如何处理？
但无论如何，这应该是一个快速开火的问题。即使没有实现树，也不应该实现树，您将如何分析树的性能？性能不取决于树的状态，比如它是否是BST？就像BST一样，查找将是O(log )，因为每次都要砍掉一半的树。
您将如何根据这两个实现来分析性能？
Stack Overflow用户
发布于 2015-02-06 07:45:03
在分析算法本身时，您想看看它是哪种类型的二叉树(平衡的还是不平衡的)，再加上有关皂甙/时间复杂性的三个因素：
- 插入
- 删除
- 搜索
将链接列表与二叉树的数组实现进行比较，我们可以看到以下内容：
- 链接列表、插入和删除比在数组中执行时要便宜得多(考虑到执行这两个操作所必须做的数组元素移位)。
- 链接列表提供灵活的大小，而数组不提供；当数据不适合初始数组大小时，必须处理数组扩展。
- 数组提供随机访问，而链接列表不提供；例如，在处理完整或完整二叉树的数组实现时，我们可以轻松地计算树中任何节点的索引。
尽管如此，对于二元搜索树的特定实现，链接列表是更好的实现，因为在二进制搜索树中，access遵循二进制搜索树的规则(根的值大于左子，小于右子)。因此，对于插入/删除和搜索，平均复杂度应该是O(log n)，只要树是平衡。如果二进制搜索树不平衡，那么所有操作的复杂度都会变成O(n) --这是最坏的情况。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/28360210
复制相关文章
相似问题
腾讯云开发者
