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?
+4
A:
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
2009-09-08 15:35:31
+11
A:
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.
Antoine Claval
2009-09-08 15:36:41
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
2009-09-08 15:39:19
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.
Ben Strasser
2009-09-08 16:43:44
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.
Blank Xavier
2009-10-12 13:28:49
+2
A:
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
2009-09-08 15:39:24
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.
2009-09-08 16:06:46
::snark:: Bubble sort uses very little code, and is easily realized in a traditional Turing machine.
dmckee
2009-09-08 16:15:32
@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.
Novelocrat
2009-09-10 19:50:25
@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
2009-09-10 23:07:21
+1
A:
No, they aren't evil, only a bit tricky to program.
AVL Trees http://www.eternallyconfuzzled.com/tuts/datastructures/jsw%5Ftut%5Favl.aspx
Red Black tree link from there too.
Eric D.
2009-10-19 12:46:57
+2
A:
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
2009-10-19 13:10:26
The fogcreek link is bad. The content is misleading. AVL trees do not require O(log n) rotations for rebalancing. Max 2.
Jesse
2010-09-13 12:48:18