Menu
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?
401
Disadvantages of AVL Trees In addition, AVL trees have high constant factors for some operations. For example, restructuring is an expensive operation, and an AVL tree may have to re-balance itself log 2 n \log_2 n log2n in the worst case during a removal of a node.
If you need a write-once–read-many map, AVL trees are hard to beat.
Red black is more efficient.
Advantages of AVL TreesThe height of the AVL tree is always balanced. The height never grows beyond log N, where N is the total number of nodes in the tree. It gives better search time complexity when compared to simple Binary Search trees. AVL trees have self-balancing capabilities.
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.
118
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.
21
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
