Trova nodi scambiati in un BST

Question

Sto provando a scrivere un programma in grado di rilevare e stampare due nodi in BST che sono stati scambiati.

In un albero di tre livelli, ho raggiunto vicino alla soluzione utilizzando questo approccio.

If (!AllSubTreeAreValid()) 
{ 
//Nodes swapped on same side of main root node 
} 
else 
{ 
    int max = getMax(root->left); 
    int min = getMin(root->right); 
    if(max > root->data || min < root->data) 
    { 
    //Nodes swapped on different sides of main root node 
    //Print max and min values 

    } 
else 
{ 
//No node swappped 
} 
} 

//Helper functions 
int GetMaxEle(TreeNode* tree) 
{ 
    while(tree->right!=NULL) 
    { 
     tree=tree->right; 
    } 
    return tree->info; 
} 

int GetMinEle(TreeNode* tree) 
{ 
    while(tree->left!=NULL) 
    { 
     tree=tree->left; 
    } 
    return tree->info; 
} 

ma l'approccio di cui sopra non è riuscito quando ho provato a verificare con albero di quattro livelli.

   20 

     15   30 

    10 17  25  33 

9 16 12 18 22 26 31 34 

Essendo nella sottostruttura destra del nodo 15, 12 è ancora maggiore (violazione).

Essendo nel sottostruttura di sinistra del nodo 15, 16 è ancora maggiore (violazione).

Quindi, 16, 12 sono gli elementi scambiati nella BST precedente. Come li trovo attraverso il programma?

Answer 1

Un modo di pensare a questo problema è quello di utilizzare il fatto che un ordine simmetrico a piedi l'albero produrrà tutti gli elementi in modo ordinato. Se è possibile rilevare le deviazioni dall'ordine ordinato durante questa passeggiata, è possibile provare a individuare i due elementi che si trovano nel posto sbagliato.

Vediamo come eseguire questa operazione per un array ordinato semplice, quindi utilizzeremo il nostro algoritmo per creare qualcosa che funzioni sugli alberi. Intuitivamente, se iniziamo con una matrice ordinata e poi scambiamo due elementi (non uguali!), Ci ritroveremo con un certo numero di elementi nell'array fuori posto. Ad esempio, dato l'array

1 2 3 4 5 

Se invertire 2 e 4, si finisce con questa matrice:

1 4 3 2 5 

come potremmo rilevare che il 2 e 4 sono stati scambiati qui? Bene, poiché 4 è il maggiore dei due elementi ed è stato scambiato verso il basso, dovrebbe essere maggiore di entrambi gli elementi attorno ad esso. Allo stesso modo, poiché 2 è stato scambiato, dovrebbe essere più piccolo di entrambi gli elementi attorno ad esso. Da questo, potremmo concludere che 2 e 4 sono stati scambiati.

Tuttavia, questo non funziona sempre correttamente. Ad esempio, supponiamo che ci scambiamo 1 e 4:

4 2 3 1 5 

Qui, sia 2 e 1 sono più piccoli dei loro elementi vicini, ed entrambi 4 e 3 sono più grandi di loro.Da ciò possiamo dire che due di questi quattro sono stati scambiati in qualche modo, ma non è chiaro quali dovremmo scambiare. Tuttavia, se prendiamo il più grande e il più piccolo di questi valori (1 e 4, rispettivamente), finiamo per ottenere la coppia che è stata scambiata.

Più in generale, di trovare gli elementi che sono stati scambiati nella sequenza, si desidera trovare

• Il più grande massimo locale nella matrice.
• Il minimo locale minimo dell'array.

Questi due elementi sono fuori posto e devono essere scambiati.

Ora, pensiamo a come applicarlo agli alberi. Dal momento che una camminata interna dell'albero produrrà la sequenza ordinata con i due elementi fuori ordine, un'opzione sarebbe quella di camminare sull'albero, registrando la sequenza in ordine di elementi che abbiamo trovato, quindi utilizzando l'algoritmo di cui sopra. Ad esempio, si consideri il tuo BST originale:

   20 
     /  \ 
     15    30 
    / \  / \ 
    10 17  25  33 
/| /\ /\ | \ 
9 16 12 18 22 26 31 34 

Se linearizzare questo in un array, otteniamo

9 10 16 15 12 17 18 20 22 25 26 30 31 33 34 

