AVL Trees

[DeanMSands3]

For reference: http://en.wikipedia.org/wiki/AVL_tree
I remember having touched these briefly in my CS Fundamentals 3 class, now some 5 years ago. Haven't touched them since.

Does anyone use these on a semi-regular basis and in what context?

[Hiroshe]

The best way to choose structures is to look at how often you'll need to use each operation and the time and space requirements, and base your choice on that. For example, you might choose an AVL over a hash table if you're working with real time applications because the worst case for hash table insertion (given that we don't know the maximum size) can be disastorus. You might choose a skip list instead of an AVL because of the concurrent access properties of a skip list.

But generally, balenced trees are often more usefull in situations where that data needs to be sorted, or more flexible serches must be performed.

For example, if you want to find a range of numbers in a set you might want to use an avl tree. This extends to other kinds of search criteria.

In "popular" practice, more complicated vartiations of balanced tree's are often used for databases (thus AVL is a good place to start if you want to learn the actual strucutres used). Also, AVL's specifically are used by one of Linux's schedulers I beleive.

I don't generally EXPLICITLY use them. However, they may be used by some mechanism I'm using. Sometimes it comes up as a thought experiment though (ie, when compairing various data structures I could be using). I sometimes consider using them if I'm actually implementing something computationally interesting though (which doesn't come up often in practice). For example, real-time operating systems.

[mike_2000_17]

The AVL tree is one of these things that I would qualify as a fundamental data structure and balancing algorithms that are good to know and understand, but the data structure itself has very limited practical purpose. The thing is that if you need a self-balancing binary search tree, you would probably select one of a number of better options, like the red-black tree that is used in most standard library implementations of a basic binary search tree.

There is, however, one practical application of AVL tree that I can easily think of (because I wrote such code). If you want a cache-efficient and memory-efficient data structure for storing a binary search tree, you need to use a contiguous layout (e.g., breadth-first layout, cache-oblivious vEB layout, etc.) which means that balancing algorithms, like that of the red-black tree, that are based on tree rotations cannot be used because there is no way to efficiently perform tree rotations, and if used, it would make things worse. In that case, the balancing algorithms of the AVL tree are pretty much the best thing to do. If Hiroshe is right that AVL tree is used in the Linux scheduler, then it's possibly for these reasons.

Another important role of the AVL tree is that more general search trees, like metric search trees or space partitioning trees, also require balancing algorithms that do not involve the tree rotation tricks, because they make no sense when the sorting is multi-dimensional (as opposed to uni-dimensional, as in basic binary search trees). In those cases, you have to use balancing algorithms that are very similar to those used by AVL trees.