What are applications of alphabetic trees?

In computer science, what is the importance of trees? What are the different applications of trees?

• Answer:

  Niklaus Wirth wrote a very influential book called Algorithms + Data Structures = Programs. According to that book, algorithms and data structures are inherently related. In other words, you can't define a step-by-step procedure (algorithm) without also considering the structure of the information that the procedure uses (data structure). Tree's are simply one tool in our toolbox to get things done. Sometimes a tree works great; other times, we need to use other tools like arrays, hash tables, link lists, etc ... I'll provide a concrete example of how trees are used. Old style hard drives have a seek arm and a rotating disk. In order to find information, the seek arm has to move to a particular distance away from the center of the disk (seek time), and then let the disk rotate until the disk head was exactly on top the particular point it wanted to read or write (rotational latency). This makes doing anything with data on hard drives incredibly slow relative to RAM; so, we often structure information in such a way that we can minimize (a) searching for data, (b) adding data, and (c) deleting data. If there was some way to naturally order the information then we could use a b-tree to achieve those ends. In terms of complexity analysis, we say that those operations all have logarithmic complexity for a b-tree.