java - 如何评估通过链表或数组列表实现的二叉树的性能？

Question

这属于 https://stackoverflow.com/help/on-topic 中的“软件算法”

这是来自面试题http://www.glassdoor.com/Interview/Yelp-Software-Engineering-Intern-Interview-Questions-EI_IE43314.0,4_KO5,32_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 n)，因为您每次都要砍掉一半的树。

您将如何立即分析基于这两种实现的性能？

Answer 1

我不确定我是否理解正确，但我是这么想的。 基本上，您可以将树中的节点存储为数组/列表的元素。

对于数组，想想这样的事情:

public class Node {
    public int data;
    public int left;
    public int right;
    ...
}

您的树将是 Node 数组(Node[] 树)，这样根就是第一个元素 tree[0]。 每个元素都将其左右子元素引用为数组中的索引。 例如，tree[ tree[0].left ] 将是根的左 child 。 -1 的 left 值可能表示该节点没有左 child ； 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))，它的右 child 是第四个元素(节点 (9,-1,-1))。

插入/删除函数的性能可能会因您的具体实现而异。 类似的想法也适用于链表(但请记住，它们没有随机访问:找到第 i 元素需要逐个元素地遍历列表)。

希望这对您有所帮助。