Si noti che il 16 è maggiore rispetto ai suoi elementi circostanti e che il 12 è inferiore alla sua. Questo ci dice immediatamente che 12 e 16 sono stati scambiati.

un semplice algoritmo per risolvere questo problema, dunque, sarebbe quella di fare un ordine simmetrico a piedi l'albero di linearizzare in una sequenza come un vector o deque, quindi eseguire la scansione quella sequenza per trovare il più grande massimo locale e il più piccolo minimo locale. Questo sarebbe eseguito in tempo O (n), usando lo spazio O (n). Un algoritmo più complesso ma più efficiente in termini di spazio sarebbe tenere traccia di tre nodi alla volta, il nodo corrente, il suo predecessore e il suo successore, il che riduce l'utilizzo della memoria a O (1).

Spero che questo aiuti!

Answer 2

penso che la getMin et getMax funziona dormivamo con le ipotesi che l'albero è un BST, così

T getMax(tree) { 
    return tree -> right == null 
    ? tree -> value 
    : getMax(tree -> right); 
} 

(o il codice equivalente con un anello). In tal caso, il codice esamina al massimo tre valori nella struttura. Anche se getMax e getMin hanno attraversato l'intero albero per ottenere il massimo/minuto effettivo, baseresti comunque il test solo su due confronti. Se si desidera verificare che l'albero soddisfi la proprietà BST, è ovvio che è necessario esaminare tutti i valori. È abbastanza per confrontare ogni nodo con il suo genitore.

void CheckIsBst(Tree *tree) { 
    if (tree -> left != null) { 
    if (tree -> left -> value > tree -> value) { 
     // print violation 
    } 
    CheckIsBst(tree -> left); 
    } 
    // same with -> right, reversing <to> in the test 
} 

Edit: ciò che era sbagliato, vedi commento. Credo che questo sia ok.

void checkIsBst(Tree *Tree, Tree *lowerBound, Tree *upperBound) { 
    if(lowerBound!= null && lowerBound -> value > tree -> Value) { 
    //violation 
    } 
    // same for upper bound, check with < 
    if (tree -> left != null) { 
    if (tree -> left -> value > tree -> value) { 
     // print violation 
    } 
    CheckIsBst(tree -> left, lowerBound, tree); 
    } 
    // same for right, reversing comparison 
    // setting lowerBound to tree instead of upperBound 
} 

Chiamata dalla radice con limiti nulli

Answer 3

l'attraversamento dell'albero effettuato da templatetypedef funziona se si è sicuri che esiste solo uno scambio. In caso contrario, vi suggerisco una soluzione basata sul codice iniziale:

int GetMax(TreeNode* tree) { 
    int max_right, max_left, ret; 

    ret = tree->data; 
    if (tree->left != NULL) { 
     max_left = GetMax(tree->left); 
     if (max_left > ret) 
      ret = max_left; 
    } 
    if (tree->right != NULL) { 
     max_right = GetMax(tree->right); 
     if (max_right > ret) 
      ret = max_right; 
    } 

    return ret; 
} 

int GetMin(TreeNode* tree) { 
    int min_right, min_left, ret; 

    ret = tree->data; 
    if (tree->left != NULL) { 
     min_left = GetMin(tree->left); 
     if (min_left < ret) 
      ret = min_left; 
    } 
    if (tree->right != NULL) { 
     min_right = GetMin(tree->right); 
     if (min_right < ret) 
      ret = min_right; 
    } 

    return ret; 
} 

void print_violations(TreeNode* tree) { 
    if ((tree->left != NULL) && (tree->right != NULL)) { 
     int max_left = GetMax(tree->left); 
     int min_right = GetMin(tree->right); 
     if (max_left > tree->data && min_right < tree->data) { 
      printf("Need to swap %d with %d\n", max_left, min_right); 
     } 
    } 
    if (tree->left != NULL) 
     print_violations(tree->left); 
    if (tree->right != NULL) 
     print_violations(tree->right); 
} 

E 'più lento, ma stampa tutti gli swap si identifica. Può essere modificato per stampare tutte le violazioni (ad esempio se (max_left> tree-> data) violazione di stampa). È possibile migliorare le prestazioni se è possibile aggiungere due campi al TreeNode con il massimo e il minimo precalcolati per quella sottostruttura.