Are AVL Trees Evil? [closed]

Question

I was reading the article from Steve Yegge about singletons. In it he mentions his teacher told him AVL Trees were evil. Is it just that red and black trees are a better solution?

Answer 1

Evil from what point of view?

Like always: there are no bad tools, only bad craftsmen.

In my memory, AVL trees have slower insertion/removal but faster retrieval than Red/black. Mainly because of the balance algorithm.

Answer 2

No, AVL trees are certainly not evil in any respect. They are a completely valid self balancing tree structure. They have different performance characteristics than Red-Black trees certainly and typically these differences lead to people choosing a red-black tree over an AVL tree. But this does not make them evil.

Answer 3

I'm sure that AVL trees are evil in the same way that GOTO is evil or BUBBLE SORT is evil.

Algorithms aren't evil, but algorithms also don't jump up and down to tell you when they are appropriate either.

Answer 4

Here's a lot of info about the differences between Red-Black and AVL-Trees:

http://discuss.fogcreek.com/joelonsoftware/default.asp?cmd=show&ixPost=22948

and a paper comparing the different structures:

http://www.stanford.edu/~blp/papers/libavl.pdf

In short - AVL is faster to search, Red-Black faster to insert.

Answer 5

Splay Trees are much cooler. :)

Answer 6

No, they aren't evil, only a bit tricky to program.

AVL Trees http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx

Red Black tree link from there too.