Come convertire un albero binario in un albero di ricerca binario sul posto, cioè non possiamo usare alcuno spazio aggiuntivo

Question

Come convertire un albero binario in un albero di ricerca binario sul posto, vale a dire, non possiamo usare altro spazio.

Answer 1

Non si dà molto per andare avanti, ma se il requisito è quello che penso sia, si dispone di un albero binario già creato e seduto in memoria, ma non ordinato (nel modo in cui si desidera che sia ordinato, Comunque).

Sto assumendo che i nodi della struttura sembrano

struct tree_node { 
    struct tree_node * left; 
    struct tree_node * right; 
    data_t data; 
}; 

Sono anche supponendo che si può leggere C

Mentre potremmo semplicemente sedersi intorno chiedendosi perché questo albero è stato mai creato, senza dover è stato creato in ordine che non ci fa bene, quindi lo ignorerò e mi occuperò solo di ordinarlo.

Il requisito che nessuno spazio aggiuntivo sia utilizzato è dispari. Temporaneamente ci sarà spazio extra, se solo in pila. Suppongo che significhi chiamare malloc o qualcosa di simile e che l'albero risultante non debba usare più memoria dell'albero originale non ordinato.

La prima e più semplice soluzione è eseguire un attraversamento preordinato dell'albero non selezionato rimuovendo ogni nodo da tale albero e facendo un inserimento ordinato in un nuovo albero. Questo è O (n + n log (n)), che è O (n log (n)).

Se questo non è quello che vogliono e dovrete usare rotazioni e cose ..... è orribile!

Ho pensato che si potesse fare questo facendo una strana versione di un heap, ma ho avuto dei problemi. Un'altra cosa che mi è venuta in mente, che sarebbe terribilmente lenta, farebbe una strana versione di bubble sort sull'albero.

Per questo ogni nodo viene confrontato e, eventualmente, scambiato con ciascuno dei suoi figli diretti (e quindi anche con il suo genitore) ripetutamente finché non si attraversa l'albero e non si trovano gli scambi necessari di .Facendo una sorta di shaker sort (bubble sort che va da sinistra a destra e da destra a sinistra) funzionerebbe meglio, e dopo il passaggio iniziale non avresti bisogno di attraversare i sottoalberi che non sembravano fuori ordine rispetto al suo genitore .

Sono sicuro che questo algorthm è stato pensato da qualcun altro prima di me e ha un nome interessante che non conosco o che è fondamentalmente imperfetto in un modo che non vedo.

Fornire i calcoli di runtime per il secondo suggerimento è piuttosto complicato. All'inizio pensavo che sarebbe semplicemente O (n^2), tipo bolle e agitatori, ma non posso convincermi che l'evitamento trasversale del sottostrato potrebbe non vincere abbastanza da renderlo un po 'migliore di O (n^2). In sostanza, le bolle e gli shaker sort ottengono anche questa ottimizzazione, ma solo alle estremità in cui l'ordinamento totale si verifica in anticipo e si possono abbattere i limiti. Con questa versione ad albero si ottengono opportunità per evitare anche blocchi nel mezzo del set. Bene, come ho detto, probabilmente è fatalmente imperfetto.

Answer 2

Un albero binario in genere è un albero di ricerca binario, nel qual caso non è richiesta alcuna conversione.

Forse è necessario chiarire la struttura di ciò da cui si sta convertendo. Il tuo albero sorgente è sbilanciato? Non è ordinato dalla chiave su cui vuoi cercare? Come sei arrivato all'albero dei sorgenti?

Answer 3

Bene, se questa è una domanda di intervista, la prima cosa che spiffero (con un pensiero effettivo pari a zero) è questa: iterare l'intero binario in modo ricorsivo e trovare l'elemento più piccolo. Toglilo dall'albero binario. Ora, ripeti il ​​processo in cui esegui l'iterazione dell'intero albero e trovi l'elemento più piccolo e aggiungilo come genitore dell'ultimo elemento trovato (con l'elemento precedente che diventa il figlio sinistro del nuovo nodo). Ripeti il ​​numero di volte necessario fino a quando l'albero originale è vuoto. Alla fine, ti rimane il peggiore albero binario ordinato - una lista collegata. Il puntatore punta al nodo radice, che è l'elemento più grande.

Questo è un algoritmo orribile a tutto tondo - O (n^2) tempo di esecuzione con il peggiore output di albero binario possibile, ma è un buon punto di partenza prima di venire con qualcosa di meglio e ha il vantaggio di essere in grado di scrivi il codice in circa 20 righe su una lavagna.

Answer 4

Effettuare l'attraversamento orizzontale dell'albero binario e memorizzare il risultato. ordina il risultato in ordine crescente forma l'albero di ricerca binario prendendo come elemento radice l'elemento intermedio della lista ordinata (questo può essere fatto usando la ricerca binaria). così otteniamo un albero binario di ricerca equilibrato.

Answer 5

Eseguire l'algoritmo seguente per raggiungere la soluzione.

1) trovare il successore in ordine senza utilizzare alcuno spazio.

Node InOrderSuccessor(Node node) 
{ 
    if (node.right() != null) 
    { 
     node = node.right() 
     while (node.left() != null) 
      node = node.left() 
     return node 
    } 
    else 
    { 
     parent = node.getParent(); 
     while (parent != null && parent.right() == node) 
     { 
      node = parent 
      parent = node.getParent() 
     } 
     return parent 
    } 
} 

2) Eseguire l'attraversamento senza utilizzare spazio.

a) Trova il primo nodo di inorder traversal. Dovrebbe lasciare la maggior parte dei figli dell'albero se ha, o la sinistra del primo figlio destro, se ha, o il bambino destro stesso. b) Utilizzare l'algoritmo di cui sopra per scoprire il successore inoder del primo nodo. c) Ripetere il passaggio 2 per tutto il successore restituito.

Utilizzare sopra 2 algoritmi e eseguire l'attraversamento in ordine sull'albero binario senza utilizzare spazio aggiuntivo. Forma l'albero di ricerca binario durante l'attraversamento. Ma la complessità è nella peggiore delle ipotesi O(N2).

Answer 6

mucchio sorta l'albero .. complessità nlogn ..

Answer 7

Do the postorder Traversal e da quella di creare un albero binario di ricerca.

struct Node * newroot = '\0'; 

struct Node* PostOrder(Struct Node* root) 
{ 
     if(root != '\0') 
     { 
      PostOrder(root->left); 
      PostOrder(root->right); 
      insertBST(root, &newroot); 
     } 
} 

insertBST(struct Node* node, struct Node** root) 
{ 
    struct Node * temp, *temp1; 
    if(root == '\0') 
    { 
     *root == node; 
     node->left == '\0'; 
     node->right == '\0'; 
    } 
    else 
    { 
     temp = *root; 
     while(temp != '\0') 
     { 
      temp1= temp; 
      if(temp->data > node->data) 
       temp = temp->left; 
      else 
       temp = temp->right; 
     } 
     if(temp1->data > node->data) 
     { 
      temp1->left = node; 
     } 
     else 
     { 
      temp1->right = node; 
     } 
     node->left = node->right = '\0'; 
    } 
} 

Answer 8

Convertire albero binario a una lista- doppiamente legato può essere fatto inplace in O (n)
Poi sorta utilizzando merge sort, nlogn
convertire l'elenco di nuovo ad un albero - O (n)

soluzione nlogn semplice.

Answer 9

#include <stdio.h> 
#include <stdlib.h> 

typedef int data_t; 

struct tree_node { 
    struct tree_node * left; 
    struct tree_node * right; 
    data_t data; 
}; 

     /* a bonsai-tree for testing */ 
struct tree_node nodes[10] = 
{{ nodes+1, nodes+2, 1} 
,{ nodes+3, nodes+4, 2} 
,{ nodes+5, nodes+6, 3} 
,{ nodes+7, nodes+8, 4} 
,{ nodes+9, NULL, 5} 
,{ NULL, NULL, 6} 
,{ NULL, NULL, 7} 
,{ NULL, NULL, 8} 
,{ NULL, NULL, 9} 
     }; 

struct tree_node * harvest(struct tree_node **hnd) 
{ 
struct tree_node *ret; 

while (ret = *hnd) { 
     if (!ret->left && !ret->right) { 
       *hnd = NULL; 
       return ret; 
       } 
     if (!ret->left) { 
       *hnd = ret->right; 
       ret->right = NULL;; 
       return ret; 
       } 
     if (!ret->right) { 
       *hnd = ret->left; 
       ret->left = NULL;; 
       return ret; 
       } 
     hnd = (rand() &1) ? &ret->left : &ret->right; 
     } 

return NULL; 
} 

void insert(struct tree_node **hnd, struct tree_node *this) 
{ 
struct tree_node *ret; 

while ((ret= *hnd)) { 
     hnd = (this->data < ret->data) ? &ret->left : &ret->right; 
     } 
*hnd = this; 
} 

void show(struct tree_node *ptr, int indent) 
{ 
if (!ptr) { printf("Null\n"); return; } 

printf("Node(%d):\n", ptr->data); 
printf("%*c=", indent, 'L'); show (ptr->left, indent+2); 
printf("%*c=", indent, 'R'); show (ptr->right, indent+2); 
} 

int main(void) 
{ 
struct tree_node *root, *this, *new=NULL; 

for (root = &nodes[0]; this = harvest (&root); ) { 
     insert (&new, this); 
     } 

show (new, 0); 
return 0; 
} 

Answer 10

struct Node 
{ 
    int value; 
    Node* left; 
    Node* right; 
}; 

void swap(int& l, int& r) 
{ 
    int t = l; 
    l = r; 
    r = t; 
} 

void ConvertToBST(Node* n, Node** max) 
{ 
    if (!n) return; 

    // leaf node 
    if (!n->left && !n->right) 
    { 
     *max = n; 
     return; 
    } 

    Node *lmax = NULL, *rmax = NULL; 
    ConvertToBST(n->left, &lmax); 
    ConvertToBST(n->right, &rmax); 

    bool swapped = false; 
    if (lmax && n->value < lmax->value) 
    { 
     swap(n->value, lmax->value); 
     swapped = true; 
    } 

    if (rmax && n->value > rmax->value) 
    { 
     swap(n->value, n->right->value); 
     swapped = true; 
    } 

    *max = n; 
    if (rmax && rmax->value > n->value) *max = rmax; 

    // If either the left subtree or the right subtree has changed, convert the tree to BST again 
    if (swapped) ConvertToBST(n, max); 
}