Tech Off Post

Single Post Permalink

View Thread: AVL tree vs red-black tree
  • User profile image

    I'm going to go out on a limb and say that RB-trees and AVL-trees are both largely redundant in contemporary software engineering.


    They reflected the way computers used to work: when it was just as fast to access any address in memory it made sense to store large amounts of ordered data in a low-arity binary tree. Now that's not the case and the less random the memory access patterns are, the faster you perform.


    On contemporary hardware, for a small number of items use an array. Inserts and deletes mean copying elements if you want to keep it sorted, but the way caches work, this is fast. If you have a large amount of data use a hash table if you don't need to maintain order. If you do need to maintain order, something like a b+tree would be a better choice (yes, even in RAM) than a binary tree.


    Most applications won't need to retain an ordered collection of elements large enough to make a tree useful though, which I assume is why there are no tree-based collections in the .NET framwork. Usually your application, just by virtue of its design domain, would split data in-memory up into multiple levels such that the number of elements in a single collection is low enough that the array-based collection performs well enough.