24

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?

Jonas
  • 121,568
  • 97
  • 310
  • 388
Chap
  • 2,776
  • 24
  • 31

6 Answers6

19

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.

Ionuț G. Stan
  • 176,118
  • 18
  • 189
  • 202
Antoine Claval
  • 4,923
  • 7
  • 40
  • 68
  • 4
    Exactly. If you need a write-once–read-many map, AVL trees are hard to beat. In my opinion, they are also easier to implement correctly. – erickson Sep 08 '09 at 15:39
  • 5
    A write-once–read-many map sounds more like a sorted array to me... A write-rarely–read-many map sounds more than an AVL tree. However even in those cases be sure to consider a sorted array. The constant costs are considerably lower, so you will need many entries before an AVL tree outperforms both red/black tree and a sorted array. – B.S. Sep 08 '09 at 16:43
  • 3
    AVL trees are however highly comprehenable. IME, RB trees are not understood by their implementors - they are merely following the rules; they do not genuinely comprehand what is going on, conceptually. –  Oct 12 '09 at 13:28
8

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.

JaredPar
  • 733,204
  • 149
  • 1,241
  • 1,454
4

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.

Dave
  • 1,081
  • 1
  • 9
  • 18
  • 6
    Goto isn't an algorithm and really isn't a legitimate comparison. – Imagist Sep 08 '09 at 15:51
  • 2
    The problem w/ bubble sort is that there are no real trade-offs which make it superior. You can't say that for AVL trees. – T.E.D. Sep 08 '09 at 16:06
  • 5
    ::snark:: Bubble sort uses very little code, and is easily realized in a traditional Turing machine. – dmckee --- ex-moderator kitten Sep 08 '09 at 16:15
  • 2
    There are (rare) cases where bubble sort is the fastest sort. – H H Sep 08 '09 at 16:28
  • 3
    @Henk: I wouldn't even call them that rare. When your input data is going to be mostly sorted, Bubble sort is essentially linear time. – Phil Miller Sep 10 '09 at 19:50
  • @Imagist: Technically, GOTO is an algorithm from the hardware's point of view. However, my point was really more social commentary regarding high school teachers that teach rules of thumb as sacred law. – Dave Sep 10 '09 at 23:07
2

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.

Tobias Langner
  • 10,634
  • 6
  • 46
  • 76
  • The fogcreek link is bad. The content is misleading. AVL trees do not require O(log n) rotations for rebalancing. Max 2. – Jesse Sep 13 '10 at 12:48
1

Splay Trees are much cooler. :)

Macke
  • 24,812
  • 7
  • 82
  • 118
1

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.

Eric D.
  • 11
  • 1