Abstract Date Types: Trees and Graphs
This is my third article on abstract data types, so reading my first two articles might help with understanding this one. However, those two are by no means a requisite. The past two articles have been about linear data types, and this one will be on the non-linear data types, so while there is some overlap, they are different enough that you could simply start here. Although there is part of the overlap that should be discussed again…
Nodes
Nodes in non-linear data types are mostly the same as their linear counterparts. With linear nodes, they have two parts: a value and a pointer. The value is there to hold the payload of the node and could be any of information. A number, a word, a whole object, doesn’t matter, the value is just tracking that part of the node. The second part is the pointer, and it gives instructions/directions about where the next node is. For the word “cat”, you could have a three nodes, one for each letter, the “c” node may point to the “a” node, which points to the “t” node. This makes a chain of nodes, which in this case is forming a string of the word “cat”.
This is a linear data type because, ignoring the beginning and ending of the chain, each node has one node pointing at it, and each node is pointing to one other node. You can iterate forwards through the chain, and if you’re tracking your progress, you should be able to iterate backwards through the chain as well.
The first thing that sets non-linear data types apart from linear date types is that their nodes can point to multiple other nodes. Or that is, they will have a value and multiple pointers. This can result in two different non-linear data types, graphs and trees. And although trees are technically a type of graph, their terminology and rules make them easier to provide examples and talk about first.
Trees
Trees start with a singular root node. This root will point to multiple other nodes, and no node will ever point at the root. This makes a kind of parent and child hierarchy, where a parent can have multiple children, and children always have only one parent. Those child nodes could then have children of their own, and those grand-children could have children, and so on. Each node that has a child is called a branch node, and nodes that have no children are leaf nodes.
What’s important and unique about trees is that there is only one way to reach each node. To reach 11, you have to go through 1, 2, and 5. To reach 7, you have to go through 1 and 3. Having only one parent per node and only one path per node means trees are good at detailing things like hierarchies or a series of dependent events and decisions. A every day example might be something like a family tree or a simple flowchart, and a technical example would be something like a Document Object Model (DOM).
If nodes have two parents, and there is more than one way to reach each node, your tree is either messed up, or you have made a…
Graph
Graph nodes (or vertices) can point to multiple nodes (the pointers being called edges), and be pointed at by multiple nodes, so the distinction of parent and child doesn’t work as well here. This also means there are no inherent root, branch, or leaf nodes. The result is that all nodes are basically equal, and this makes them good for working with problems with relationships, networks, and mapping.
I’m not sure there’s too much more I can say about graphs at this level. After this point, you need to start consulting discrete mathematics, graph theory, and topology. Again, I’d recommend Crash Courses video on all the data structures and types. And if you were having any problems with “The Seven Bridges of Königsberg” image I posted at the top of the article, I’d also recommend watching the Numberphile video below for the solution. Or rather, negative solution. For now, I think this serves as an introduction to trees and graphs, and what problems they are best suited to solve.
References:
