数组到二进制搜索树快速

本文介绍了数组到二进制搜索树快速的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

给定一个整数数组，有没有一种方法可以将其快速转换为二进制搜索树（不平衡）？我尝试为每个元素一个一个地插入它，但这意味着我必须从每个插入开始一遍。它工作得很好，但我认为最坏的情况是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).

算法如下：

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

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

Sort the array of integers. This takes O(nlog(n)) time

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.

编辑：

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

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

请参阅自平衡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).