AVL Trees e il mondo REALE

14

a scuola ci viene insegnato come possiamo bilanciare un albero AVL al momento dell'inserimento o dell'eliminazione.

In che modo questo tipo di conoscenza sarà davvero utile nel mondo reale? Qualcuno può dare un esempio su quando questo tipo di conoscenza sarebbe effettivamente utile?

Da quello che ho visto, sul posto di lavoro questi dettagli non si vedono quasi mai ...

Riesco a vedere in che modo la conoscenza dettagliata degli algoritmi e di alcune strutture dati può essere importante ma non i dettagli come le rotazioni dell'albero AVL (e concetti dettagliati simili).

grazie!

    
posta rrazd 02.07.2011 - 20:00
fonte

3 risposte

13

Lo studio degli alberi AVL può essere utile per i seguenti motivi:

  • È un'ottima pratica per ragionare sui dati astratti. Non devi pensare a un albero in particolare, devi considerare ogni possibilità. Praticare con questo tipo di ragionamento può aiutare anche con casi più semplici.

  • È un'ottima pratica per comprendere predicati e contratti. Garantire che un albero sia bilanciato e che gli strumenti utilizzati per dimostrare l'equilibrio preservato di ciascuna operazione possano, ad es., Essere applicati a problemi di sicurezza e al codice parallelo.

  • Ti consente di scrivere le tue varianti o persino di creare tipi di strutture dati completamente nuovi.

  • Potrebbe essere necessario implementare un albero AVL per una nuova libreria o piattaforma.

Puoi discutere i particolari vantaggi dell'apprendimento di ogni tipo di algoritmo di ordinamento o di ogni tipo di albero bilanciato. Non ha importanza se quali hai finito per apprendere, ma dovresti assicurarti di avere una copertura completa degli argomenti più importanti.

Se vuoi vedere quanto sono importanti gli algoritmi di conoscenza nel mondo reale, leggi " Come uccidere una grande idea! ", un articolo in Inc sulla caduta di Friendster e su come la minima applicazione dei principi fondamentali per migliorare l'efficienza avrebbe potuto aiutarli.

    
risposta data 02.07.2011 - 20:45
fonte
5

Oltre ai punti Macneils ...

Gli alberi red-black sono forse più direttamente utili perché ci sono operazioni efficienti utili che non sono ampiamente supportate in implementazioni di librerie standard come il C ++ std::map (almeno AFAIK). Gli alberi rosso-neri possono supportare "dividere" (tagliare un albero in due, uno contenente chiavi meno di una chiave specificata e uno contenente le chiavi più grande) e "unirsi" (il contrario, combinando un albero di grandi chiavi con un albero di piccole dimensioni chiavi) possono essere eseguite in O (log n) time, ma se sono supportate nelle librerie contenitore standard, sembra essere una cosa ben nascosta.

Tuttavia, le strutture dati "aumentanti" sono comuni. Un semplice esempio è l'aggiunta di informazioni sulla dimensione della sottostruttura ai nodi in quasi tutte le strutture di dati dell'albero per supportare O (log n) subscripting. Esempi più sofisticati includono gli alberi intervallati.

Una volta che hai avuto l'idea di aumentare le strutture dei dati, ci sono molte varianti che possono essere utili per particolari applicazioni - e molto poche sono disponibili preconfezionate come una libreria. Le strutture di dati della libreria standard esistenti (ad es. std::map ) non possono essere aggiunte per copiare il codice sorgente e modificarlo direttamente: non è possibile aumentarle utilizzando i parametri del modello.

Ovviamente per sviluppare una struttura dati ampliata, è necessario comprendere la sottostante struttura dati non aumentata.

Gli alberi AVL possono essere più veloci degli alberi red-black se fai molte più ricerche di inserti / eliminazioni (e se non hai bisogno di quelle operazioni di split / join), quindi a seconda dell'applicazione, potrebbero essere molto buona base per l'aumento.

    
risposta data 03.07.2011 - 02:20
fonte
5

No

Non è davvero utile nel mondo reale ...

Ad eccezione di ti fanno pensare .

Il mondo reale presenta problemi molto più difficili , molti dei quali non hanno già soluzioni note.

    
risposta data 03.07.2011 - 05:30
fonte

Leggi altre domande sui tag