AVL Trees and the REAL world

Question

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!

Answer 1

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.

Answer 2

In addition to Macneils points...

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.

Answer 3

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.