2013-10-16 24 views

Odpowiedz

11

To powinno dać zrównoważonego drzewa (w czasie O (n)):

  1. zbudować węzeł dla elementu środkowego w tablicy i zwróć go
    (będzie to root w przypadku podstawowym).
  2. Powtórz od 1. w lewej połowie tablicy, przypisując wartość zwracaną do lewego dziecka katalogu głównego.
  3. Powtórz od 1. w prawej połowie tablicy, przypisując wartość zwracaną prawemu potomkowi użytkownika root.

Java podobny kod:

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

Kod pochodzi z here.

+0

Panie, jaka byłaby złożoność czasu, gdyby nie było restrykcyjności zrównoważonego drzewa wyszukiwania binarnego? Czy powinien to być tylko O ​​(n)? – laura

+0

to znaczy, że mógłbym zrobić skrzywione drzewo przez dane posortowane dane wejściowe. Jaka byłaby jego złożoność czasu? – laura

+1

@laura Potrzeba również O (n) do zbudowania niezrównoważonego drzewa. Po prostu przechodzenie przez tablicę wejściową zajmuje raz O (n), więc nie ma sposobu, aby to zrobić lepiej. – Dukeling

0

Włóż je w pseudo-losowej, jak tutaj:

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