Chcę zaimplementować algorytm wstawiający posortowane tablice do drzewa wyszukiwania binarnego, ale nie chcę, aby drzewo było tylko z jednej strony.Włóż posortowaną tablicę do drzewa wyszukiwania binarnego
Czy masz jakieś pomysły?
Dzięki.
Chcę zaimplementować algorytm wstawiający posortowane tablice do drzewa wyszukiwania binarnego, ale nie chcę, aby drzewo było tylko z jednej strony.Włóż posortowaną tablicę do drzewa wyszukiwania binarnego
Czy masz jakieś pomysły?
Dzięki.
To powinno dać zrównoważonego drzewa (w czasie O (n)):
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.
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;
}
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;
}
}
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
to znaczy, że mógłbym zrobić skrzywione drzewo przez dane posortowane dane wejściowe. Jaka byłaby jego złożoność czasu? – laura
@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