data-structurestreemultiway-tree

Practical use of m-way tree

I have started studying data structures again . I found very few practical uses of this. One of those were about file system on disk . Can someone give me more example of practical uses of m-way tree .

Solution

  • M-way trees come up in a lot of arenas. Here's a small sampling:

    1. B-trees: these are search trees like a binary search tree with a huge branching factor. They're designed in such a way that each node can fit just inside of the memory that can be read from a hard disk in one pass. They have all the same asymPtotic guarantees of regular BSTs, but are designed to minimize the number of nodes searched to find a particular element. Consequently, many giant database systems use B-trees or other related structures to store large tables on disks. That way, the number of expensive disk reads is minimized and the overall efficiency is much greater.
    2. Octrees. Octrees and their two-dimensional cousins quadtrees are data structures for storing points in three dimensional space. They're used extensively in video games for fast collision detection and real-time rendering computations, and we would be much the worse odd if not for them.
    3. Link/cut trees. These specialized trees are used in network flow problems to efficiently compute matchings or find maximum flows much faster than conventional approaches, which has huge applicability in operations research.
    4. Disjoint-set forests. These multiway trees are used in minimum-spanning tree algorithms to compute connectivity blindingly fast, optimizing the runtime to around the theoretical limit.
    5. Tries. These trees are used to encode string data and allow for extremely fast lookup, storage, and maintenance of sets of strings. They're also used in some regular expression marchers.
    6. Van Emde Boas Trees- a lightning fast implementation of priority queues of integers that is backed by a forest of trees with enormous branching factor.
    7. Suffix trees. These jewels of the text processing world allow for fast string searches. They also typically have a branching factor much greater than two.
    8. PQ-trees. These trees for encoding permutations allow for linear-time planarity testing, which has applications in circuit layout and graph drawing.

    Phew! That's a lot of trees. Hope this helps!