Albero binario ordinato per ordine di livello da un albero binario

Question

Albero binario ordinato per ordine di livello da un albero binario

#1 da (1 voti)
#2 da (0 voti)

1

Supponiamo di avere un albero binario. La struttura del nodo dell'albero è come

struct node 
{
   int val ;
   struct node *left , *right ;
}

Ora dobbiamo ordinare l'albero in ordine di livello. Ad esempio, supponiamo di avere un albero originale come questo

root = 6
root->left = 1 
root->right = 9
root->left->left = 8
root->right->right = 2

Quindi, dopo aver applicato l'ordinamento per livello, il nostro albero sarà

root = 1
root->left = 2
root->right = 6
root->left->left = 8
root->right->right = 9

Un modo per risolvere questo problema è semplicemente prendere tutti i valori in una matrice e applicare uno qualsiasi dell'algoritmo di ordinamento standard e quindi rimettere i valori nella struttura ad albero in modo trasversale. Questa soluzione non è efficiente in termini di spazio e tempo entrambi.

Quale algoritmo posso utilizzare per ridurre le operazioni e l'utilizzo della memoria dal mio piano proposto? Esiste un algoritmo più efficiente per farlo senza l'uso di un array ordinato?

Ordinamento dell'ordine di livello: L'ordinamento a livello di livello significa che se esegui l'attraversamento di un ordine di livello dell'albero, dovresti ottenere una sequenza ordinata non decrescente.

Vincolo:
La forma dell'albero non dovrebbe alterare quella condizione se nell'albero originale lasciato figlio della radice non ha figli giusti (come nel mio esempio) e dopo l'ordinamento, non dovrebbe avere figli giusti.

algorithms sorting binary-tree

posta sdream 12.08.2014 - 19:32

fonte

2 risposte

Leggi altre domande sui tag algorithms sorting binary-tree

Creazione di una ricerca rapida e in tempo reale per gli script televisivi Attività di lunga durata avviata nel sito web

score 1 · Answer 1

Sembra che tu abbia bisogno di un tipo di heap con alcune proprietà modificate. Innanzitutto, usa un min-heap invece di un max-heap: ogni nodo è minore di i valori dei suoi figli e aggiunge un vincolo che un nodo è maggiore di il suo fratelli a sinistra.

Una delle caratteristiche chiare di un heap è che si tratta di un albero binario bilanciato: la profondità di tutti i nodi foglia varia al massimo di 1. Inoltre, i nodi foglia sono popolati da sinistra a destra. Anche se questa non è la stessa rappresentazione che hai, rende tutto molto più semplice.

Se prendi un albero con queste proprietà ed esegui un traversal di ordine di livello, puoi facilmente convertirlo in e da un array:

root = 6
root->left = 1 
root->right = 9
root->left->left = 8
root->left->right = 2

L'attraversamento dell'ordine di livello fornisce quanto segue: 6, 1, 9, 8, 2.

Nota come ogni livello prende 2 ^ elementi in quell'array, dove n è la profondità dei nodi a quel livello. Il nodo radice ha una profondità 0, quindi richiede 2 ^ 0 = 1 elemento. Il livello successivo ha la profondità 1, quindi richiede 2 ^ 1 = 2 elementi. Questa proprietà significa che esiste una correlazione diretta tra un elemento specifico nell'albero e la sua posizione dell'array.

Ora esegui un ordinamento efficiente su quell'array e ottieni: 1, 2, 6, 8, 9.

Esegui il contrario della prima trasformazione. L'elemento 0 è la radice, gli elementi 1 e 2 sono il livello successivo, gli elementi 3, 4 (e 5, 6 se presenti) sono il livello successivo.

root = 1
root->left = 2
root->right = 6
root->left->left = 8
root->left->right = 9

Se è necessario mantenere il fatto che le foglie non sono popolate da sinistra a destra, o l'albero non è bilanciato, è possibile aggiungere spazi vuoti dicendo che alcuni nodi sono null e modificare un algoritmo di ordinamento per lasciare valori nulli sul posto. Non ideale, ma può consentire di sfruttare le proprietà di un heap per farlo. L'ordinamento di ordine di livello deve essere fatto praticamente usando un heap, per quanto ne sappia io (realizzato tramite BS e MS in informatica senza aver mai sentito o visto un altro modo per farlo, e tu conosci al mondo reale non interessa)

score 0 · Answer 2

Supponiamo che tu abbia un iteratore forward-only che visiterà l'albero in ordine di livello, questo può essere realizzato usando un ordinamento in stile inserimento, due iteratori e una posizione di archiviazione temporanea.

For each node (using Iterator1)
  Put the value into temp
  For each node up to Iterator1 (using Iterator2)
    Skip until temp >= value
    Insert temp and move values down one position

Molto efficiente nello spazio, non tanto in velocità ma facile da codificare.

Se c'è abbastanza spazio per copiare tutti i valori, allora c'è un algoritmo più veloce copiandoli, ordinandoli e copiandoli di nuovo.

A titolo di chiarimento, un "forward only iterator" indica un puntatore o un indice o un altro meccanismo che consente a ciascun nodo di essere visitato in un ordine predefinito, ma non consente l'inversione o l'accesso casuale. Questo è il modo più comune per attraversare gli alberi e probabilmente quello che stai già facendo.

Con due di questi e un singolo temporaneo puoi implementare un ordinamento sul posto. Il primo iteratore (esterno) esegue un singolo passaggio dall'inizio alla fine e ne estrae un valore ogni volta. Il secondo (interno) fa più passaggi dall'inizio all'iteratore esterno, prima di trovare dove posizionare il valore rimosso e quindi rimescolare i valori rimanenti. Questo è un tipo di inserimento (ma abbastanza simile a un tipo di bolla). Probabilmente sono 5-10 righe di codice, a seconda della lingua.