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

Question

这属于 "a software algorithm" 来自 https://whosebug.com/help/on-topic

这是来自面试问题 http://www.glassdoor.com/Interview/Yelp-Software-Engineering-Intern-Interview-Questions-EI_IE43314.0,4_KO5,32_IP2.htm,

特别是"performance of binary tree if implemented thru array or linkedlist"

你会如何通过数组或链表实现二叉树？

我被教导这样做的方式是通过链接节点类型的结构，它有两个指针，左指针和右指针，即（来自 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

不知道我理解的对不对，但是我是这么想的。基本上，您可以将树中的节点存储为 array/list.

的元素

对于数组，可以这样想：

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

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

insertion/deletion 函数的性能可能因您的具体实施而异。类似的想法适用于链表（但请记住，它们没有随机访问：找到第 i 个元素需要逐个元素遍历列表）。

希望这对您有所帮助。

Answer 2

在这样分析算法时，您想看看它是什么类型的二叉树（平衡与不平衡），加上关于 sapce/time 复杂度的三个因素：

插入
删除
搜索

比较二叉树的链表与数组实现，我们看到以下内容：

链接列表的插入和删除比在数组中完成时要便宜得多（想想为完成这两个操作而必须进行的数组元素移位。
链表提供灵活的大小，而数组则没有；当数据不适合初始数组大小时，您将不得不处理数组扩展。
数组提供随机访问，而链表不提供；例如在处理完整或完整二叉树的数组实现时，我们可以轻松计算树中任何节点的索引。

话虽如此，对于Binary Search Trees, linked lists are better implementations simply because in a binary search tree, access follows the rules of a binary search tree (root's value is greater than left child and less than right child). Therefore, for insertion/deletion and search, average complexity should be O(log n), provided the tree is balanced的具体实现。如果二叉搜索树不平衡，那么所有操作的复杂度都会变成 O(n) - 这是最坏的情况。

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

How to evaluate the performance of a binary tree implemented via a linked list or an array list?

java

algorithm

tree

binary-tree

linked-list