Insert sorted array into binary search tree

问题:

I want to implement an algorithm that inserts sorted arrays into binary search trees but I don't want ending up with a tree that only grows to one side.

Do you have any ideas?

Thanks.

回答1:

This should give you a balanced tree (in O(n)):

1. Construct a node for the middle element in the array and return it
   (this will be the root in the base case).
2. Repeat from 1. on the left half of the array, assigning the return value to the left child of the root.
3. Repeat from 1. on the right half of the array, assigning the return value to the right child of the root.

Java-like code:

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);
}

Code derived from here.

回答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;
    }
}

回答3:

Insert them in pseudo-random order, like here:

#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;
}