Before exploring HTML and CSS further, you’re going to need to understand graphs, trees, and hierarchies.
These concepts apply throughout programming and are not limited to just HTML and CSS. But as I was trying to figure out what topic to explain next to you, I realized that you’re going to need to understand these topics in order to master HTML and CSS. You’ll be glad you took the time to understand these when you encounter them again in your code.
All trees are actually graphs. But not all graphs can be called trees. There are four special conditions that a graph must follow in order to be considered a tree:
- There can be no cycles in a tree.
- Every vertex represents a node that is the root of a subtree. .
- Every two nodes in a tree are connected by exactly one path. .
- A tree is fully connected and has exactly one less edge or connection than nodes.
So how do hierarchies fit into all this? A hierarchy is a tree with a couple extra properties:
- The first is inheritance either up or down the hierarchy.
- The second property of hierarchies is that they consider roles.
Make sure to listen to the full episode for more details and examples and subscribe to the podcast so you’ll get future episodes automatically. You can also read the full transcript below.
Transcript
These concepts apply throughout programming and are not limited to just HTML and CSS. But as I was trying to figure out what topic to explain next to you, I realized that you’re going to need to understand these topics in order to master HTML and CSS. You’ll be glad you took the time to understand these when you encounter them again in your code.
Let’s get started. There’s a lot to cover and as I was brainstorming, my notes quickly filled up several pages. This episode will be an introduction focused mainly on comparing graphs with trees, and then with hierarchies. I’ll go into more details in future episodes.
I always like to learn new topics by comparing and contrasting them together and with what I already know. You might also benefit from this. Our brains work by associating things together. We think of something and that brings up other thoughts of things similar in some way. This makes it easier to remember something if there’s many different ways to get to whatever it is you’re trying to remember.
So whenever you want to learn something new, it’s always a good idea to link it into your thoughts in many different ways. Thinking about how something relates to things you already know either through similarities or through differences is a great way to improve how fast you can learn something. It’ll also improve your ability to remember it later.
That’s why I like to give you examples of things you can relate to when explaining new concepts. You might forget some of the details and that’s okay. You can always look those up later when needed. Having a firm grasp of the basic concepts is important though to help guide you as you refresh yourself on the details.
The topics today are actually very related to everything I’ve just said. That’s probably why I went off on that sidetrack. Whenever I think of how things are related, I think of how our memories work on relations. And graphs, trees, and hierarchies are all about relations.
A graph is the most general way to relate things. A good example is a map of world countries in Europe or of the states in a map of the United States. Think of how the countries are positioned so they touch one another. In order to go from one country to another, you can either go straight there or you can take a winding path through many countries. You might even pass through a particular country many times on your journey. And with modern airline travel, you can even go from one country to another even if they don’t share a border.
Each country in this example is called a vertex in a graph. The connections between countries either directly through a shared border or indirectly by flying are called edges in a graph. If you were to draw a graph of Europe, you could start by drawing a dot for each country. It helps to put the dots on the graph in the general location of the center of each country. But you don’t have to. You can put the dots wherever you want and they don’t have to follow any scale. Big countries or small don’t matter. Each country gets a dot or a vertex in the graph.
This type of graph only needs two dimensions but a more complicated graph that represents important points in an object will likely need points drawn in 3 dimensions so it’s not flat. Our world isn’t flat but it’s big enough that a flat map does a very good job. And when you’re just trying to figure out all the various ways to get from one country to another, it probably doesn’t matter very much if one country is at a higher elevation than another. So a flat 2 dimensional graph is just fine.
Once you have your vertices drawn, then you can start working on the connections. Now, the word vertex is a Latin word that wasn’t brought into the English language very well. The traditional way to say the plural form of vertex is vertices. But it’s also perfectly okay to say vertexes. There’s a little less tongue twisting needed to say vertices which might explain why it’s a little more common. But vertexes fits in better with how the English language forms plurals. There’s no right or wrong way here. Both are just fine.
There’s lots of things to consider when making the edges. What if there’s more than one way to get from one vertex to another? Should you use multiple edges or combine them together into one? What if one way uses a bullet train so it’s fast and easy while another uses pack mules through the mountains? Can you go both ways? Or is the connection one way only? What about cost or tolls? Should that be included? Maybe waiting times to get visas?
What do you do if one or more vertices are isolated with no way to get to the other vertices? Maybe one of the countries is led by a ruler who wants nothing to do with the other countries and blocks all travel. That might be bad for the citizens but is just fine for a graph.
How often will the connections change? Maybe new roads will be built or new regulations enacted that restrict movement. And maybe the connections could change multiple times each day. During rush hour, what was previously a good connection can become jammed with too many cars. Or maybe there’s an accident or flood blocking a major road. That’s when a graph will help you find a different route to your destination.
Okay, let’s switch over to trees now and explore how they compare with graphs. First of all a tree is a special kind of graph. All trees are actually graphs. But not all graphs can be called trees. There are four special conditions that a graph must follow in order to be considered a tree.
• #1 There can be no cycles in a tree. This doesn’t mean that there are no bicycle paths connecting countries. A cycle in this sense is a loop or a way to go around and around in the edges.
• #2 Every vertex represents a node that is the root of a subtree. Even a single node can be considered the root of its own subtree. Usually trees refer to the vertices as nodes instead. The two terms are somewhat interchangeable and if you want to you can refer to both of them as nodes even for a graph.
• #3 Every two nodes in a tree are connected by exactly one path. That path might have to go up the tree through parent nodes and back down again through other nodes. But it will exist.
• And #4 A tree is fully connected and has exactly one less edge or connection than nodes. There are no unconnected nodes allowed in a tree.
What do I mean by there being one less connection than there are nodes? Well, let’s say we have a tree with just two nodes. The two nodes must be connected with a single connection. And 1 is exactly one less than 2. If there’s a tree with three nodes, then there must be 2 connections. If all three nodes were connected directly, then that would need 3 connections and you would have a graph with a cycle in it. Even if you doubled up on one of the connections so maybe node 1 is connected twice to node 2 and then node 2 is connected to node 3. This would still result in a cycle between node 1 and node 2. By that I mean that you could go from node 1 to node 2 using the first connection and then back to node 1 again using the second connection.
You can think of a tree as the branch structure of a real tree. It starts out with the trunk. This is called the root. I know, in a real tree, the roots are underground. Just ignore that for now. The root is the trunk and branches split off from there. Every place where a branch splits is a node. You can follow this splitting from the trunk all the way to each twig and there’s just a single path to each twig. If you want to go from one twig to another, then you can follow the path back towards the trunk until both twigs share the same branch and then follow the path to the other twig. Again, there’s just a single path from any node to another. Each node in the tree can be thought of as its own trunk of its own smaller tree.
However, if you cut off a branch, you don’t have two trees in real life. You do have two trees in programming. And if this was a graph, you would continue to have a single graph with disconnected nodes.
All this comparison with real trees is just an example. I know that in real life, it is possible to cut off a branch of some kinds of trees, like a willow, and if you stick that cutoff branch in the ground, it’ll grow into its own tree. And some trees in the tropics can grow roots from the branches that can wrap back around the tree. These roots resemble cycles in a graph because they can join back into other nodes.
When drawing a tree, you don’t have to follow the way a real tree looks. Many times, you’ll see the root node drawn at the top and leaf nodes drawn at the bottom. A node is considered to be a leaf node if it has no further nodes. You could even draw a tree with the root node in the center and the other nodes branching away in all directions like a mind map.
So how do hierarchies fit into all this? A hierarchy is a tree with a couple extra properties.
• The first is inheritance either up or down the hierarchy. If you have a hierarchy representing the managers at your company and one of your managers leaves the company, that doesn’t mean that your group immediately forms its own hierarchy in isolation. You remain in the same hierarchy and inherit guidance from the remaining managers. A tree would split into two separate trees if a connection is removed like this. While a hierarchy absorbs the loss of the connection through inheritance. That covers inheritance down the hierarchy. What about inheritance up the hierarchy? This implies that the root of a hierarchy is not complete without all the nodes in the tree. Would you be happy if you bought a new dining table and it was missing a leg? A tree would have no problem with this. But a hierarchy representing the table would not be complete with missing nodes.
• The second property of hierarchies is that they consider roles. With a tree, each node appears once in the tree and is completely different from any other node. In other words, each node has a unique identity even if the node values are the same. But with a hierarchy, the nodes can take on roles with can then refer to the same thing. Back to the management hierarchy, what would you do if a manager needed to fill two positions either temporarily or permanently? A tree would need two copies of the same person. But a hierarchy could recognize that a single person is filling both roles.