BST từ hai mảng chưa phân loại

Question

Câu hỏi này được hỏi trong một cuộc phỏng vấn: Với hai mảng chưa phân loại, hãy kiểm tra xem nó có tạo cùng bst hay không. ví dụ: 2, 1, 4, 0 và 2, 1, 0, 4 sẽ tạo thành cùng một BST.

 2 
    /\ 
    1 4 
/
0 

hãy đề xuất một số bản ngã tốt.

Answer 1

• Lấy phần tử đầu tiên - Đây sẽ là thư mục gốc (trong trường hợp ở trên nó là 2)
• Tất cả các yếu tố đó là ít hơn so với các phần tử gốc sẽ xuất hiện theo thứ tự ở cả hai mảng
  • Trong ví dụ trên, 0 và 1 là các phần tử nhỏ hơn các phần tử gốc.
  • Trong mảng đầu tiên, thứ tự là 1, 0
  • Thứ tự tương tự được duy trì trong mảng thứ hai. Vì vậy, cả hai hình thành cấu trúc tương tự

• Tất cả các yếu tố đó là lớn hơn sau đó các phần tử gốc sẽ xuất hiện theo thứ tự ở cả hai mảng

  • Trong ví dụ trên 4 là yếu tố duy nhất lớn hơn 2. Nó xuất hiện trong cả hai mảng. Và do đó cả hai mảng tạo BST có cấu trúc giống nhau.

• Và tất nhiên điều kiện đầu tiên là cả hai mảng phải chứa cùng một phần tử nhưng theo thứ tự khác nhau.

Do đó, điều này có thể được giải quyết trong thời gian tuyến tính.

Mã giả sẽ là như thế này:

int GetNextIncresingElement(int[] arr, ref int index, int root) 
{ 
    for(int i = index; i< arr.Length; i++) 
    { 
     if(arr[i] > root) 
     { 
      index = i; 
      return arr[i]; 
     } 
    } 
    return -1; 
} 

int GetNextDecreasingElement(int[] arr, ref int index, int root) 
{ 
    for(int i = index; i< arr.Length; i++) 
    { 
     if(arr[i] <= root) 
     { 
      index = i; 
      return arr[i]; 
     } 
    } 
    return -1; 
} 

bool CheckFormsSameBST(int[] arr1, int[] arr2) 
{ 
    int index1 = 1; 
    int index2 = 1; 
    int num1; 
    int num2; 

    int root = arr1[0]; 
    if(root != arr2[0]) 
     return false; 

    while(true) 
    { 
     num1 = GetNextIncresingElement(arr1, ref index1, root); 
     num2 = GetNextIncresingElement(arr2, ref index2, root);  

     if(num1 != num2) 
      return false;  
     else 
     { 
      if(num1 == -1) 
       break; 
     } 

     index1++; 
     index2++; 
    } 

    index1 = 1; 
    index2 = 1; 
    while(true) 
    { 
     num1 = GetNextDecreasingElement(arr1, ref index1, root); 
     num2 = GetNextDecreasingElement(arr2, ref index2, root);   

     if(num1 != num2) 
      return false;  
     else 
     { 
      if(num1 == -1) 
       break; 
     } 

     index1++; 
     index2++; 
    } 

    return true; 
} 

Answer 2

Bạn có thể kiểm tra giải thích chi tiết so sánh hai cây nhị phân (không chỉ BST) tại Determine if two binary trees are equal. Thật dễ dàng để tạo BST từ các mảng và sau đó chạy thuật toán trong các câu hỏi đã đề cập.

Answer 3

IMO, bạn có thể sắp xếp một mảng và thực hiện tìm kiếm nhị phân từ mảng thứ hai tới mảng được sắp xếp, trong khi đó, hãy đảm bảo rằng bạn đang sử dụng mọi phần tử. Nó sẽ làm bạn mất mlogn.

Answer 4

kiểm tra nếu nó sẽ tạo ra các bst giống nhau không?

Có.

bắt đầu lấy phần tử đầu tiên làm gốc và giữ số lớn hơn gốc ở bên phải và nhỏ hơn gốc từ bên trái.

nếu bạn làm theo quy trình trên, bạn sẽ quan sát thấy cả hai cây đều giống nhau.

Answer 5

Tôi đồng ý với ý tưởng Peter và Algorist được mô tả. Nhưng tôi tin rằng các cây con của mỗi nút (được biểu diễn bằng mảng nhỏ hơn nút này và mảng lớn hơn nó) cần phải được kiểm tra trong thời trang này. Ví dụ, 621407 và 621047 mang lại BST giống nhau nhưng 624017 thì không. Hàm có thể được viết đệ quy.

mẫu mã thêm:

bool sameBST(int * t1, int * t2, int startPos, int endPos) { 
    int rootPos1, rootPos2; 
    if (endPos-startPos<0) return true; 
    if (t1[startPos]!=t2[startPos]) return false; 
    rootPos1=partition(t1,startPos,endPos,t1[startPos]); 
    rootPos2=partition(t2,startPos,endPos,t2[startPos]); 
    if (rootPos1!=rootPos2) return false; 
    return sameBST(t1,t2,startPos,rootPos1-1) && sameBST(t1,t2,rootPos1+1,endPos); 
} 

phân vùng chức năng là một trong những cùng bạn sử dụng trong quicksort. Rõ ràng, T (n) = 2T (n/2) + O (n), dẫn đến độ phức tạp thời gian T (n) = O (nlogn). Do đệ quy, mức độ phức tạp không gian là O (logn)

