数组到二进制搜索树快速 [英] Array to Binary Search Trees Quick

问题描述

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

Given an array of integers, is there a way to convert it into Binary Search Tree (unbalanced) quickly? I have tried inserting it one by one for each element, but this means that I have to traverse from the beginning for each insertion. It works perfectly, but I think the worst case is O(N^2) for being unbalanced, e.g. the array is sorted. Given a large N, I think it is going to take some time.

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

Back to my question, is there a way to do this faster than the algorithm that I stated?

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

For example, given array [4,5,2,3,1], is there a fast way to create this?

    4  
   /  \  
  2    5  
 / \  
1   3

推荐答案

是的，有一种简便的方法可以从O（nlogn）中的整数数组构造平衡的二叉搜索树。

Yes, there is easy way to construct a balanced Binary Search Tree from array of integers in O(nlogn).

算法如下：

1. 排序整数数组。这需要O（nlog（n））时间


2. 从O（n）时间中的排序数组构造BST。只需保持将数组的中间元素作为根，然后在数组的左半部分和右半部分上递归执行此操作即可。

1. Sort the array of integers. This takes O(nlog(n)) time
2. Construct a BST from sorted array in O(n) time. Just keep making the middle element of array as root and perform this operation recursively on left+right half of array.

---

编辑：

1. 首先，您不能比O（ nlog（n）），因为这样一来，您本质上会比O（nlogn）更好地对未排序的数组（使用比较）进行排序（使用比较）。这是不可能。


2. 如果您不这样做，不必先进行排序，您可以通过对数组的每个元素使用二叉树插入算法来构造二叉树。

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

Refer to any standard implementation of Self-balancing BST. While scanning the array, at ith iteration, you have BST for arr[1...i]. Now, you add arr[i+1] to BST (using insertion algorithm).

这篇关于数组到二进制搜索树快速的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！