Lists are great for storing a bunch of items, but what about looking up specific elements? In the previous chapter, a skip list greatly outperformed a regular linked list when simply finding an item. Why? Because it was utilizing an iteration strategy that resembles that of a balanced tree structure: there, the internal order lets the algorithm strategically skip items. However, that's only the beginning. Many libraries, databases, and search engines are built on trees; in fact, whenever a program is compiled, the compiler creates an abstract syntax tree.
Tree-based data structures incorporate all kinds of smart ideas that we will explore in this chapter, so you can look forward to the following:
- Implementing and understanding a binary search tree
- Learning about self-balancing trees
- How prefix or suffix trees work
- What a priority queue uses internally
- Graphs...
