Trees Overview

[00:00:00]
>> All we did were linked lists arrays, searching, sorting, all the things we're gonna be shifting gears and going into what is considered more of the advanced ish data structure. So this would represent probably the last 4 to 5 weeks of your second semester in college and it will bleed into a little bit of the fourth class usually in college.

[00:00:21]
Fourth class being advanced data structures. And so I hope that everyone practiced a little bit of recursion if you're weak at recursion, if you're great at recursion, this will be easy breezy beautiful data structures. All right, eventually all things lead to trees. Well, that's technically a lie. All roads lead to Rome.

[00:00:39]
But all data structures eventually become graphs and all data structures really are graphs if you think about it, but I always end up using trees on projects. They just somehow are everywhere. I don't know what it is, but it just happens all the time, and so we're gonna kind of start going over them.

[00:00:55]
Anyway, so where are trees? Your file system is a tree. So let's just jump over here and just do a simple LS of my route. So, if you're on Windows that'd be C:/ or \ or a slash that's the opposite of Unix. Effectively, if you think about that there is a single point on my drive in which has many directories.

[00:01:15]
Each one of those directories can have many subdirectories, they can actually point to other directories which kind of breaks the tree concept, but we'll just keep going with the tree concept here. They just start from a top, a single point and go on down. That's effectively a tree, your hard drive and how it's organized is effectively a tree.

[00:01:31]
The DOM, your DOM is also a tree. Think about it, body or HTML body, thousands of div tags. I don't know how many div tags are in a website, but I know what's going up faster than the stock market. And so that's a tree as well. It's a general tree, it has many children and have zero to many children.

[00:01:49]
And there's many, many more compilers abstract syntax tree if you've been to a s t explorer.net. I think it is, you get to play with the tree that is what Babel transforms from one type of JavaScript to another type of JavaScript. So it is something that's pretty useful to just have a fundamental understanding of.

[00:02:09]
And so hopefully today, you will be able to just kind of hurdle that, be able to be understanding exactly what trees are. All right, so we're gonna do a quick whiteboard example and just solidify this. Just in case none of those examples stuck with you, let's just kind of walk over exactly what they are.

[00:02:31]
All right, so a tree usually when we draw are represented by nodes, and you can think of a node a lot like the linked list node, right? Up, there's an O in there. And it's generic probably over some sort of t in which there's different ways we can represent a node in a tree.

[00:02:47]
But let's go with this, there will be something like a value, and then there's gonna be something like children. So instead of having a next or previous, you can have an array of possible connections. Now, that means there can be zero or more connections. So if I were to draw this out, it would look something like this, right?

[00:03:10]
There is many, many, many connections, and you can just imagine your file system here as it goes, right? This makes a lot of sense if you've seen anything that looks like this, you can think of this as HTML, right? This as your body, and then of course all those lovely div tags over and over again.

[00:03:30]
That's why when you use a node in that, if you ever actually use vanilla JavaScript you'll actually have access to a node which does actually have access to a children's array. And you can kind of walk around and do that, and each one of those children have possible children, so forth and so on.

[00:03:45]
You get the idea, right? Pretty fun. There's other ways you can represent nodes, and we will do other ways but right now, we'll just kind of focus on the general case. All right, so let's talk about some terminology. Root, when I say the word root, what I'm saying is your top most node, right?

[00:04:02]
So the one that's at the very tippy top of the tree in the file system that is slash or C colon other slash. In most trees that is just usually some node that has either no value, which we'll see in some cases, or a middle value near the median, the smallest value, the largest value.

[00:04:22]
Usually the root node has some level of importance in a lot of the data structures we'll be using. All right, second height. Height is simply described as the longest path from the root to the most childish node, right? The most the greatest grand descendant of the tree. So, whatever that is, that is the height of the tree.

[00:04:39]
Now, that means that trees don't have to be balanced, they don't have to be in some sort of perfect ordering, they may have one really, really long strand and that would be the height of your tree. So, even if 99% of your tree exists within three levels and only one branch goes down 100, the heights are 100.

[00:04:57]
Let's see, binary tree, binary trees are pretty simple. Binary trees are what we're gonna be mainly focusing on today cuz they tend to be the data structure that is most frequent in a lot of items. It's either general or binary. There are some other cool ones, maps and C++ are a form of tree if I'm not mistaken.

[00:05:13]
A binary tree is exactly what you think it is. It's just a tree with at max two children. And we did a lot of algorithms that involved splitting things in half from yesterday, so you can imagine that today, we'll be splitting things in half again. Often when you're using a binary tree, you'll see something like left and right, instead of a children array.

[00:05:36]
Just cuz it's a lot simpler. It's already assumed that there's going to be a left, there's going to be a right, it's a binary tree. So it makes it a lot easier not to have an array of 0 to 2. And all these same properties apply to a binary tree.

[00:05:50]
Root, height, all that general tree, the exact same thing except for it's one too many we've already kind of shown a general tree. A binary search tree is simply a tree with a specific ordering to it. And usually, it's a strong ordering it actually is in some sort of very strong order, it's not like a weak ordering if you remember from yesterday.

[00:06:08]
A weak ordering had some level of ordering to it, a binary tree tends to have a very strong ordering. Leaves, that's simply a node without any more children. So this is binary tree, if there's a bunch of children here, this wouldn't be a node until eventually or a leaf until eventually we get to a part where there's children with an empty array, right?

[00:06:27]
So this one leaf, if we had just a single note here, it's a leaf. So there's many leaves to a tree. I've never liked when they try to take a terminology and then use like kitschy terms from reality. So a tree with leaves, I don't really like any of that kind of things.

[00:06:43]
Terminus would have been a much better but they chose leaf, fantastic. A balanced tree is a tree in which all the child nodes, all the leaves eventually are on the same level. That'd be a perfectly balanced tree, the more it's out of balance, the more problematic some of the algorithms will become.

[00:07:03]
And so, that is something to kind of think about is that it's not always easy to keep a tree balanced. You don't know when you're gonna get the data, but it's a whole branch of trees is just keeping them balanced. A whole branch of trees, I just realized what a great pun that was.

[00:07:17]
Branching factor, how many children there are? So, a binary tree has a branching factor of two, a general tree could have a branching factor of infinity, right? You don't know how big that is. There's other types of trees, we're not gonna be touching on pretty much any type of tree other than general and binary.

[00:07:34]
Hopefully this makes sense and seeing Quicksort from yesterday how we drew it out, it's a lot like a binary tree, right? We had Quicksort. We would split the input in half and have another Quicksort and split the input in half. It's effectively a binary tree in some sort of sense.