如何评估通过链表或数组列表实现的二叉树的性能？
这属于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 )，因为每次都要砍掉一半的树。
您将如何根据这两个实现来分析性能？
回答 2
Stack Overflow用户
发布于 2015-02-06 07:38:19
我不确定我的理解是否正确，但这正是我所想到的。基本上，您可以将树中的节点存储为数组/列表的元素。
对于数组，可以这样想：
public class Node {
public int data;
public int left;
public int right;
...
}您的树将是Nodes (Node[] tree)的数组，因此根将是第一个元素tree[0]。每个元素都将其左、右子元素作为数组中的索引。例如，tree[ tree[0].left ]将是根的左子。left值-1可以指示节点没有左子节点；与right类似。
例如，考虑以下树：
5
/ \
2 8
\ / \
3 6 9假设您最初在数组中分配了10个元素。因为树中只有不到10个节点，所以其中一些节点将是null。如下所示：(我将每个Node表示为一个(data,left,right)元组)
{ (5,1,2) , (2,-1,4) , (8,5,3) , (9,-1,-1) , (3,-1,-1) , (6,-1,-1) , null , null , null , null }因此，对于节点(8,5,3)，可以看出它的左子元素是第六个元素(节点(6,-1,-1))，它的右子元素是第四个元素(节点(9,-1,-1))。
插入/删除功能的性能可能因您的精确实现而有所不同。对于链接列表也有类似的想法(但请记住，它们没有随机访问权限:查找i-th元素需要逐个元素遍历列表)。
希望这能有所帮助。
Stack Overflow用户
发布于 2015-02-06 07:45:03
在分析算法本身时，您想看看它是哪种类型的二叉树(平衡的还是不平衡的)，再加上有关皂甙/时间复杂性的三个因素：
- 插入
- 删除
- 搜索
将链接列表与二叉树的数组实现进行比较，我们可以看到以下内容：
- 链接列表、插入和删除比在数组中执行时要便宜得多(考虑到执行这两个操作所必须做的数组元素移位)。
- 链接列表提供灵活的大小，而数组不提供；当数据不适合初始数组大小时，必须处理数组扩展。
- 数组提供随机访问，而链接列表不提供；例如，在处理完整或完整二叉树的数组实现时，我们可以轻松地计算树中任何节点的索引。
尽管如此，对于二元搜索树的特定实现，链接列表是更好的实现，因为在二进制搜索树中，access遵循二进制搜索树的规则(根的值大于左子，小于右子)。因此，对于插入/删除和搜索，平均复杂度应该是O(log n)，只要树是平衡。如果二进制搜索树不平衡，那么所有操作的复杂度都会变成O(n) --这是最坏的情况。
https://stackoverflow.com/questions/28360210
复制相似问题
腾讯云开发者