Answer 6

Điểm có thể so sánh các hoán vị của subsegments của một mảng với subsegments tương ứng của mảng khác (nghĩ thứ tự mức độ):

bắt đầu với phần tử đầu tiên trong mảng, đối với i = 0 cho một số n, nhóm các phần tử thành bộ 2^i

2^0 = 1: phần tử đầu tiên là gốc - phải bắt đầu cả hai mảng: [50].

2^1 = 2: bất kỳ hoán vị của 2 yếu tố tiếp theo là tốt:

[25,75] or [75,25] 

2^2 = 4: bất kỳ hoán vị của 4 yếu tố tiếp theo là tốt:

[10, 35, 60, 85] or [60, 35, 10, 85] or ... 

2^3 = 8: bất kỳ hoán vị nào của 8 phần tử tiếp theo là tốt:

[5, 16, 30, 40, …. 

từ 2 đến n cho đến khi mảng trống. các phân đoạn tương ứng phải có cùng số phần tử.

Answer 7

1) Sắp xếp mảng bằng cách sử dụng đếm hoặc phối phân loại.

2) Tạo cây bằng cách sử dụng mảng đã sắp xếp của chúng tôi và cho mảng chưa phân loại (để kiểm tra thứ tự chèn). Nó sẽ bảo tồn cấu trúc của cây.

3) So sánh cả hai cây.

Tất cả có thể được thực hiện trong thời gian tuyến tính - O (n).

Code:

import java.util.Arrays; 
public class BSTFromUnsorted { 

static class Node{ 
    int key; 
    int arrivalTime,min,max,root; 
    Node left; 
    Node right; 
    Node(int k,int at){ 
     key=k;left=null;right=null;arrivalTime=at; 
    } 
} 
public static void printTree(Node n){ 
    if(n==null) return; 
    System.out.println(n.key+" "+ ((n.left!=null)?n.left.key:"-") + " " + ((n.right!=null)?n.right.key:"-")); 
    printTree(n.left); 
    printTree(n.right); 
} 
public static boolean compareTree(Node n1,Node n2){ 
    if(n1==null && n2==null) return true; 
    return (n1!=null && n2!=null && n1.key==n2.key && compareTree(n1.left,n2.left) && compareTree(n1.right,n2.right)) ; 
} 
public static void main(String[] args){ 
    int[] bstInsertOrder1={8, 10, 14, 3, 6, 4, 1, 7, 13}; 
    int[] bstInsertOrder2={8, 3, 6, 1, 4, 7, 10, 14, 13}; 
    Node n1 = buildBST(bstInsertOrder1); 
    printTree(n1); 
    System.out.println(); 
    Node n2 = buildBST(bstInsertOrder2); 
    printTree(n2); 
    System.out.println("\nBoth are " + (compareTree(n1,n2)?"same":"different")); 
} 
public static Node buildBST(int[] insertOrder){ 
    int length = insertOrder.length; 
    Node[] sortedOrder = new Node[length]; 
    for(int i=0;i<length;i++){ 
     sortedOrder[i] = new Node(insertOrder[i],i); 
    } 
    Radix.radixsort(sortedOrder,length); 
    int[] sortedIndex = new int[length]; 
    for(int i=0;i<length;i++){ 
     sortedOrder[i].max=sortedOrder[i].min=sortedOrder[i].root=i; 
     sortedIndex[sortedOrder[i].arrivalTime]=i; 
    } 
    for (int i=length-1;i>0;i--){ 
     int j = sortedIndex[i]; 
     int min=sortedOrder[j].min-1,max=sortedOrder[j].max+1; 
     Node n=null,n1; 
     if(min>=0){ 
      n = sortedOrder[sortedOrder[min].root]; 
     } 
     if(max<length){ 
      n1=sortedOrder[sortedOrder[max].root]; 
      if(n==null){ 
       n=n1; 
      } 
      else{ 
       n=(n.arrivalTime>n1.arrivalTime)?n:n1; 
      } 
     } 
     n1=sortedOrder[j]; 
     if(n.key<n1.key){ 
      n.right=n1; 
      n.max=n1.max; 
      sortedOrder[n.max].root=sortedOrder[n.min].root; 
     } 
     else{ 
      n.left=n1; 
      n.min=n1.min; 
      sortedOrder[n.min].root=sortedOrder[n.max].root; 
     } 
    } 
    return sortedOrder[sortedIndex[0]]; 
} 
static class Radix { 
    static int getMax(Node[] arr, int n) { 
     int mx = arr[0].key; 
     for (int i = 1; i < n; i++) 
      if (arr[i].key > mx) 
       mx = arr[i].key; 
     return mx; 
    } 
    static void countSort(Node[] arr, int n, int exp) { 
     Node output[] = new Node[n]; // output array 
     int i; 
     int count[] = new int[10]; 
     Arrays.fill(count, 0); 
     for (i = 0; i < n; i++) 
      count[(arr[i].key/exp) % 10]++; 
     for (i = 1; i < 10; i++) 
      count[i] += count[i - 1]; 
     for (i = n - 1; i >= 0; i--) { 
      output[count[(arr[i].key/exp) % 10] - 1] = arr[i]; 
      count[(arr[i].key/exp) % 10]--; 
     } 
     for (i = 0; i < n; i++) 
      arr[i] = output[i]; 
    } 
    static void radixsort(Node[] arr, int n) { 
     int m = getMax(arr, n); 
     for (int exp = 1; m/exp > 0; exp *= 10) 
      countSort(arr, n, exp); 
    } 
} 

}