M-shaped trees appear in many arenas. Here is a small sample:
- B-trees: These are search trees, such as a binary search tree with a huge branching coefficient. They are designed in such a way that each node can only be inserted inside the memory, which can be read from the hard drive in one pass. They all have the same asymmetric guarantees for regular BSTs, but they are designed to minimize the number of nodes that were searched to find a specific item. Consequently, many gigantic database systems use B-trees or other related structures to store large tables on disks. Thus, the number of expensive disk reads is minimized, and the overall efficiency is much higher.
- Octrees. Octrees and their two-dimensional cousins are data structures for storing points in three-dimensional space. They are widely used in video games for quick collision detection and real-time calculation of rendering, and we would be much worse if not for them.
- Tie / cut trees. These specialized trees are used in network flow problems to efficiently calculate correspondences or find maximum flows much faster than conventional approaches that have tremendous applicability in operations research.
- Divided forests. These multipath trees are used in algorithms with minimal tree coverage to accurately compute communications, optimizing runtime to a theoretical limit.
- Tries. These trees are used to encode string data and provide extremely fast search, storage and maintenance of string sets. They are also used in some regular expression markers.
- Van Emde Boas Trees is a lightning fast implementation of priority queues of integers that are supported by a forest of trees with a huge branching coefficient.
- Suffix trees. These jewels in the world of word processing allow you to quickly search for strings. They also tend to have a branching factor much larger than two.
- PQ trees. These trees for coding permutations allow a linear check of planarity, which has applications in the diagram and graphic drawing.
Phew! It is a lot of trees. Hope this helps!