将有序数组插入二叉搜索树

Question

我希望能实现一种算法，将排序数组插入二叉搜索树中，但我不想最终得到一棵只向一侧生长的树。

你有任何好的想法吗？

谢谢。

- Ege

Answer 1

这应该可以给你一个平衡的树（在O（n）时间内）：

1. 为数组中间元素构造一个节点并返回它
   （这将是基本情况下的根节点）。
2. 在数组的左半部分上重复步骤1，并将返回值分配给根节点的左子节点。
3. 在数组的右半部分上重复步骤1，并将返回值分配给根节点的右子节点。

类似于Java的代码：

TreeNode sortedArrayToBST(int arr[], int start, int end) {
  if (start > end) return null;
  // same as (start+end)/2, avoids overflow.
  int mid = start + (end - start) / 2;
  TreeNode node = new TreeNode(arr[mid]);
  node.left = sortedArrayToBST(arr, start, mid-1);
  node.right = sortedArrayToBST(arr, mid+1, end);
  return node;
}

TreeNode sortedArrayToBST(int arr[]) {
  return sortedArrayToBST(arr, 0, arr.length-1);
}

源自这里的代码。

- Bernhard Barker

---

先生，如果没有平衡二叉搜索树的限制，时间复杂度会是多少？它应该只是 O(n) 吗？ - laura

我的意思是，如果给定排序的输入，可以制作倾斜树。它的时间复杂度会是多少？ - laura

@laura 构建一棵不平衡树也需要 O(n) 的时间。仅仅遍历一次输入数组就需要 O(n) 的时间，因此没有比这更好的方法。 - Bernhard Barker

先生，还有一个请求。您能否为您给出的算法提供递归关系式。我想推导出最坏情况下的时间复杂度 :) - laura

@laura 看起来是 T(n) = 2T(n/2) + 1。 - Bernhard Barker

Answer 2

public class SortedArrayToBST {
    public TreeNode sortedArrayToBST(int[] num) {
        if (num == null) {
            return null;
        }
        return buildBST(num, 0, num.length - 1);
    }

    private TreeNode buildBST(int[] num, int start, int end) {
        if (start > end) {
            return null;
        }
        int mid = start + (end - start) / 2;
        TreeNode root = new TreeNode(num[mid]);
        TreeNode left = buildBST(num, start, mid - 1);
        TreeNode right = buildBST(num, mid + 1, end);
        root.left = left;
        root.right = right;
        return root;
    }
}

- F.Z

Answer 3

将它们以伪随机的顺序插入，就像这样：

#include <stdio.h>

int array[] = {1,2,3,4,5,6,7,8,9,10};

#define COUNT 10
#define STEP 7  /* must be relatively prime wrt COUNT */
#define START 5 /* not important */

int main(void)
{
unsigned idx;

idx=START;
while(1) {
        printf("[%u] = %u\n", idx, array[idx] );
        // do_insert(array[idx] );
        idx = (idx + STEP ) % COUNT;
        if (idx == START) break;
        }
return 0;
}

- wildplasser