# AVL Trees and the REAL world

in school we are taught how we can balance an AVL tree upon an insertion or deleting.

How is this type of knowledge actually going to be useful in the real world? Can someone give an example on when this type of knowledge would actually be useful?

From what I have seen, in the workplace such details hardly ever come up...

I can see how detailed knowledge about algorithms and some data structures can be important but not such details as AVL tree rotations (and similar detailed concepts).

thanks!

• It's helpful in interviews, if that counts as the real world. Jul 2, 2011 at 18:26
• This is the same arguement that some folks make about learning trigonometry in school "Sheesh! When am I ever going to use that in real life?", and the answer is "it thought you how to analyse and solve an entire class of problem". That and some day you want to cut down a tree and your partner asks "Are you sure that's not going to hit the house?" Trig to the rescue! Aug 17, 2012 at 7:16

The study of AVL trees can be helpful for the following reasons:

• It's great practice for reasoning about abstract data. You don't have to think about one particular tree, you have to consider every possibility. Practice with this kind of reasoning can help with simpler cases too.

• It's great practice for understanding predicates and contracts. Ensuring that a tree is balanced, and the tools you use to prove each operation preserved balance, can, e.g., be applied to security concerns and to parallel code.

• It empowers you to write your own variants, or to even create wholly new types of data structures.

• You just may well have to implement an AVL tree for a new library or platform.

You can debate the particular merits of learning each kind of sorting algorithm or each kind of balanced tree. It doesn't really matter which ones you end up learning, but you should be sure to get full coverage of the most important topics.

If you want to see how important knowing algorithms is in the real world, read "How to Kill a Great Idea!", an article in Inc about Friendster's downfall, and how the slightest application of fundamental principles to improve efficiency could have helped them.

• Interesting article, but I don't see how AVL trees would have helped friendster. Mar 4, 2016 at 23:44
• I would have liked to see an example, like B+-Trees are used for database indexing. Mar 20, 2016 at 22:49

Red-black trees are maybe more directly useful because there are useful efficient operations that aren't widely supported in standard library implementations such as the C++ `std::map` (at least AFAIK). Red-black trees can support "split" (cutting a tree into two, one containing keys less than a specified key, and one containing keys greater) and "join" (the reverse, combining a tree of big keys with a tree of small keys) can both be done in O(log n) time, but if these are supported in standard container libraries, it seems to be a well-hidden thing.

However, "augmenting" data structures is common. A simple example is adding size-of-subtree information to nodes in almost any tree data structure to support O(log n) subscripting. More sophisticated examples include interval trees.

Once you get the idea of augmenting data structures, there's a lot of variations that can be useful for particular applications - and very few are available pre-packaged as a library. Existing standard-library data structures (e.g. such as `std::map`) cannot be augmented short of copying the source code and modifying it directly - you can't augment them using template parameters.

Of course to develop an augmented data structure, you need to understand the underlying non-augmented data structure.

AVL trees can be faster than red-black trees if you do a lot more searches than inserts/deletes (and provided you don't need those split/join operations), so depending on the application, they may be a very good base for augmenting.

• +1 for augmenting data structure, though it is quite a rare thing to do. Most programmers do not have to strive for performance (else we would all be using C++/C/Fortran/Assembly). Jul 3, 2011 at 19:45
• @Matthieu - I believe it's common, but only in certain kinds of development environments. That's not a contradiction, honest, because... errm, well...
– user8709
Jul 3, 2011 at 20:47
• I fully agree! :D Jul 4, 2011 at 6:14

# No

It's really not useful in the real world...

Except to make you think.

The real world has much more difficult problems, many of which do not already have well-known solutions.