Chèn mảng đã sắp xếp vào cây tìm kiếm nhị phân

Question

Tôi muốn triển khai thuật toán chèn các mảng được sắp xếp vào các cây tìm kiếm nhị phân nhưng tôi không muốn kết thúc bằng một cây chỉ phát triển sang một bên.

Bạn có ý tưởng nào không?

Cảm ơn.

Answer 1

này sẽ cho bạn một cây cân bằng (trong thời gian O (n)):

1. Xây dựng một nút cho các phần tử trung trong mảng và trả lại
   (đây sẽ là gốc trong trường hợp cơ bản).
2. Lặp lại từ 1. ở nửa bên trái của mảng, gán giá trị trả lại cho con trái của gốc.
3. Lặp lại từ 1. ở nửa bên phải của mảng, gán giá trị trả về cho đúng con của thư mục gốc.

mã Java như:

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

Mã bắt nguồn từ here.

Answer 2

Chèn chúng theo thứ tự giả ngẫu nhiên, giống như ở đây:

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

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