数组到二叉搜索树快速

Question

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

回到我的问题，有没有比我所说的算法更快的方法？

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

Answer 1

Given an array of integers, is there a way to convert it into Binary Search Tree (unbalanced) quickly?

当然可以。对数组进行O(n logn)排序，select数组的中间元素为根，将左边中间元素之前的所有元素插入根，右边插入中间元素之后的元素(O( n）时间）。总复杂度为 O(n logn)。例如，如果您有数组：

3, 5, 2, 1, 4

您将其排序为 1, 2, 3, 4, 5。中间元素是 3 所以你创建树

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

问题是树的高度是n/2，这意味着搜索操作是O(n)，这很慢。为了获得更好的性能，您应该改用自平衡二叉搜索树，例如 red-black tree or AVL tree

Answer 2

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

算法如下：

Sort 整数数组。这需要 O(nlog(n)) 时间
在 O(n) 时间内从排序数组构造 BST。就一直把数组的中间元素作为根，对数组的左+右半边递归执行这个操作。

编辑：

首先，您不能比 O(nlog(n)) 做得更好，因为那样您基本上可以在复杂度上比 O(nlogn) 更好地对未排序的数组进行排序（使用比较）。这是 impossible.
如果一开始不需要排序，可以对数组的每个元素使用二叉树插入算法构造二叉树。

参考 Self-balancing 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;

}

在这之后只需要遍历 pri

Answer 4

好吧，我不确定这个解决方案有多优化，但这是我写的

算法

对输入数组进行排序
创建一个采用排序数组的递归函数
递归函数内部如果arr的长度为1或者是空数组，returnarr
否则计算中点(parseInt(arr.length/2))
return 一个数组 [midpoint, recuriveFunc(arr[leftToMidPoint]),recuriveFunc(arr[rightToMidpoint])]

Javascript

中的代码实现

const arr =  [1,2,3,4,5,6,7]


const recursiveSetValues = (arr) => {
  if (arr.length < 2) return arr
  const midPoint = parseInt(arr.length/2)
  return [arr[midPoint], ...recursiveSetValues(arr.slice(0, midPoint)), ...recursiveSetValues(arr.slice(midPoint+1, arr.length))]
}


const sortArray = arr.sort((a,b) => a-b)
console.log(recursiveSetValues(sortArray))

数组到二叉搜索树快速

Array to Binary Search Trees Quick

algorithm

binary-search-tree

算法

Javascript