Hello world, I'm Nico. I'm a student studying software engineering in New Orleans. This week I learned about data structures, and today I will give a quick explanation on one of the most common data structures around: trees.
Before we jump into trees, let's start with a little bit of computer science. Data structures are simply a way for us to store and hold our data. I know that sounds too simple, but it's true! Every data structure tends to have methods for inserting, removing, and finding an element in an array. Different data structures come with unique pros and cons and unique time complexities. If you have any familiarity with Javascript, you already know about one data structure: arrays. Arrays aren't something that only exists in Javascript, but they are used that much that Javascript is kind enough to have a feature that implements arrays for us. Now back to trees...
Trees are non-linear data structures. This means that, unlike some other data structures like Arrays or Stacks, trees have no set start or end.
Trees store nodes. The first node that is put into a Tree is called the root (see why it's called a tree?) This node can have child nodes that can only be accessed by first accessing the root node. That second node can then have its own children and so on and so on. The tree is storing all of the data in a hierarchical manner, this means that if we want to get to a child node, we first have to go through the root and then to the parent and continue to until we finally reach our desired node.
Some quick terminology for trees:
- root: the initial node that every other node is linked to.
- parent: the node that the has a reference to another node.
- child: any node that has a parent node linked to it.
- sibling: two nodes that share the same parent.
- leaf: a node that doesn't have any children.
I understand that this might be hard to visualize, so I have a picture!
A great example of a Tree data structure is the file system on your computer. The PC is the root of the entire file system. Documents and Desktop are its children which makes them both siblings. They then have their own children all the way down to the "2018 Taxes" which has no children at all, making it a leaf.
To get to your music folder you have to start at your PC, then to your desktop and then you can access your music folder and whatever you have stored in there.
Another example of a tree data structure is the DOM element in HTML. The root of the body, and every tag you add in the body can have its own children and so on and so on.
A great thing about Trees is its time complexity. Inserting, removing, and finding a value in a tree all have logarithmic time complexities. This just means that if you had a tree with a high quantity of data the task of traversing the tree would only increase at a smaller rate every time. This is very useful if you are thinking about the possibilities of scaling your website or application to be usable for thousands or even millions of people.
Top comments (0)