Forest data structure finds great use in data science. Before knowing about the forest data structure, let us learn the basics of graph and tree data structures.
Graph
A graph is a collection of nodes that are connected to other nodes in the data structure. You can consider Facebook as a real-life graph example and everyone’s connection with many others as a relationship (friendship relation in this case). It can have any number of cycles in the data structure.
Tree
A tree is an example of a nonlinear data structure which stores the data in a nonlinear manner. You can also say that tree is a graph that doesn’t contain any cycle.
Linear Data Structure
Linear data structure stores data in a linear manner, for example, array, linked list etc.
Non-linear Data Structure
In a tree, the data is stored in non-linear way e.g. Tree has a starting point called root node and subsequent nodes that are connected to the root node or other nodes. There is no cycle in data structure. For example, if A is connected to B and B is connected to C so C can’t be connected to A. Here is a pictorial representation of a tree.
There is a specialized tree is called binary tree in which each node has maximum two nodes.
Forest
Forest is a collection of disjoint trees. In other words, we can also say that forest is a collection of an acyclic graph which is not connected. Here is a pictorial representation of a forest.
Here you can see that there is no connected tree in the example. A single tree and empty graph is also an example of forest data structure.
Uses of Forest Data Structure
Social Networking Websites
Social networking sites (Such as Facebook, LinkedIn, Twitter etc) are using tree and graphdata structure for their data representation. When you work on adding two people as a friend, you are creating a forest of two people.
Big Data and Web Scrapers
Websites are organized in the form of a tree data structure where the main page forms the root node and the subsequent hyperlinks from that page represents the rest of the tree. When Web scrapers scrap multiple such websites, they represent it in the form of a forest of several trees.
Operating System Storage
If you are working on a Windows-based operating system, you would be able to see various disks in the system such as C drive (C:\), D drive (D:\), etc. You can think of each drive as different trees and the collection of all storage as the forest.
Now by the above example, you can see the importance of forest in computer science and programming. It is always advisable to have a basic knowledge about these topics so that you can easily relate many technical papers and articles.
Comments are closed.