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?
risposta
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
- 1. Differenza tra alberi AVL e alberi splay
- 2. Perché gli alberi binari sono importanti?
- 3. Gli intervalli, i segmenti, gli alberi fenwick sono gli stessi?
- 4. Quali sono i vantaggi degli alberi a T sugli alberi B +/-?
- 5. .NET AVL-Tree incorporato?
- 6. Albero di ricerca binario su albero AVL
- 7. Perché gli alberi di espressione sono più sicuri del riflesso?
- 8. In che modo gli alberi rosso-neri sono isomorfi a 2-3-4 alberi?
- 9. Come funzionano gli alberi Suffix?
- 10. bilanciamento di un albero AVL (C++)
- 11. Prolog, ricostruire gli alberi BST dall'elenco interno
- 12. Algoritmo Divide-And-Conquer per gli alberi
- 13. A cosa servono gli alberi di sintassi astratti?
- 14. Eclipse: come visualizzare gli alberi delle directory come pacchetti
- 15. a movimento laterale, l'iterazione, visitando gli alberi in Clojure
- 16. Lavorare con gli alberi di suffisso in python
- 17. Sto rendendo gli alberi BSP in modo errato?
- 18. stampa di tutti gli alberi binari dall'inorder traversal
- 19. Costruire un gruppo LINQBy query utilizzando gli alberi di espressione
- 20. Come trovare la sottostringa comune più lunga usando gli alberi?
- 21. Come calcolare gli aggregati per i sotto-alberi in Gremlin?
- 22. Comprendere l'algoritmo di Ukkonen per gli alberi di suffisso
- 23. parametro obbligatorio in tutti gli alberi di espressione
- 24. Solo relayout bambini e non tutti gli alberi
- 25. Creazione di distinzione utilizzando gli alberi di espressione
- 26. Feedback: visualizzazione per gli alberi decisionali Apache Spark
- 27. Le macro non espandono gli alberi di token interpolati?
- 28. Come spostare un sottoalbero tra gli alberi in Haskell?
- 29. Riscrittura alberi
- 30. Backbone.js e gerarchie/alberi
Il rappresentante OP di 666 conferma che gli alberi AVL sono malvagi – SwDevMan81
Non credo che potremo fare questa domanda? ;) –