Operating Systems Course – Useful Pre-requisites

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.

I would define them as the interface they provide, including complexity of the operations.

One could after all implement a linked list with an array and vice versa (and recursivly), but it would be impossible to keep the complexity.

Update: To clarify: A stack is defined as a datastructure with constant-time add to top, and constant-time remove at top. It doesn't say how we implement it. One could implement it using an array, or a linked list, but also a double linked list, but that is irrelevant.

The atomic we have on a computer is (binary) memmory, and the most basic form of memmory is an array, thus one can create every kind of datastructure using an array.

One could imagine we had another atomic (maybe a qubit). Then a stack would still be a stack, but maybe we couldn't implement it with that atomic.