Albero di ricerca binaria perfettamente bilanciato

Question

Ho una domanda teorica su Balanced BST.

Mi piacerebbe costruire Perfect Balanced Tree che ha i nodi 2^k - 1, da un normale unbalanced BST. La soluzione più semplice a cui riesco a pensare è quella di utilizzare uno Array/Linked list ordinato e dividere ricorsivamente l'array in array secondari e creare Perfect Balanced BST da esso.

Tuttavia, in caso di dimensioni Tree estremamente grandi, sarà necessario creare un Array/List nelle stesse dimensioni in modo che questo metodo consumerà una grande quantità di memoria.

Un'altra opzione è utilizzare le funzioni di rotazione AVL, inserire elemento per elemento e bilanciare l'albero con le rotazioni in base al fattore di equilibrio dell'albero: tre altezze dei subalberi sinistro e destro.

Le mie domande sono, ho ragione riguardo alle mie ipotesi? C'è un altro modo per creare un perfetto BST da squilibrato BST?

Answer 1

Non ho ancora trovato una situazione molto buona per aver bisogno di un albero di ricerca perfettamente bilanciato. Se il tuo caso ne ha davvero bisogno, mi piacerebbe saperlo. Di solito è meglio e più veloce avere un albero quasi equilibrato.

Se si dispone di un albero di ricerca di grandi dimensioni, l'eliminazione di tutte le strutture esistenti di solito non è una buona idea. L'uso delle funzioni di rotazione è un buon modo per ottenere un albero più equilibrato preservando la maggior parte della struttura esistente. Ma normalmente si utilizza una struttura dati adeguata per assicurarsi di non avere mai un albero completamente sbilanciato. Cosiddetti alberi autobilanciati.

C'è ad esempio un albero AVL, un albero rosso-nero o uno albero-albero, che usano varianti di rotazione leggermente diverse per mantenere l'albero equilibrato.

Se si dispone di un albero totalmente sbilanciato si potrebbe avere un problema diverso. - Nel tuo caso la rotazione del modo AVL è probabilmente il modo migliore per risolverlo.

Answer 2

AVL e alberi simili non sono perfettamente bilanciati quindi non sono sicuro di come siano utili in questo contesto.

Si può costruire una lista doppiamente concatenata di nodi della struttura, utilizzando left e right puntatori in luogo di forward e backward puntatori. Ordina quell'elenco e costruisci l'albero ricorsivamente dal basso verso l'alto, consumando l'elenco da sinistra a destra.

Costruire un albero di dimensione 1 è banale: basta mordere il nodo più a sinistra della lista.

Ora, se è possibile costruire un albero di dimensioni N, è anche possibile costruire un albero di dimensioni 2N+1: costruire un albero di dimensioni N, poi mordere un singolo nodo, quindi costruire un altro albero di dimensioni N. Il nodo singolo sarà la radice del tuo albero più grande, e i due alberi più piccoli saranno i suoi sottoalberi sinistro e destro. Poiché l'elenco è ordinato, l'albero è automaticamente un albero di ricerca valido.

Questo è facile da modificare per dimensioni diverse da 2^k-1.

Aggiornamento: dal momento che si parte da un albero di ricerca, è possibile costruire un elenco ordinato direttamente da esso in O(N) tempo e O(log N) spazio (forse anche in O(1) spazio con un po 'di ingegno), e costruire l'albero basso verso l'alto anche nello spazio O(N) e nello spazio O(log N) (o O(1)).

Answer 3

Se la memoria costretti, quindi è possibile utilizzare il dividere e unire le operazioni che possono essere fatte su un albero AVL in O (log n), e credo che lo spazio costante.

Se anche tu fossi in grado di mantenere le statistiche d'ordine, allora si può dividere in mediana, rendere il LHS e RHS perfetto e poi unirsi.

La pseudo-codice (per una versione ricorsiva) sarà

Ciò può essere implementato in O (n) e O (log n) spazio, credo.