2009-09-08 15 views
24

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?

+12

Il rappresentante OP di 666 conferma che gli alberi AVL sono malvagi – SwDevMan81

+1

Non credo che potremo fare questa domanda? ;) –

risposta

19

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.

+4

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

+5

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. –

+3

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. –

8

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.

4

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.

+6

Goto non è un algoritmo e in realtà non è un confronto legittimo. – Imagist

+2

Il problema con bubble sort è che non ci sono veri trade-off che lo rendono superiore. Non puoi dirlo per gli alberi AVL. –

+5

:: snark :: Bubble sort utilizza pochissimo codice ed è facilmente realizzabile in una macchina di Turing tradizionale. – dmckee

2

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.

+0

Il collegamento di fogcreek è cattivo. Il contenuto è fuorviante. Gli alberi AVL non richiedono rotazioni O (log n) per il ribilanciamento. Max 2. – Jesse

Problemi correlati