数组到二进制搜索树快速

Question

给定一个整数数组，有没有办法将其快速转换为二进制搜索树（不平衡）？我尝试为每个元素一个一个地插入它，但这意味着我必须从每个插入开始一遍。它可以完美工作，但我认为最坏的情况是O（N ^ 2）不平衡，例如，数组已排序。考虑到较大的N，我认为这将需要一些时间。

回到我的问题，有没有一种方法可以比我说的算法更快呢？

例如，给定数组[4,5,2,3,1]，有没有快速的方法来创建它？

    4  
   /  \  
  2    5  
 / \  
1   3

Answer 1

给定一个整数数组，有没有办法快速将其转换为二叉搜索树（不平衡）？

当然。以 O(n logn) 的方式对数组进行排序，选择数组的中间元素作为根，并将左侧中间元素之前的所有元素插入到根中，将中间元素之后的元素插入右侧（O(n) 时间） 。总复杂度为O(n logn)。例如，如果您有数组：

3, 5, 2, 1, 4

你把它排序为1, 2, 3, 4, 5. 中间的元素是 3，因此您创建了树

      3
     / \
    2   4
   /     \
  1       5

您可以有两个指向中间元素的指针，然后开始将第一个指针向左移动，另一个向右移动，然后将指针指向的元素分别插入到左子树和右子树中。

问题是树的高度是n/2多少意味着搜索操作是O(n)慢的。为了获得更好的性能，您应该使用自平衡二叉搜索树，例如红黑树或AVL树

Answer 2

是的，有一种简单的方法可以从 O(nlogn) 的整数数组构造平衡的二叉搜索树。

算法如下：

1. 对整数数组进行排序。这需要 O(nlog(n)) 时间
2. 在 O(n) 时间内从排序数组构造一个 BST。只需继续将数组的中间元素作为根，并在数组的左+右半部分递归执行此操作。

编辑：

1. 首先，你不能比 O(nlog(n)) 做得更好，因为那样你基本上可以比 O(nlogn) 更好地对未排序的数组进行排序（使用比较）。这是不可能的。
2. 如果您最初不必进行排序，则可以通过对数组的每个元素使用二叉树插入算法来构造二叉树。

请参阅自平衡 BST 的任何标准实现。在扫描数组时，在第 i 次迭代中，您有 arr[1...i] 的 BST。现在，您将 arr[i+1] 添加到 BST（使用插入算法）。

Answer 3

已经有了很好的解释。下面是从给定数组构造 BST 的代码。

public static void main(String args[])  
{       
    Node root=null;
    int arr[]=new int[]{99,35,19,0,11,40,5};
    int length=arr.length;
    Arrays.sort(arr); 
    root=constructBST(arr,0,length-1,root);
}
public static Node constructBST(int[]arr,int start,int end,Node root)
{
    if(start>end)
        return null;
    int mid=(start+end)/2;

    if(root==null)
        root=new Node(arr[mid]);

    root.left=constructBST(arr,start,mid-1, root.left);
    root.right=constructBST(arr,mid+1,end, root.right);

    return root;

}

在这之后只是做 inorder traverse to pri