BST da due array non ordinati

Question

Questa domanda è stata posta in una delle interviste: Dato due array non ordinati, verificare se creerà lo stesso bst. ad esempio: 2, 1, 4, 0 e 2, 1, 0, 4 formeranno entrambi la stessa BST.

 2 
    /\ 
    1 4 
/
0 

si prega di suggerire qualche buon algo.

Answer 1

• Effettuare il primo elemento - Questa sarà la radice (nel caso precedente è 2)
• Tutti gli elementi che sono minore rispetto all'elemento principale dovrebbe apparire nello stesso ordine in entrambe le matrici
  • Nell'esempio precedente, 0 e 1 sono gli elementi minori degli elementi radice.
  • Nel primo array l'ordine è 1, 0
  • Lo stesso ordine viene mantenuto nel secondo array. Quindi entrambi formano la stessa struttura

• Tutti gli elementi che sono maggiori allora l'elemento principale dovrebbe apparire nello stesso ordine in entrambe le matrici

  • Nell'esempio precedente 4 è l'unico elemento superiore 2. Appare in entrambi gli array. E quindi entrambi gli array creano BST che sono strutturalmente uguali.

• E ovviamente la prima condizione è che entrambi gli array debbano contenere gli stessi elementi ma in ordine diverso.

Quindi questo può essere risolto in tempo lineare.

Pseudocodice sarebbe come questo:

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

È possibile controllare la spiegazione dettagliata confrontando due alberi binari (non solo BST) a Determine if two binary trees are equal. È facile creare BST dagli array e quindi eseguire l'algoritmo nelle domande citate.

Answer 3

IMO, è possibile ordinare un array e fare una ricerca binaria dal secondo array all'array ordinato, nel frattempo, assicurarsi di utilizzare ogni elemento. Ti costerà mlogn.

Answer 4

controllo se si creerà lo stesso BST?

Sì.

inizia a prendere il primo elemento come root e mantiene il numero che è maggiore di root a destra e più piccolo di root a sinistra.

se si segue la procedura sopra, si osserverà che entrambi gli alberi sono identici.

Answer 5

Sono d'accordo con l'idea descritta da Peter e Algorist. Ma credo che anche i sotto-alberi di ciascun nodo (rappresentati dall'array inferiore a questo nodo e l'array più grande di esso) debbano essere esaminati in questo modo. Ad esempio, 621407 e 621047 producono la stessa BST ma 624017 no. La funzione può essere scritta in modo ricorsivo.

codice di esempio ha aggiunto:

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

partizione La funzione è la stessa che si utilizza in quicksort. Apparentemente, T (n) = 2T (n/2) + O (n), che porta alla complessità temporale T (n) = O (nlogn). causa della ricorsione, la complessità spazio è O (log n)

Answer 6

Il punto può essere di confrontare permutazioni delle sottosezioni di uno array con i rispettivi sottosegmenti dell'altra matrice (si pensi ordine livello):

a partire dal primo elemento dell'array, per i = 0 per alcuni n, raggruppare gli elementi in serie di 2^i

2^0 = 1: il primo elemento è la radice - deve avviare entrambi gli array: [50].

2^1 = 2: ogni permutazione dei prossimi 2 elementi è soddisfacente:

[25,75] or [75,25] 

2^2 = 4: ogni permutazione dei prossimi 4 elementi è soddisfacente:

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

2^3 = 8: ogni permutazione dei prossimi 8 elementi è soddisfacente:

[5, 16, 30, 40, …. 

così via per 2^n finché gli array sono vuoti. I rispettivi sottosegmenti devono avere lo stesso numero di elementi.

Answer 7

1) Ordinare la matrice utilizzando il conteggio o l'ordinamento digitale.

2) Costruisci albero utilizzando la nostra matrice ordinata e fornito matrice non ordinata (per verificare l'ordine di inserimento). Conserverà la struttura dell'albero.

3) Confrontare entrambi gli alberi.

Tutto può essere eseguito in tempo lineare - O (n).

Codice:

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

}