A Brief Descent into JavaScript Trees
Jill
Posted on September 29, 2019
The creation of JavaScript trees are a lot like the creation of trees in nature. A seed is planted, and over time can evolve into a huge (or tiny, looking at you Bonsai) perennial plant that is able to pass on it's genetic information the same way the tree itself received it, via propagation.
The only difference between trees in nature and the Abstract Data Structures called Trees (besides the obvious), is that ADS Trees grow upside down.
e.g. The Document Object Model, or the DOM Tree:
The DOM is not always so clear to understand(or really exciting to look at), but not to worry, this easy-to-follow guide will help you get a better grasp on how ADS Trees grow from the top, but start at the root!
What I mean by that, is that JavaScript is read from top to bottom, so what renders on the screen actually looks something like a root system! However, this is only trivial and not something to get hung up on, so let's get started.
A Tree starts with a root node, a storage container for it's children that will be exact copies of the tree, and various methods that originate from the Tree prototype.
Whenever new versions of the Tree are created using the constructor function, they are called instances. In this example, I'll be using ES6 syntax, and in order to really relate to the hierarchical aspects of this data structure, I'll be referencing America's favorite family.
This grouped data is constructed by calling the 'class' keyword, and giving the group a name that will be the origin of instances' prototypical inheritance.
Our class is called 'Soprano', our 'root' node is the constructor which will point to all the instances of the Tree, and our children are 'capos'. There are also a few other characteristics and a custom method called 'doAFavor' that alters a characteristic on the instance when it is called as a method of that instance.
Now that we've created our Tree and given it a few characteristics that we want our family members to have, we can call the class constructor, using the new keyword to create new instances of the Tree.
Now we see that even though every Tree began with the same characteristics that were created in the constructor, we can also alter the instances in a modular manner and make changes to each member's characteristics, without altering the others, like slight variations in each family member's genetic code.
In nature, this is called 'variegation', and it's just as cool in JavaScript.
The instances all trace back to the root via edges, (just like tree branches), and the edges are what extend our root to all the way to the very farthest leaf on the tree. Edges hold our tree together, and connect descendants to their ancestors, they are the way Trees utilize linear time complexity.
If we wanted to check if our family contained certain members or add new members when the books open or remove old members when they go into the witness protection, we could do that too, but the larger our family gets, the longer that's going to take thanks to all the edges that have to be checked first.
Let's just keep it simple for now and see how Tony turned out:
Nice! We see Tony's Tree, and even though he was originally just an offshoot of our Soprano Tree constructor, he now has his own unique memory and lineage. Just like a regular's tree's rings tells it's story, Tony's Tree has also been rendered dynamically so that we see his information has changed as the program went on, while the rest of his "family" remained innocent, dues-paying Union Members. Doing all those favors really paid off for Tony!
Just for fun, let's check out Chris' Tree:
Excellent, so we see that not only does our Tony Tree update to the specifics we give it, but also that our Chris Tree updates as well, while all of our other Soprano members are still unchanged.
Next time you're trying to store some hierarchical data, consider planting a seed, to grow a root, to sprout a thriving, robust tree that somehow grows best upside down.
Thanks for reading!
Posted on September 29, 2019
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
November 29, 2024