Stavo leggendo il article da Steve Yegge su singleton. In esso menziona il suo insegnante che gli ha detto che gli alberi di AVL erano malvagi. È solo che gli alberi rossi e neri sono una soluzione migliore?Gli alberi AVL sono malvagi?
Male da che punto di vista?
Come sempre: non ci sono strumenti cattivi, solo cattivi artigiani.
Nella memoria, gli alberi AVL presentano un inserimento/rimozione più lento ma un recupero più rapido rispetto al rosso/nero. Principalmente a causa dell'algoritmo di bilanciamento.
Esattamente. Se hai bisogno di una mappa write-once-read-many, gli alberi AVL sono difficili da battere. Secondo me, sono anche più facili da implementare correttamente. – erickson
Una mappa write-once-read-many suona più come una matrice ordinata per me ... Una mappa write-rarely-read-many suona più di un albero AVL. Tuttavia, anche in questi casi, assicurarsi di considerare una matrice ordinata. I costi costanti sono notevolmente inferiori, quindi avrai bisogno di molte voci prima che un albero AVL superi sia l'albero rosso/nero sia un array ordinato. –
Gli alberi AVL sono comunque altamente comprensibili. IME, gli alberi RB non sono compresi dai loro implementatori - stanno semplicemente seguendo le regole; non sono in grado di capire realmente cosa sta succedendo, concettualmente. –
No, gli alberi AVL non sono certamente malvagi sotto nessun punto di vista. Sono una struttura ad albero auto bilanciamento completamente valida. Hanno caratteristiche di performance diverse rispetto agli alberi Red-Black e tipicamente queste differenze portano le persone a scegliere un albero rosso-nero su un albero AVL. Ma questo non li rende cattivi.
Sono sicuro che gli alberi AVL sono malvagi nello stesso modo in cui GOTO è malvagio o BUBBLE SORT è malvagio.
Gli algoritmi non sono malvagi, ma anche gli algoritmi non saltano su e giù per dirti quando sono appropriati.
Goto non è un algoritmo e in realtà non è un confronto legittimo. – Imagist
Il problema con bubble sort è che non ci sono veri trade-off che lo rendono superiore. Non puoi dirlo per gli alberi AVL. –
:: snark :: Bubble sort utilizza pochissimo codice ed è facilmente realizzabile in una macchina di Turing tradizionale. – dmckee
Splay Trees sono molto più freschi. :)
No, non sono cattivi, solo un po 'complicati da programmare.
AVL alberi http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx
collegamento albero Rosso Nero da lì.
Ecco un sacco di informazioni sulle differenze tra Rosso-Nero e AVL-alberi:
http://discuss.fogcreek.com/joelonsoftware/default.asp?cmd=show&ixPost=22948
e una carta confrontando le diverse strutture:
http://www.stanford.edu/~blp/papers/libavl.pdf
In breve - AVL è più veloce da cercare, Red-Black più veloce da inserire.
Il collegamento di fogcreek è cattivo. Il contenuto è fuorviante. Gli alberi AVL non richiedono rotazioni O (log n) per il ribilanciamento. Max 2. – Jesse
Il rappresentante OP di 666 conferma che gli alberi AVL sono malvagi – SwDevMan81
Non credo che potremo fare questa domanda? ;) –