Skip to main content
Loading Explore guides…
JavaScript DS · Acedra
Home
Explore
Computer Science
JavaScript DS
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
265 segments
Copy
Hide video
0:00
Hi, I'm Beau in this video I will be going over some common data structures and algorithms in JavaScript I'll be showing you how to implement them in JavaScript So if you want to see the exact list You can check the description and I have links to all the code in the description as well. So let's get started
0:23
A stack of books is a great example of the stack data structure If you make a stack of books The topmost book in the stack was the one that you put there last if you remove that book from your stack stop You would expose the book that was put there before The last book stacks are of last in first out type of service The last book you put on top of a stack would be the first book
0:46
You take off the stack. Another example of the stack is your browsers back button. If you look up here, we just opened up facebook.com So we add it to the top of the stack of sites that we've already visited previously Would you stack top push push is one of the stack methods you push Facebook on top of the stack? This middle is what it looks like when we are Visiting Facebook and then this bottom image is where we press the back button to navigate back to Twitter
1:14
So we pop off the most recent URL and we just leave Twitter at the top of it The function is traditionally provided in the stack our push for placing data onto a stack pop for removing the top element of a stack peak for displaying the top element of a stack and length or size for determining how many elements are on a stack a Nice feature of JavaScript. Is that the array? object Already has all the functions we need in order to use it as a stack so you could just use an array as a stack
1:51
I will show you how to do this using an array But then I will actually create a stack class and show you how that works, too I'm going to use an array stack to find words that are palindromes a Palindrome is a word that is spelled the same forwards and backwards such as Bob b.o.b. Or racecar RAC eca are okay, so we have our letters equals an empty array and That's the stack Because remember I said arrays are have all the functions of a stack. So look at how this program works first
2:22
we're gonna set a word to be anywhere we want and we're gonna choose race car, which is a palindrome and Then we are going to have a variable which is just a empty string for our word or first word We're going to use the stack to fill up the r-word variable with the reverse of the word variable The first thing we're going to do is put the letters of the word into the stack So we have a for loop here and we're going to start at Index 0 and go to the last index of the word length
2:54
So an index in a string is just which character we're looking at so we're going to do letters which remember is our stack dot put The step function where you put something on top of the stack and we're going to push word Index I so that's just going to take This for loop is just going to take each Letter of our word because we have an X 0 and X 1 and X 2 each letters new index and push it on to the letter stack Now we're going to pop off the stack in reverse order so we can create the r-word
3:30
variable which is the reverse of the word variable another for loop and Now we are going to have the R word and we're going to add one letter at a time from the stack by popping off the top letter and Because they were put in order they're going to be popped off in reversed order Now we have a string that should be the reverse of the first word So word and our words to be reverse of each other now to check it's a palindrome We just say if our word equals equals equals word. It is a palindrome
4:04
Over else it's not a palindrome. So let's run that and see what happens and
4:09
Racecard is a palindrome but if we change that to
4:15
Free code yeah and run that
4:18
Nope, it's not a palindrome Okay, that was just a basic usage of a stack using an array now. I will show you how to implement a stack in JavaScript so you can understand stacks a little more You probably would never do that because you can use an array as a staff, but this should possibly help you understand How stacks work a little better So here's where we're going to create the stack, which is going to be this function here We're going to have two variables this that count
4:48
and this that storage now this storage is an empty object and Count is gonna keep track of how many items are in the stack So here are all the different methods We have pushed this step push is going to add a value to the end of the stack You're gonna pass end the value this that storage or storage is the empty object At the end X this that count we are going to add the value so we're gonna put the value on the top of the stack or the end of the stack and then we're just going to increment
5:20
Count up one so now it's showing that we have another item in the stack the next function We're going to remove and return the value at the end of the stack or at the top of the stack Which is the stuff top this is gonna pop an item off So if this that count equals equals zero That means there's nothing of the stack and we're going to return undefined because there is nothing in the stack once we return undefined right
5:42
We're not gonna do anything it the rest of this code here because we've already returned from this function if we're popping off something We're going to have to decrement the count. So it's a count minus one So one less we're gonna set the result to this that storage which is the object for our stack and index this count which is the last item in the stack and Then we're going to delete that item and we're gonna return result. So you get the last item back
6:09
but it will be deleted off of the stack and there's just a few more methods this dot size is going to return this that count which is the number of items in the stack and then the last function is This that peak which is going to return the value at the end of the stack But it will not Remove it like pop so peek and pop are kind of similar but pop removes the item and peek does not remove the item So return this dot storage and then this that count minus one
6:42
This that count would actually be they'll index one after the final item because what that's where you would add in a new item But you would have to do minus 1 to get the last item And if you're peeking you do not want to pass in the value, so let me take that bad off there So you only pass in the value when you're pushing in something
7:02
Let's see how this would work down here
7:13
Okay, we are going to create a variable called my stack which is a new stack which is what we just defined up there We're gonna push one on to it to the top. Don't push two on the top so it's just a stack with one and then two we're going to Peak and we're gonna have to console dot log this because it's going to just return The top number of the staff which should be two now, we're gonna pop off to so it's going to return to again But it's gonna remove it and if we peek will she be back to one?
7:43
And before we run that I forgot these extra parentheses here Because these are functions and need the parentheses at the end of all functions. So let's try that
7:53
Okay, see we peaked at two we popped off two and then when we peaked again It was one because two was was removed. Now. You can also add other things to the stack
8:13
Now I'm going to push a string onto the stack and we're going to check the size then want a peak and I'm gonna pop it off anyway a peak again. So let's see what that does So we push the one we push to Repeat with show two we pop whoosh pop off, too we peaked again which showed one so there's only one thing in the stack then we pushed free code camp to string and we
8:40
Console dot log the size and now this item to the stack is just one on The bottom and then free code camp on the top We're going to peak which is going to show free coke camp now. We're going to pop Which is going to pop off and show freako camp and they're gonna peak again and we'll see that it's just one on the bottom
9:01
Well, those are the basics of stack
9:06
The set data structure is kind of like an array except there are no duplicate items and the values are not in any particular order the Typical use first set is to simply check for the presence of an item I'm going to show you how to implement a set function bf6 actually has a built in set object however, the built in set objects does not contain all the methods that are Common to sets so you may still have to implement part of the set yourself
9:37
Depending on what you're gonna use it for when I show you the implementation for the set I will tell you which methods are part of the es6 set and which are not so we're just gonna go through this code We're gonna call it my set. Now we could call it set but I want to make it different than the es6 set So this is my set. So here's just the collection This set is gonna be a collection of items and we're gonna store them in an array which an array can't have duplicate items
10:02
But we're gonna implement this in such a way that you cannot add duplicate items to this array this method the method Has is gonna check for the presence of an element and then return true or false So you have passed in the element and it's going to do collection that index of element is Not negative one. So if the element is not in the collection, it's gonna return negative one. So if it doesn't Return negative one. It's true. So if it's not negative one, it's true. That means the
10:33
Element is in the array else. It's false. Now. We have the values This is going to return all the valleys of the set pretty straightforward. Just return the collection Now I've add we're gonna add an element to this set But first we have to check if the Elm is in the set already so we're gonna call the the method we've already defined that has method and See if the collection has the element if it does not have the element then we can add it We're gonna push that element to that
11:02
Collection array and we're gonna return true else
11:06
We're gonna return false. So if we don't push an element to the collection, we're returning false Now we have removed. This is going to remove an element. So first we just check if the element is in the collection and if it is in the collection We're gonna find out what the index of the element is and then we're gonna remove it splice is means we're gonna take out We're gonna take out an element in the array starting at the index of the element and going for one element
11:36
we're gonna take out one element and then we're gonna return true or We're gonna return false if that element is not in the collection
11:45
Then we're just going to return the size of the collection
11:50
We're just going to turn collection that length every method we've gone through so far is in the es6 implementation of the set so the es6 set has values add Remove in size except remove is delete in the ex6 Set instead of calling remove you're gonna call delete, but all the other things are included another thing is size is not a method in the es6 set size is a Property that just means that when you're calling it You're not going to put parenthesis at after the the method
12:27
Because it's just a property so you can do set that size and sort of set that size with parentheses after it. Okay? now we're going to get into the methods that are not in the es6 implementation of the set, but are Often included in sets the next few methods actually just help you work with Sets and when you're working with two different sets So we have Union this method is going to return the union of two sets
12:54
So it's gonna combine the sets but leave out any duplicates in the combination of the sets so we're gonna Call the Union method on the original set or I'm gonna pass in the other set that we want to combine We're gonna create a new set which this should be my set same what's down here because we want to make it distinct from The es6 set so we have the the Union set which is just a new set That's what we're going to combine the sets into we have the first step
13:26
Which is this stop values and the values were just calling the the values? that up here to return the collection and The second set is going to be the other set that values For a new first set for each and for each value in that set We're gonna do a union set that add to add the value then we do the same thing second set for Each and for each value in the second set we're going to add the value Remember the add method already does not add the value if it's a duplicate
13:57
So the Union set now will not contain any duplicates and since for the set data structure the order doesn't matter We don't have to have the values in any particular order and then we're going to return the Union set Now we have intersection which is going to return the intersection of the two sets as a new set So we're gonna make a new set here intersection set equals new My set the first set again
14:24
We're gonna call the best values to get all the values in the first set now for each value in the first set We are going to check if the other set has the value We are going to add it and then we're going to return the intersection set So the intersection is just all the items that are in both sets And that's we're gonna return that as a new set and this next function We're also gonna have to add them my there. So this is the difference
14:55
So the difference between the sets so all the items that are in one set, but not the other set So we're gonna create a new set again the different set. And again, we're gonna get the values of the first step now This is very similar to the intersection. We're going to go through each value in the first set and If the other set does not have the value remember up here we were seeing its other set hand the value now we're gonna use the not operator the exclamation point to see if
15:27
The value is not in the set and we're going to add that to the different set then we'll return the different set and the last method we're going to talk about is the subset and This is going to test if the set is a subset of a different set. So it's going to test the first set is Completely contained within the second set. So it's just gonna return true or false so we're gonna pass in the other set we're gonna again get all the values of the first set and
16:00
we're going to call this function first set that every and what that Every method is going to do is going to test whether all the elements in the array Pass the tests implemented by the provided function. So we're gonna test if all the elements in the first set Will pass this function which is other set that has value are all the elements in the first set Are they in the second set? So we're gonna see if the first set is a subset of the second set
16:32
So that's the set data structure and let's quickly just show you some some uses of the set So we have set a as my new my set set B is new my set We're going to add to set a a look edit set B B we had to set BC or ad to set B a and we're going to add to set B D and now we're gonna see if set a is a subset of set B so is Set a is every item in set a which is actually just the letter a and set B Which it is because it's right here. Let's run that and it should say true. Let's do some other things
17:12
Okay, and this is the set a that intersection set B is going to return a new set which we are then going to call the values function so we can see all the valleys in that set and it's just a because the only value that's in both set a and set B is a But we can do a lot of the same things with the built in set I'm gonna copy all this instead of long That's my set or just going to be half set. We're gonna do set C and set D
17:51
Okay, so here's one difference with the es6 set Is that when you call the values method instead of returning an array, it's going to return an iterator So you can see objects set iterator here and then you can still iterate through all the items in the array besides that all the other Methods that a set has are very similar to the methis ette that we implemented so we can do set D delete
18:20
Now this is instead of remove
18:26
So we're gonna delete the a and then we're going to cancel that log and check if that D has a
18:35
And we can see it's false because it's been deleted
18:42
And We can also try to add D which is already in the set Oh and there is one final thing that's different with the es6 implementation The add method is not gonna return true or false Whether the item has been added or not besides adding the item what it's going to return So whatever it was, it's gonna cancel that log is is the set itself. It's not an array of the set It's going to return the full set. So if we run that you can see here It's going to return the set which is an object
19:17
And since it's an object, it's not gonna show all the different items in this set. Okay, that's the set data structure
19:27
The queue data structure is a way to hold data it's similar to a stack while a stack is first in last out a queue is first in first out an Example in real life is when you were waiting in line to buy something in a store The first person to get in the line is the first person to get to the cash register Another example is a print queue when a lot of people are printing documents at the same printer The documents are printed in the order. They were sent to the print queue in
19:55
JavaScript just like a stack you can implement a queue with just an array If you want a limit and array to just the traditional queue methods, you must create it yourself Let me show you one such implementation so we have the queue right here, and we're going to have a collection that's going to collect all the items in the queue and this is just kind of a helper function to Print or it's a console that log the collection and here that the main main methods of a queue we have in queue
20:22
which is going to push the First item onto the queue and then we have DQ which is going to take an item off the queue so there's two ways to do it with an array items can go into the array at the beginning of the array or Items can go in the array at the end of the array in this implementation items are going into the array at the end of the array and Then they come off of the array at the beginning of the array to put an item onto the queue
20:52
We're just going to push that I know that element onto the queue then to DQ. We're going to use The rage IFFT dot shift just pulls off the first item of the array It removes the first item of the array and returns it another cue method is front This is just going to return what item is at the front of the array without Removing the item off of the array so we're just gonna do collection output just going to return what items at the at the zero index of the collection array and
21:26
Size we just try to figure out the size of the queue pretty straightforward just collection that length and then is empty Check if it's empty if there's not no items on the queue. So, let's see how that was gonna work here I'm just gonna uncomment that and run the code So we in cute we created a new Q then we Inc we in cute ABC So the line the end of the line is the end of the array the beginning of the line is the beginning of the array so it's gonna print a B C here and then D Q means that the
22:04
item at the beginning of the array is gonna to be removed so the a is going to be removed and then we're gonna do cute out front which I forgot to put that console.log here Okay, run that again you'll see that it's going to Check what what elements at the front of the array which is B and I'm gonna print the array again it's just me B and C because we DQ'd a another way to create a queue is a priority queue in a priority queue not only do you pass the element into the queue you also pass the
22:39
Priority of the element so if all the priorities are the same number It's going to behave just like a normal queue but when you pass in elements at different priorities The elements that are passed in with a higher priority are sent to the beginning of the queue. So all elements with priority 5 are Ahead of elements with priority 4 but if elements have the same priority, it just behaves like a normal Q So let me explain how the priority queue works first
23:09
Let me show you an example of this code down here where we're using the priority queue so to create the priority queue and then we're going to in queue something and so we're gonna pass in an array the first Element in the array is the item. We want to put on to the priority queue The second thing in the array is the priority so you can see I'm not pushing them on in the same order two three one but if I run this when we that print the collection it's going to print in the order of the
23:45
Priority and just to show another example Let me add an item with the same priority as an item. We already have
23:52
And if I run that You can see these two items have the same priority So they're in the queue in the order that they were pushed on to the queue So everything's the same on a priority queue except the in queue function So in the in queue function first, we're going to check if the queue is empty if it's empty You're just going to push on the element But if it's not empty you're gonna have to check the priorities to see where to put the element on so we're gonna create a variable just to
24:25
Check whether we've added the item to the queue or not And it would fall it starts at false And now we're gonna have to run through each element in the the collection or the queue to check what the priorities are So we have this floor loop that's gonna run through each item in the collection and we're gonna check is the element at index one remember the element that we pass into the queue is an array index zero is the item you want to put into the queue and
24:51
Index one is the priority. So is the priority of the element we're passing into the queue less than the priority of The item in the collection that we're checking and see we're using this eye from the for loop We're gonna go through and check every item in the collection And we're going to check the index 1 which is the priority of that item And then if the priority is less than the item we're going to add That item or the element to the collection array
25:21
That's what this splice is doing and then we're gonna say add it equals true. We're gonna break out of the loop here and Then we're gonna be done except if the element hasn't been added We are going to then push the element to the array and the only thing that's slightly different Is this DQ method? And this is the way I did is kind of optional you could return the entire element with the item and the priority or you can do an idea where I just returned the
25:51
Item without the priority here. That's just index 0 of this value Which is the the items that we got off the beginning of the array. Well, those are cues and priority queues
26:05
A tree data structure is a way to hold data that when visualized looks like a tree you would see in nature now This is actually what we visualized a tree data structure to look like all data points in the tree are called nodes The top of the tree is called the root node and from here It branches out into additional nodes each of which may have more child nodes and so on Nodes with branches leading to other nodes are referred to as the parent of the node of the branches that leads to the child
26:37
Leaf nodes are nodes at the end of the tree that have no children also Any children of a node are parents of their own sub tree in this video We will be covering a specific type of tree called a binary search tree While the tree data structure can have any number of branches at a single node for instance C the C here? There's F G H. It has three branches at a single node a binary tree. However can only have two branches for every node
27:02
So look down here. Here's a binary tree each node. Only has two branches Also binary search trees are ordered each subtree is less than or equal to the painter node and each Right subtree is greater than or equal to the parent node Because they use the principle of binary search on average operations are able to skip about half of the tree so that each lookup Insertion or deletion takes time proportional to the logarithm of the number of items stored in the tree
27:31
This is much better than the linear time required to find items by key in an unsorted array but slower than the corresponding Operations on a hash table. So let's see how this works in JavaScript here We're going to use classes to create the binary search tree basically We're going to create two classes the no class in the BST or binary search tree class The no class represents each node in the tree and there's any three data properties
27:57
We have the data which is what we're actually trying to store and we have this that left and this that right Which are going to point to the left node and the right node? So in the binary search tree, we're going to have the constructor which just creates the the root node Which is the top of the tree which it starts as null and then we're gonna have the add function So this is how we are going to add something to the tree. So we're gonna add the data
28:23
We're going to get a reference to the root node. But if this is the first node node will be null in that case We're just gonna set the root node to the new note the new data We just put in so new node data So we're just gonna create a node based on that data If it's not the first node We're gonna have to figure out where to put this node in the tree to figure out where to place the new node we are going to use a Recursive function so I'm gonna create this function, which is search tree
28:56
We're gonna pass in the node which starts off as a root node If the data we pass in is less than no dot data That means we're going to put the note on the left side of the tree so if The node dot left side of the tree is null we're just going to assign node dot left to the new node And then we'll return but if no doubt left is not null. We're going to return search tree No doubt left that just means we're gonna continue Searching this is where it the recursive nature comes in
29:27
It's going to run the search tree function again and continue working down the tree to find where to put the node And you can see here else if if the data is more than no data That means we're gonna put the note on the right side So if no dot write equals equals equals null then we just assign no dot right to the new node And we can return else if if the node right does not equal null. We're gonna have to keep searching
29:55
So we're gonna return search tree. No dot right so else that means data is not less than no dot data data is not More than no dot data, so they must be equal if they're equal. We're not going to add the data to the tree We're just gonna return null. So this is the search tree function And this is how we initially call the search tree function return search tree node, which starts out as a root node But then it can be called with different nodes as it's going recursively through the tree
30:27
Let's say you have 50 in your tree and you have 17 in your and you want to add 23 first It's going to see that the note is not null because you have things in your tree and then it's going to run the search Tree function putting in the root node, which is 50, then we'll see if data is less than no dot data Which it is because 23 is less than 50. We're gonna go to the the node dot left if no doubt left is
30:53
Null we would put it here, but it's not because there's a 17 here. Remember we're just adding the number 23 So else if if left no doubt left does not equal null, which is true We are going to return the search tree. No dot left So we we are now gonna run this search tree function but passed in the 17 So now we're gonna see does is data less than no data Well now date is 23 but no data is 17. So this is false now We're gonna go down to this is data more than node data. Yeah 23 is more than 17
31:28
Well is no dot writeln all in this example? we're saying that 23 isn't there so no dot right would be null and Then we can just set no dot right to be the new node the next functions We're going to talk about our find min and fine max So we're just gonna be find the minimum of the array and finding the maximum of the array if you look at this binary search Tree right here You can see the minimum is all the way on the left side 9 the math is all the way on the right side
31:54
76 so just using that knowledge makes it easy to find men and find max So I'm going to set the current node to the root node. And so the minutes can get all the way on the left so While this dot Left does not equal null the current node is going to be current dot left and then at the very end It's gonna return current data. So we're gonna check this if the left side is not null We're gonna go to the next one
32:17
If it's not learn all we're gonna go to this one if it's not null when we go to this one now The next is null because there's nothing to the left of 9, so we're gonna return current data We're gonna return the 9 cuz that's the data on the very left side fine Max is just the same way but the opposite we're gonna start at current which is going to this dot root Which is gonna start at the top while current dot right does not equal null Well, this does not equal null fit at 72
32:42
Then we're gonna go to the next loop current equals current dot right when we go to the next one But now current that right isn't all because there's nothing to the right of 76 so we can just return Current data now we have the find function now is present is very similar But instead of returning the node, we're just gonna return true or false whether the data is in the tree So we're starting at the top
33:05
They're written out while current that means while there is a current node while current is not null We're going to do the following if data equals equals equals current that data return true That means we found it if we haven't found it we're going to see is data Less than current at data now current equals current out left. So we're gonna start searching on the left side else Well data must be more than current data So we're going to start searching on the right side
33:32
and we're going to keep searching and if we never find it if We never find that data equals equals current that data and return true That means is not in the tree and we can return false Okay, the remove function is a little more complicated than the other functions We've covered just like in the add function and their move function. There's gonna be a recursive function So we're gonna create this function here kant's remove node equals function
33:56
Where we're gonna pass in the node and we're gonna pass in the data which is the data what we're trying to remove so we have this whole function here and Then here's where we're gonna call the function at the end This that root equals remove node and we're gonna pass in this that root and data We're assigning this that root to whatever is returned to this function here We're gonna pass in the root node, because you always start with the root node, and then the data that we're searching for
34:25
So, let's see how that works first of all We have to check if we have an empty tree if the node equals null then we have an empty tree and we can return Null now we're gonna see if does data equal no data So we're trying to see if we can find that data in the tree So if we've found the node with the data, this is what we're gonna do There's actually three different options either. No one has no children. That would be just like the 76 if there's no children We just completely delete that node
34:55
So if no doubt left equals null and no doubt Right equals null then He's there's no children just returned know when we're returning null were setting the node that had that data to null now We're gonna check if the node just has one child if node has no left child. If no dot left equals null That'll be just like this 54 here There's a node on the right but there's no node on the Left if node outlet left equals null then We're just gonna return no dot right?
35:26
That means we're gonna replace this node with whatever is on the right, which is 67 So instead of 72 points in 54 that will be replaced with 54 ZnO dot right? Which is 67 and if there's no note on the right, we're gonna do the same thing We're gonna just return the node that's on the left to be the the new node that's being pointed to it gets more complicated When the node has two children like such as v 17 if you want to replace node 17 you can't just
35:57
Put in 12 here because then what will happen to 23 is you can't just put in 23 here It isn't what will happen to 12. So let's look down here. This picture down here is kind of small Let's say we're trying to remove this 3 here that has the red X in here The way to remove this node right here would be to replace it with this node down here so if we remove 3 we can place we can replace it with 4 and then Everything will be right with the binary search tree. So if you look at what it would become
36:26
Over here. We just replaced a 4 down here with the 3 up there But how are we gonna get down to that 4 well first we have to go to the right sub node And then we have to go all the way down to the most left sub node after we've gone to the right sub node So, let's see that we're gonna create in node, which is going to be no dot, right? So in this case the temp if we're trying to delete the 3 the temp node would be no debt
36:50
Right, which would be the 6 here? Well, no tip node. That left does not equal null tip node equals No dot left. That means we're gonna keep first. We're gonna go to the right of the node We're gonna delete and then we're gonna keep me gonna keep going to the left until we get to the last one on the left Side and this one just happens before there's no more to go down because you just have to go down one
37:10
But if there was more to go down to it, just keep hopping down until it got to the most left node Now we're gonna set no dot data to tip. No data. So the node is the three up here So instead of the data of this node, being three the data the note is now four because Tim no data is four now I'm gonna set node dot right to equal and now here we're gonna call the remove node function again this is where it starts becoming recursive and we're gonna pass in the Noda the node on the right and
37:41
the tip node data, and this will keep running through the function and Set up the right side of the tree Correctly we see here we were saying if data equals no data Else if data is less than no dot data that just means we have to go to the left side of the tree because it's less and Here we're gonna call we're gonna say that no doubt left equals remove node and we're gonna call this recursive function again and pass a node up left and the data and Then we're gonna return the node else
38:12
That means data is more than no data when you know dot right and then call this recursive function again And no dot right data, and we're gonna return the num the node So you can see that the leaf is the most complicated one that we've covered especially when one node has two Leafs So let's look at how you use a binary search tree. At least this one that I've created so far So let's open up the console here. I'm gonna do Const BST equals new BST. I've created my binary search tree
38:40
we're gonna add four at two six one three five seven and then I'm gonna remove four and then we're going to file we're gonna console that log the min and the max Two times and I'm gonna check to see if 4 is present. Another thing we're gonna do is we're I'm gonna add in you remove Seven and we'll run that again. You can see it first. It's the minimum is one It's gonna console that log max which is seven but then we remove seven and now the max is going to be six and
39:09
We're gonna see is this present is for present false note 4 is not present because we've removed in This video covered all the key methods common to a binary search tree however in a future video I'll be going over a few other things you such as finding the tree height and Traversing the tree through in order preorder and postorder traversal if you want to play around with this code You can check the link to the code in the description
39:38
Finding the tree height and tree traversal Height in a tree represents the distance from the root node to any given leaf node So if you look at this example over here the root node is nine That's height zero, but if you see four and seventeen here, that's height one three six and twenty two Height two five seven and twenty our height three, so it's the distance from the root node to the leaf nodes They're kind of like layers of a cake. And that's how you're gonna count them
40:08
Different paths in a highly branched tree structure may have different heights but for a given tree There will be a minimum height and a maximum height and if the tree is balanced these values will differ at most by one So before I show you the code to implement those things I'm going to show you the use of the code We're going to go all the way down to the bottom Where we create a new binary search tree and then we add all these values with the those values
40:37
They are the same values as in the picture over here. We're going to find the men height We're going to find the map site and we're gonna check if it's balanced Let's just comment out these now. So it's only the men height is one in a console the mattes That is three, and it's not balanced The men height is the distance from the root node to the first leaf node without two children So if you look on here 17 is a root node, without two children. It has a right child, but doesn't have a left child
41:08
So the minimum height you started at the root node Which is zero and then you count to the next level which is one. So the min height is one Now the max height is just the distance from the root node To whatever the the most bottom node is so five seven and twenty are all at the max height. So zero one
41:30
two Three. So the Mac side is three now this tree is not balanced because remember if a tree is balanced the values between the Min height and the max height will be at different most by one you can see that there's a missing Number here. The reason why this tree is not balanced is because there's no number here to the left of 17 But if I uncomment out this code here We're gonna add ten now ten you see when it's being added
42:01
It's going to add to the left of seventeen because it's more than nine, but it's less than seventeen so the tin will fill this spot right here and Then we're gonna find the min height the max site and then check if it's balanced again
42:13
Okay. So now the min height is two and the max height is three the min height is going to be either this three or The ten that we just add that it's not showing up in the picture, but just imagine there's a 10 right here So we have 0 1 And then the min height is this level right here Because this is the first level that there are node without two children if you imagine there's a 10 right here so that's 2 and then 3 is out here right now is
42:44
Balanced is true the difference between the min height and max height is at most 1 So it's going to have to be either 0 or 1 To be balanced when a tree is balanced then searching through it is much more efficient We're not going to cover this in this video But there are ways that you can make a tree Automatically balance itself when you add new items and when you delete items this creates greater
43:09
Efficiency when searching the tree. Okay. Now we're going to look at these last lines. I have to have commented out here these are ways to traverse the tree tree traversal methods can be used to explore tree data structures and basically find all the values in the tree in Depth-first search a given sub trees explored as deeply as possible before the search continues on another sub tree
43:33
When I show you an example it will that will make more sense, but there's basically three ways that this can be done There's in order traversal Preorder traversal post order traversal and this last one. I'm going to talk about later this level order traversal So let me run this and then I'm going to explain it So here you look at the bottom of the console and you can see what we've logged here
43:57
For in order traversal, you're going to begin the search at the left most node and in the the rightmost node So you can see this. This just has all the numbers in order 3 4 5 6 7 9 10 17 20 22 So there's all these numbers in order you're gonna begin at the left notes most note and you're gonna add all the numbers in order now preorder traversal You can explore the root nodes before the leaves. So let's look at this
44:25
I'm gonna read off these numbers down here and I'm going to show up on the picture where they are in the picture So we're looking at the root nodes first in the list 9 is first that's a root node Then 4 that's a root node, then 3 and the next newt is gonna be six and then five and then seven then 17 and then 10 which we don't have on this picture then 22 than 20 This is a pre-order focuses on the root nodes first and then adds that their notes below that the postorder
44:56
Explores the leaf nodes before the roots. So look at this one the first node on the list is 3 because it's a leaf all the way down and then we have 5 Because that's a leaf node, and then we have 7 and then we're gonna go to 6 We're not gonna hop over to 20 over here because that's not a completely different branch of the tree You have to finish all the leaf nodes on one branch before you go to the next branch
45:18
So after 6 is 4 now is where we jump over the leaf nodes on the next branch and we use 10 Which again is not on the picture then 20 then 22 then 17 and 9 this level order is called a breadth-first Search this explores all the nodes in a given level within a tree before continuing on to the next level further it's going to do level 0 which is 9 if you see these numbers on here, and the next line is Next is gonna show 4 and 17 Then 3 6 22 then 5 7 20. So let's go over the code
45:54
So first, we're gonna go over the code for them main height and the find max ID and then it is balanced So that is balanced is pretty simple because you just call these functions that I haven't talked about yet But you na'kal find min height and see if that's less than or equal to find max height minus 1 so this is going since this is a a
46:17
Conditional statement is going to return true or false So as an example if you remember before we added the ten we have the min height of one and the Mac side of three if This Mac side is 3 3 minus 1 is 2 so is 1 less than or equal to 2 no false, so we know that the tree is not balanced we have false right here, but then we run it again down here and the max height is 3 and the min height is 2 if we do 3 minus 1 that's going to be 2 so now we have is 2 Less than or equal to 2
46:55
Yes, so we're gonna return true. So that's how we're gonna find out if it's balanced now, let's look at fine min height This is going to be a recursive function you can pass in a node, but if you don't pass in a node It's going to set the node to the root node here and then it's going to check if the node is null and Return negative 1 if you haven't added anything to the binary search tree, it's gonna return negative 1 for the height
47:18
We're gonna set the left and right to calling the Fineman high on the left and Fineman height node Right. So this is where the function becomes recursive Eventually, one of these two is going to be negative one because the left or right node is going to be null So here we are going to add one to the left if left is less than right And we're going to add one to the right else So if right is less than left and 4/5 find max Heights, it's it's the opposite
47:50
So instead of having the less than here, we have the more than here So here we're going to return left plus one as if left is more than right else Returned right plus one. Feel free to check the code in the description to play around with this yourself
48:06
The inorder preorder and postorder there's a lot of similarities to the code. So let's look at the inorder traversal first
48:14
The only thing that's going to be different and each of these in order preorder and postorder Are these three lines and the only thing that's going to be different in those three lines is the order of the lines So for all of them we're going to check if the root is null and In all this just to check if there's even a binary search tree that exists or if there's any values in it So if we find out that there is a binary search tree. We're going to do these things
48:39
we're going to create a new array of the result and we're going to add each value in the in the tree onto the result So we're going to create this function traverse in order function and you can see down here We're going to call that function and pass in the root node And then after the function has been run you're going to return the result So inside this function it's going to be recursive And remember these three lines are the only thing different between inorder preorder and postorder
49:08
It's going to change the order that we check things So in order we are going to first do this line. So this right here is
49:19
short-circuit evaluation whenever JavaScript evaluates the and Operator like this if the first thing is true It will also run the second command if the first thing is not true It will not run the second command Check my video on short-circuit evaluation to find out more about that. So if no dot left is true that means if no doubt left exists, then we are going to Run the trench reverse in order
49:51
Function on no dot left and that just calls the same function again and passes n note that left then we're going to push No dot data. So we're going to push the value in that node Onto the result array and then we are going to check if no dot right exists If it does we are going to call the traverse in order function on no dot right and if we look down here Like we're I said, they're just these three lines are different. So in pre-order, it's going to push first and
50:24
Then it's gonna call the function on note left and then it's gonna call the function I know dot right in Post order it's going to call the function on no dot left Then I call the function on node dot right and then push the data so just to order that we call these commands is going to change the order of How we get the result when traversing the tree again? You can check that code and play around with it until you can figure out exactly how it works
50:50
I'm going to go down to the level order function in this method We start by adding the root node to a queue then we begin a loop where we DQ the first item in the queue add it to a new array and then inspect both it's child sub trees if It's children are not null they are each in queued this process continues until the queue is empty We are treating a result array that we are eventually going to return now. Here's just that the queue array this is just a
51:21
Temporary array that we're using that we're eventually going to put things off that ray onto our result If this that root is not null if there actually is a binary search tree We're going to push the root node on to queue and this is a while loop So it's gonna continue going through this until we've actually added all the all the elements from the tree So while Q is the queue length is more than 0 we're gonna keep doing these things
51:47
so first we're going to let node equals Q dot shift now shift just takes off the first element in the array and Returns that element so we're gonna put the root node into node because it started out as the root node And now Q is not going to have that root node on it anymore And we're going to push no data onto that result so we've just pushed 9 onto the result and if you remember 9 is the first thing in the the level order result now if no debt left does not equal null
52:20
We are going to push no left onto the queue and if no dot right is not equal Now we're gonna push note that right onto the the queue and then then we're going to go back through the while loop We're gonna take off the first node and put into node, which remember is going to be no doubt left So we pushed on here and we are going to push that value to the results We're going to push forward to the result And now we're going to push no doubt left and we're gonna push no dot, right?
52:48
So in the queue, we're not gonna have 3 and 6 but when we go back through the while loop and we Shift off an element even though we added three and six in the last iteration of the loop The know that we're shifting off is going to be 17 Because shift is going to take the first item of the array off and three and six are at the end of the array so then it's going to get that value and so on it's going to keep going through this until it's got every value from the tree
53:22
a Hash-table is used to implement associative arrays or mappings of key value pairs Hash tables are a common way to implement the map data structure or objects They are widely used because of how efficient they are The average time for each lookup is not tied to the number of elements stored in the table in fact The average time complexity of hash tables and big notation is o of 1 for a search insert and delete That's very fast
53:52
The way a hash table works is that it takes a key input and then runs it through a hash function a hash function Basically just Maps strings to numbers and usually the numbers just correspond to indexes in an array so for example Here are the strings we pass through the hash function and then we get the numbers over here a hash function needs to be consistent so when you run a key through the hash function It always gives the same number and it should map different words to different numbers
54:25
If two words get hashed to the same number This is called a collision you can see in this example John Smith gets hashed to two Lisa Smith gets hashed to what was ero 1 Sam go for and then Sandra Dee also gets hashed to 2 So this is a collision because both of these names once they run through the hash function Get turned into the same number or the same index for the array One way to handle collisions is just to store both key value pairs at that index
54:57
then upon lookup of either you would have to iterate through the bucket of items to find the key you are looking for this could Take a little extra time because of the iteration so here's another example where it's showing that the names are going through the hash function and then it's showing basically the Information that's being stored in the bucket So this would be the array index and then in that array index or the bucket, we would store the phone number
55:25
So this would be like a phone book the numerical value from the hash function is then you as the index to store that Information then if you try to access the same key again The hashing function will process the key and return the same numerical result Which will then be used to look up the associate value which just means that once you store all these things in the array Once you want to get the number again You would just pass in the key John Smith into the hash function
55:55
It would give you the exact same array index, too And then you would get the information returned to you, which is the phone number now You will probably never have to implement hash tables yourself because most languages Including Java Script already have them built-in in JavaScript. Hash tables are usually used to implement objects However, it can be helpful to see how they are implemented just to gain a better understanding
56:20
So I'm going to show you the code for a hash table so you can see how they work First of all, we have our hash function Where we're gonna pass in the string that we want to hash and then the Max Max is the number of buckets that we're using in our hash table to store values we're gonna start with hash being zero and We are going to for each character in the string string that link for as long as the string is We are going to add the care code of each character
56:52
Each string character has a numerical value associated with it so basically We're just adding up the character codes for each character in the string and putting into the hash Now instead of returning the hash we're gonna return hash modulus max That just means we are going to divide by the number of buckets and then return the remainder So if we had 5 buckets if we're divided by 5 The remainder is either going to be 0 1 2 3 or 4 and then that would be the index that we're going to place
57:25
The item into the array now This is a very simple hash function just for an example, but they can get much more complicated now Let's go into the hash table function so in the hash table function, we're gonna have our storage array which is where we're going to store all the data, we're putting into it and The storage limit now, this is the number of buckets in the array at first I'm just gonna show you with just four different buckets
57:52
But normally actually this number will be much higher and this is just a utility function just for this example So I can easily Print all the items in this storage array I can easily log them So here's where the real methods come in for the hash table if we want to add some information So first you're gonna pass in a key and a value We're gonna figure out the index of the array by running it through the hash function
58:17
so we create this hash function where we're gonna pass in the key and the storage limit the number of buckets that we're gonna have in our hash table and that's going to return an Index that we went over before if there's nothing in that index in the storage array if it's undefined We're just going to set that index to be this key value pair array Else if it's not undefined that means there's already something in that bucket
58:44
So first, we're gonna set insert it to false and then we're gonna go through each index to see if the key already exists if the key already exists, we're gonna set the new value here and
58:58
Set insert true if the key does not exist, then insert is still gonna be equal to false So we're going to push in the new item. That's where we'll get multiple Entries into one bucket. So the next thing is if we're going to remove an item from the hash table So if we're gonna remove you're just passing the key of what you want to remove and now we're gonna look up the index by
59:24
passing it into the hash function if the index that length equals one, that means there's only gonna be one item in that bucket and the item in that bucket Equals the key that you passed in then you can just delete that index. You can just sleep that item But if it does not equal one that means there's probably a few different items at that index and we want to only Delete the item associated with that key. So we're going to go through each item in that bucket or in the index and
59:57
If the key equals the key we passed in then we can delete that item The zero index is the key. The one index is the value So let's go how we would look up an item again we're gonna set the index using our hash function with the key that we passed in and the storage limit if the index there is Undefined we just return undefined. It's not the item is not in the hash table else We're going to go through each element in that bucket
1:00:26
If the element equals the key then we can return that element. So let's look up a few examples first I'm going to show you an example of the hash function Here if we run that to me three and every time I run that you'll see in the console three three three Every time I put Bo it's gonna put three, but if I put a different name here and I run that You can see on the console. It's gonna be five and now every time I run two has to be five so with this hash function
1:00:54
It's going to always be a number between zero and nine because we're passing in ten as the number of buckets So now let's actually see the hash table So here we're gonna create a new hash table called hte for hash table We're gonna add Bo who's a person add find out who's a dog retsu the dinosaur tux who's a penguin? Then we're gonna look up tux and then we're just gonna print the entire thing. So, let's see what happens in the console
1:01:24
So we saw that tux is a penguin now, let me bring this over a little bit It's going to show our entire hash table now Normally, you're never gonna print out the hash table like I did to the console But I just did that just for learning purposes if you remember up here
1:01:44
We have the storage limit set at four so we only have four buckets the reason why I had it set at four is so we will see what it looks like when there's a Collision when there's two things in one bucket just by coincidence The first buck is undefined that means none of these words Hashed to zero and then if we look at the second bucket, that's right here There's actually two key value pair in the second bucket so both bow and tux both gave
1:02:15
One when it went through the hash function and then you can see in this bucket right here We just have one item and then this bucket right here. We just have one item So when we pass in reps to the hash function, we got three returned But if we go up here and we change the number of buckets to something like 14 now I'm gonna try running that again If you look right here now, there's a lot more undefined because most of the buckets are now empty but this bucket only has one item that
1:02:47
Book has one item and then the last two books have one item and there are no collisions now each bucket only has one item Now this has just been a pretty simple example of a hash table Implementation but it's enough to give you a basic idea of the hash table
1:03:07
A linked list is a common data structure where elements are stored in a node the node contains two key pieces of information The element itself and reference to the next node So in this example the element here will be one and then here's the reference to the next note This arrows point to the two this two is the element we're storing the information To and the way this length linking to the next node, like arrays linked lists can be used to implement many other data structures
1:03:37
linked lists have some advantages and disadvantages when compared to arrays Traditionally arrays are just have a fixed size and linked lists have dynamic size so you can just keep adding Links and you don't have to do anything differently JavaScript kind of hides some of this but when you create an array can only be a fixed size also arrays have pretty inefficient insertions and deletions while linked lists are very efficient search terms and deletions a
1:04:03
Benefit to arrays are the random access which means you can say you want something at index five and you can instantly get the thing At index five however with linked lists if you want something at index five You have to go through every element in the linked list to get to index five and then for arrays they may result on much memory waste to make up for the Fact that arrays can only only be made at a fixed size
1:04:26
Sometimes they will be created a lot bigger than what you really need to make sure you have enough room for everything However in a linked list because of the dynamic size There is no wasted memory and then we have really fast sequential access for raised and slow for linked lists So every linked list is gonna have a head so we have this head pointer here that points to the first node And then it's also going to have a size. So that's just the amount of node
1:04:53
So in this example here the size will be three and you can see each node points the next node in the last node it Just points to null because there is no next node So if you look at the code over here we start with the head of null because we don't have a head yet and the length is going to be zero and The linked list is made up of nodes So here's how we're going to create a node we pass in an element and this Telma is set to element this Next is set to null
1:05:20
So this not element in the picture is the info and this that next in the picture is the link so it starts off Just like the last element where the link is point to null next is point to null then we just have a few simple functions this step size just returns the length and this the head just returns the head and Here's the add function whatever we're going to pass in to the linked list is going to be the element So you're gonna add the element and then we're gonna create a new node
1:05:52
With that element. So after you pass in the element and it creates this new node The element of the node is set to the element you passed in but the next of the node is set to null
1:06:05
So if head equals null that means there are no nodes in the linked list yet so we just set the head to equal the node and at that point there would just be one node in the linked list and The head would be pointed that first node else. That means there's more than one element list We're gonna set the current node to equal the head and let's add a var in front of here So this just means that we're gonna start at the head node
1:06:31
Which you always have to do whenever you're doing anything to a linked list You start the beginning and then you to go through each item in the list while current node dot next that means While there is a current door next while current node that next does not equal null You can see at the end. Remember the link equals current node next So at the end it equals null So before the end of the list the current node next which would be the link does not equal Null it equals the next node
1:07:00
So this just means while there is a next node current node equals current node next So that's just a way to hop from node to node on the list. Once there is no current node next That means we're at the end of the list the end of the list is where we want to add the element that we're adding Now we'll set current node next to equal the node once we get to the last node in the list We'll set the Curnow dentin X or this link to equal the new node
1:07:31
We added instead of null and we just increment the length
1:07:36
The remove method takes an element and searches a linked list to find and remove the node containing that element so you're passing the element that you want to remove and We always start at the head current node equals head And then we also need to know the previous node when you're gonna remove something So if the current node that element equals element if current node element equals element Well, that just means that the head node is the element
1:08:03
We're trying to remove so if we're trying to remove the head node We just have to set the head to current node next So the head pointer will be pointing to the next node if the head node is not the node We're looking for we go to the else So else while current node to element is not equal known element basically while the node Ron does not equal the node We're searching for Previous node is gonna equal the current node Like I said, we have to keep track to the previous node
1:08:31
And then the current node is going to equal current node next It just means we're gonna keep going through this while loop and keep jumping to the next Node on the list until we find the node we're looking for let's let's say if this second note on this example here We're minus that previous node that next to equal current node dot next if we're trying to remove this second node We're gonna step previous node next. So the previous node that next would be the first node
1:08:59
So there'll be the link the link is now going to not point to the current node the link is going to point to the current node dot next we would skip over that node and point to the current node that next right here and that's how a node would be deleted from the linked list and then we just decrement the link now here's another quick function is empty return length equals equals equals 0, so if filling T equals zero We're going to return true if it doesn't equal zero
1:09:27
We're gonna return false and you may want to know the index of a specific element So we're just gonna have to hop from node to node until we find that element and then return index so the current node is gonna equal head start at the beginning and next is gonna start at negative one and So Wow current? No, that means while there is a current node while it's not null. We're gonna increment the index
1:09:47
So at this point we start the beginning we've incremented the index. So where the index is now is zero So if current node that element equals element returned index So if the first element which would be this info equals what we passed in up here, we're gonna return the index So if instead of the head node we're gonna return the index zero if not current node equals current node next and then when we continue doing this while loop and just hop from node to node and then then
1:10:15
We're gonna eventually be able to return the index as we keep adding one to the index for every time we do the while loop and if we go through all the whole while loop and don't find Anything we're gonna return negative one that just means the element is not in the linked list So we just found the index of an element now going to find the element at an index. That's just the opposite You're passing an index number and you're going to return the element So we have current node equals head
1:10:42
Count equals zero and here's the wall loop here while count is less than index. That means we haven't gotten to the index We're searching for increment count and current node equals current note that next so that means we hop to the next node so we're gonna keep going through every node in the list until Count is not less than index. That means count equals index So we've reached the right index so we can just return current node that element
1:11:10
Yep, you're gonna pass in the index and elements and add Remember, we you always add to the end of the linked list But an add at you can add in the middle of the list So just like a ID we're gonna create a new node with the element We pass them and the current node is gonna equal head. We always start at the beginning We need to keep track to the previous node, and the current index is gonna equal zero
1:11:31
So if index is more than length that means we've passing an index that's way bigger than the actual length of the linked list so we cannot add at the index when we return false if Index equals zero that means we're trying to add the element to the head node. So we'll set node n or no It is a note that we just passed in so the next element is now gonna be the current node Which would be the current head node? And then we just set the head to equal the node that we passed in else
1:12:01
We don't want the index to be the head node while current index is less than index We're gonna go through each index until we find the correct index so cray index increment We're gonna set the previous node to equal the current node. So we want to keep track of the previous node The current node is gonna equal current node. Next we're gonna keep going through this while loop until we find the correct node so if we want to add a node as
1:12:26
Index one or the second node on the list once we get to that index We're gonna set node X equal to current node So or no debt next is the node we passed in and we're gonna set that to equal the current node Which would be this index right here? then we have to set previous node that next to equals and note that we're passing in and then we just increment the length and the last function I'm gonna talk about is remove it now remove it and a net are
1:12:56
Very similar a lot of the lines are the same except we're not gonna create a new node The kernel is gonna be the head. We need a previous node the current index is gonna be zero here is a slightly different thing if the index is less than zero or If the index is more than or equal at length return null so we cannot remove a negative index and we cannot remove an Index greater than the length of the list if index equals zero, we're trying to remove the head node
1:13:22
So we just set the head node to equal the current node next So instead of the head pointer point to this node right here that head pointer is going to point to the next node right here else this part is just like the ad and we're just going to keep going through each element on the list and once we find The element we want to remove like let's say we're removing this second element at index one
1:13:45
We're going to set previous node next to equal current node. Next. We're going to set the previous node next or this link is going to point to whatever was in the link to the current node, or So this link is going to point to now this note right here and we're gonna completely take out this one and then we're gonna do length - - and Return the note that we're removing and now we're just going to quickly show an example of using the linked list We're going to call the linked list
1:14:14
Conga because a linked list is kind of like a conga line and let me bring up the console So we're gonna create this new linked list. We're gonna add some items kitten puppy dog catfish. We're gonna show the size We're gonna remove the third item on the list. So we'll run them and see we're gonna remove cat now let's copy this we're gonna do element at
1:14:38
Then we'll try index app and for the element we're gonna put puppy look I mean index of so we remove cat Now we check the new element three, which is gonna be fish and the index of puppy is gonna be one Kitchen would be zero copy is one and the size is four. Well, that's the linked list
1:15:02
a try That's how this is pronounced right here A try sometimes called a prefix tree is a special type of tree used to store Associative data structures a try stores data in steps each step is a node in the try this is often used to store words since there are a finit number of letters that can be put together to make a string a Possible use case would be to validate that a word is in a dictionary Each step or node would represent one letter of a word
1:15:33
So if you can see over here, this is an example of a try This word right here will be B a ll ball the steps begin to branch off when the order of the letters Diverged from the other words in the try or when a word ends. So if you get the word be a ll But you also have be a T bat So the first two letters ba are part of the word ball and part of the word bat and then down here you have doll
1:16:05
do dork and Dorm, if you look at the red stars, that just means it's at the end of the word So the word do you can see it's the end of a word? Even though there are still letters in other words after the O So let's look at the information in each node from the code here Each node is going to have a keys which is just a new map And this is the es6 map structure. It's kind of like an object It has just key value pairs and in the in these keys the key value pairs are kind of like
1:16:42
the name of a folder in a folder in a directory structure so if you can imagine these all folders in the root node, there is The keys map that's going to have B D and s and each of the key value pairs are the B The name of this folder is the key in the map and the value of that key is The folder be the actual contents of the folder B. And so that D is Key in the map and the value the key value pair The value is going to be the actual contents of the folder
1:17:21
Each snows gonna have a list of keys, which is just a list of all the other letters That are inside that folder or in that inside that note and then we're gonna have an end data That just means is this the end letter in a word? so in this picture all of The node with a star have end Set to true and all the nodes without a star have end set to false now We just have a setter function set end and is equal to true is end So it's just gonna return true or false if it's the end of the word
1:17:55
So now that we've looked at each node in the try Let's look at how the code to the actual try set up So we're going to only going to have three functions We're gonna have add to add a word to a try we're gonna have is word to see if a word is a word in the try and then Print this is more of kind of like a helper function just to print all the words that are in the try So before I go through the code let me show you how it be used what we're gonna create a new try and
1:18:26
Then we'll get you can add the words like this And then after you add all these words and these are the same words are in this picture over here You can check if it is a word is dollar word Well doll is gonna be word is daughter word See we have the word do R in the picture But there's no star on our because door is not a an actual word even though those letters are in the try and then Dorf
1:18:53
Well check do R and then there's no F so that's not a word and you can just print the whole thing like that So if I run that you're gonna see in the console down here True false false and then you can see the whole list here. So let's go back up to here first of all, we're gonna create the root node a new node and Then let's look at the ad function. So this ad function is a recursive function So when you call it for the first time, you're gonna put the entire word
1:19:20
You want to add to the try and that becomes the input and theer says note equals this dot root That means if you pass in a note it will use that node But if you don't pass in a node, it will just use this that root as the default node So if input that length equals equals zero That means if we're at the end of the word that we passed in We're just going to do no dot set end and then return and we're done with the add function
1:19:52
Else if that means if there's more than zero letters that we've passed into this add function We're not at the end of the word So first, we're going to check if there's already a node with that letter that we're looking at so this is if not No dot keys that has so let's say we're in the root node no duck keys is a list of all the letters of that root note points to so if it does not Has if it does not have a letter input zero would just mean the first
1:20:25
character of the string we passed in so if we pass in ball it would this is just saying if There is not a node with the letter B here Then we are going to create a node with the letter B Know that keys that set set is how we're going to create a new key value pair in the keys map We're going to set it with the key to be the letter input zero So input was you don't bracket just means the first letter of the input would pass in
1:20:57
so if we pass in ball the first letter to me B and so remember each key value pair is Then Nate is kind of like the name of a folder and the contents of the folder The name of the folder is B the contents of the folder are a new node. So then this is where it becomes recursive We're gonna call this dot add and we're gonna pass in inputs abstract one which takes the input and Takes every letter after the first letter and passes it into the add function again So if the word was ball
1:21:32
every letter after The first letter is a ll so we're gonna just pass in the letters all and we're also gonna pass in a node Before remember twister there with the root node. Now we're gonna pass in this node, which is also the node. We just Created here. So we're gonna set a node with the letter B that'll be the input 0 so now we're gonna get the node with the Input 0 that's the first character. So now we're gonna run the add function but instead of after being at the root node
1:22:04
We're gonna be at the the node B, and then the else is just if there is already a letter by that name So remember here we added a node with the letter B, but if there already is a letter B like for instance let's say we already have the word doll and We're gonna add the word dork if we're at the D and the word doll is already in the Tri and we want to add dork Well O is already going to be in the Tri So if I was already in the Tri we're not going to create the own ode
1:22:35
We're just going to add the the new sub string which in this case would be so our k we're gonna add that to The nodes that know that keys that get input 0 which would be the O Node, so we're gonna keep running through that until we've added the word to the Tri and then down here We're gonna check if the word is in the Tri. So this is where the Tri really performs You can check if a word is in the dictionary
1:23:05
Much quicker in the Tri than other data structures because we don't have to check through every word We're just checking one letter at a time. So we're passing in the word we're setting the node to the root node at first and Then this is the loop that we're gonna keep running through until we find the word so while we're dot linked as more than one while there's more characters to search in the the word that we passed in so if
1:23:31
Not no duckies that has word. This is saying we're gonna check the first character in the word So let's say we're on the root node So if there is no key with the first character in the word, like let's say we passed a word tree Well, there's no T. There's no key with the letter T here so we can return false We quickly determined that that word three is not in This try because there's no word that starts with T else that just means there must be a word that starts with that letter
1:24:03
So let's say we're looking for the word it's end Well, if it does have the letter S then we're going to do these two things We're gonna set the note remember, which we used to be the root note But now we're gonna set the node to the the note s because if we're gonna look for the word descend We're sorting the note to the S note and we're gonna change the word into the word - the first character So now we're just gonna be looking for the word end instead of sindh so I'm gonna go back up here now
1:24:34
We're we're gonna keep running through this now. We're on the S note, but we're looking for the word end And yeah we'll find the e we'll find the end and we'll find the D and now we go to this very last line if note that key that has word Which would just be a single letter because remember we keep taking the letters off and so if it has the last letter of the word that we passed in and It is the end so is end
1:25:02
Then we're gonna return true that word is in the Tri else. We're gonna return false. Yeah So this last one was just the the print function that's kind of a helper function And so we're gonna create an array of every word But right now it's just gonna be empty Then when a search we're gonna pass in or a search if we don't pass anything here It's gonna set this is a root node. Actually that we don't even need this Let me just run that just to see if it does the same thing in the console. Yep
1:25:31
We don't even need to set the note to the root node Because when we first call the search command down here, we already passed in this dot root So we're just gonna pass in a node and we're gonna pass in a string Here if no duck keys. That size does not equal zero That means they're still still more letters to look through So for each letters and the keys here, let's say we're on the root node So the letters in the key would be B D and s so for each of those letters
1:25:59
We're going to run the search command again, and then we're gonna pay Sen note keys that get letter that means we're going to pass in the the node at that letter so we would pass in the B node and then we're going to Add that letter to the string at the beginning the string would be empty So do string that can concatenate one letter. We're going to add the letter B and basically since this is recursive It's going to keep going and keep adding each letter so we keep
1:26:30
Concannon each letter to the string Until it's formed the whole word and then see if node that is end if we've gone to the last node in the word It's going to do word dot push string. So that's our word to raid if we've gone to the last letter in the word we're gonna push the word onto the words array no else that's else to this if statement if the Note keys that size Does equal zero then we're at the last letter of a branch if string that length is is more than zero
1:27:01
We're just gonna push that word on to the words array or else Returned undefined and here's where we call that a search function for the first time So here's the search function and then we call for the first time and this is gonna go over and over until it gets every word in the try if Words that length is more than zero It's gonna return that where the words the words array or it's gonna return all if there's no words in the array So that's a try
1:27:31
a Binary heap is a partially ordered binary tree which satisfies the heap property It has some similarities to a binary search tree except the order is a little different Each node has at most two child nodes the heap property indicates a specific relationship between the parent and child nodes You may have a max-heap in which all parent nodes are equal than or greater to than the child nodes so you can see the the biggest numbers on top and the smallest numbers are on bottom or
1:28:02
You may have a min heap in which all child nodes are greater than or equal to the parent nodes So the child nodes are the biggest ones and the parent nodes are the smallest ones The order between child nodes on the same level does not matter So you have 10 6 and 12 here here We have 5 6 & 1 You can see that it goes from a small number to a big number to a small number the order doesn't matter if they're on the same level Binary heaps are also complete binary trees
1:28:30
this means that all levels of the tree are fully filled and if the last level is partially filled it is filled from left to Right. So if you see the example down here, so here's level one Then we have level two here level three level three is all the way filled Level four is only partially filled because there's nothing over on the right side here But you can see it's filled from left to right Binary heaps may be implemented as tree structures with nodes that contain left and right
1:28:56
References like what? I showed in my binary search tree video However, heaps are more often implemented as arrays This is possible because of the partial ordering according to the heap property We can just compute the parent-child relationship of the elements. Now. This will make a lot more sense with this diagram here So if you see this array right here, this is the array Representation of this tree right up here. The number 1 is 20 and that's the root
1:29:25
You can see that right up here and then 2 & 3 are the child knows 19 and 17 right here And now I want to pull your attention over to these equations up here so that the left child is going to be I times 2 the right child can be I times 2 plus 1 Let me show you what that means. So if you look at 20 here, which is at index 1 in the array Also, I should point out that there is no index 0 so when you're representing a heap
1:29:54
You're just gonna leave index 0 as null to make the math work out a little better so if we go back to Index 1 well the equation for the left shell is I times 2 so 1 times 2 will be 2 so yeah 19 is the left child and the right child is I times 2 plus 1 So 1 times 2 plus 1 is 3 17. That's the right child. Now. Let's say we go to number 13 here That's index 4 well if we go to the equation I times 2 4 times 2 is 8 so if your index 4 and you go to index 8 11, yep
1:30:31
That's the left child now, we start index 4 and we do the right child equation I times 2 plus 1 that's 9 so if we go to index 9, yep, that's the right child here So that's how you can use these equations to find the left and right child from an array representation You can also figure out the parent so the equation for a parent I divided by 2 if we are on 11 that's index 8 8 divided by 2 is 4 index 4 and this really should be floor
1:31:01
I divided by 2 because you divide the index by 2 and then round down to the nearest whole number For instance 5 divided by 2 is 2 point 5 But if you round out it's 2 and then 2 would be the the index 19 here Also, you can see in this diagram that the last index is also the size of the heap size 10 This diagram is a max-heap. I'm going to show you the code for a min heap but in the same file down here, we I also have the code for The max heap down here so you can check the link in the description
1:31:33
So you can review this actual code yourself and you can review the maxi on your own But like I said, we're just gonna review the the men heap right now But before I show you the actual code I want to show you a visual representation of how it works when you're inserting and You're removing items from the heap Those are the main two commands insert and remove and then there's one more I'll show you at the end But let me show you this
1:31:59
Representation here so you can see this is the array representation And I'm going to insert some numbers and you'll see them show up as a tree representation. So, let's see 4 You can see 4 goes at the top. That's the the root node. And now I'm going to put in 6 6 just goes down to the bottom there 8
1:32:20
So as it builds the node one thing to keep in mind is that it's gonna build one Level of the tree at a time I'm gonna put in 10 that's gonna be on the very left side now so far I've been putting them in order but now I'm gonna put in the number 5 here and when I insert the number 5 you're gonna see this it's gonna First go to the end of the array here. You'll see their array which is gonna first appear right down here and Then it's going to move up to the correct position So, let's see that
1:32:59
So then as you see it checks what position to move it up to so I'm going to put in a few other numbers here
1:33:08
See 16 3
1:33:13
Ok, so you see it always puts in at the end of the array or the end of the tree and then it moves it Up to the correct position now I'm going to show one more where I put in one where it's gonna put it put it down here and it's gonna move it all the way up to the top and It's a check one at a time to see if it has to move it up also Another thing would just be removing what when you remove you always just remove the smallest
1:33:38
it's gonna remove what's in index 1 which is always gonna be the smallest and then it's gonna pop the last Node to the first node, and then it's going to sort them. So, let's see how that works
1:33:54
So did you see that so it moved the last node to the first node? And then it has to keep checking and keep moving it down until it gets to the right position. So let's move remove 3
1:34:08
Okay, so now let's go to the code and you can see how that works in the code So before we insert anything You can see that we've created a heap with an array that just has one item and it's the item null at index zero So when we insert something we pass in a number and we're gonna push that number on to the end of the heap So if you pass in the number three, there's going to be index zero is null and next one would be three now if the length of the heap is
1:34:38
More than two that means there's more than one item in the heap if it's less than two There's one or zero items in the heap and that makes things really easy. But let's say it's it's more than two So we're gonna let the index equal heap dot length minus one. So That means we're finding the last index and the heap while heap at that at the last index is less than Heap and then see this equation right here That is the the parent equation
1:35:12
So now we're saying if the last item in the the array which is the item We just inserted right here. If the last time of the array is less than its parent Well if it's less than its parent We're gonna have to move it up because the smallest numbers have to be at the top in the men heap So if the index is more than or equal to one that means if we haven't reached the root node Then we're going to do this now This is es6 destructuring syntax, which just means we are gonna switch the node
1:35:46
We just inserted with the parent node. We're gonna we're gonna switch them. So here is the parent node Here is a node. We just inserted and now we're gonna switch them So the node we just inserted is gonna be first and then the parent node is gonna be next So it's just a way to swap them for more information about the es6 destructuring You can check out my video about that topic so if math math dot floor index divided by two is more than one this just means
1:36:18
If the parent node is not the root node, because remember this is the equation for the parent node Is the index of the root node So if the parent node is more than the root node Then we're gonna set the index to map that floor and X divided by two. That's the parent node Which if you remember up here we just put the number we passed in Into the parent node. So now the index is still gonna refer to the number We just passed in because that number has went into the parent node
1:36:49
And so now we're going to set the index to that node And since this is a while loop or when I keep going through this and we're going to keep switching the the node To its parent node, as long as it is Smaller than the parent node else break. So once it's not smaller than the parent node, we just get out of this while loop and That's the insert so let's go down to Remove it's a little more more code, but it's some similar concepts So we are always going to remove the top node the smallest node
1:37:23
So we're gonna let this smallest equal heap 1 So that just means that the first node in the array is the smallest node. So that's the easy part The hard part is rearranging the array after you've removed that node So if heap that length is more than 2 that just means we have more than one node in in the tree. We're going to Set the first node in the tree, which remember was the smallest node But we're gonna set this to the last node
1:37:52
The last node in the array now gets moved to the first node in the array Now we're gonna heap that splice keep that length minus 1 this just shortens the array by 1 So we just removed the hole the last index of the array completely since we've already moved that to the first Index if heap that length equals 3, that means there's only two numbers in the the tree and that makes things really easy Just if one is bigger than the other then we just switch them. This is the destructuring syntax again
1:38:23
So if the first one is bigger than the second one then we switch it so the second one is bigger than the first one and then we just return the smallest if There are more than two nodes in the array. That's where it gets slightly more complicated So we're just going to set the index to equal 1 we're gonna set the left equal two times I and the right equals two times. I plus one remember that was just that the equations from up above the equations right here
1:38:47
We're just putting him into our formula down here
1:38:52
Now technically you would not need to put this equation here since we know that I equals one You could just put three here You just put four here, but this is just so you know, we're using the equations from above So we're one is the root notes or starting with the runo So while the root note is more than or equal to its left child Or the root note is more than or equal to its right child We're gonna do everything in here. That means we're going to have to
1:39:22
Basically move a down and keep moving it down until we get to the appropriate spot So if the the left node is more than the right node Then we're going to switch the root node with the left node This is the destructuring syntax again, so we're gonna just swap the nodes So for instance, we would be swapping if we're on this node and this node We just swap those two nodes and then we're gonna set the index to the left node
1:39:47
So gonna set the index to be the node that was at the top node, but has now been swapped Else that means the right node is less than the left node. We're gonna switch the node with the right node So we're just gonna swap with the right node. And then we just set the index to be the right node So the the node just moved down a little bit and then we set the index to point to the node that we just pushed Down a little bit and then we have to set the new left and right node
1:40:14
so we would set the left and right no to be the left and right of the the one we just passed down and then if The the left child or the right child equals undefined that means we're at the very bottom of the tree so we can just break out of this while loop and if it's not undefined we just keep going through until we find the place where the node that we're moving down the tree is not
1:40:37
more than equal to the left node and is not more than or equal to the right node else if it's only equals two that Means there should be only one element in the array. So we just cut off the last element else We reach our null that means there were zero elements than the to begin with and then widgets can return the smallest element Which is just the element. We just set up here. The last thing I'm going to talk about is this Now a common use case for the heap data structure is for heap sort
1:41:05
This is one of the most efficient sorting algorithms with average and worst-case performance of o of n log in heap sort works by taking an unsorted array Adding each item in the array into a men heap and then extracting every item out of the man heap into a new array The men heap structure ensures that the new array will contain the original items in least to greatest order So this is the function that you would use to do that heap sort the hard part is
1:41:34
Creating the all the code. We just already went over and this is just gonna use that code so let result equals new array while heap that length is more than one we're gonna do with this that remove so we're gonna remove the element on top of the tree and we're gonna push onto the result and we're going to keep doing that until we've moved removed all Of the smallest elements and push it on to the result and it's going to put the elements in order
1:41:56
Well, that's all I'm going to talk about for heaps feel free to check out this code and create your own heap and and Add some items and remove some items just to see how it works
1:42:10
The graph data structure is not the same as a graph you may have learned about a math class Graphs are collections of things and the relationships or connections between them the data in a graph are called nodes or vertices The connections between the nodes are called edges One example of graphs is a social network where the nodes are you and other people? And the edges are whether two people are friends with each other. There are two major types of graphs directed and undirected
1:42:41
Undirected graphs are graphs without any direction on the edges between nodes directed graphs are graphs with a direction and its edges an
1:42:50
Example of an undirected graph could be a social network The nodes are people and the edges are friendships an example of a directed graph Could be the internet and web page links The nodes are web pages and the directed edges are links to other pages which might not necessarily Point the other way, I'm going to show you three ways to represent a graph The first way is called an adjacency list this representation for a graph
1:43:18
Associates each vertex in the graph with the collection of its neighboring vertices or edges in This image a is connected to B B is connected to a and C and C is connected to B this is how you could show a relationship with texts and Here is how you could show this adjacency list with JavaScript
1:43:41
This is an undirected graph because it does not show the direction of the edges This can also be more simply represented as an array where the nodes just have numbers rather than string labels
1:43:55
Another way to represent a graph is to put it in an adjacency matrix an adjacency matrix is a two-dimensional array where each nested array has the same number of Elements as the outer array so it's basically a matrix of numbers where the numbers represent the edges Zeroes means there is no edge or relationship and ones means there is a relationship This table shows an adjacency matrix to represent You can see that the labels for the nodes are on the top and left now. Here's a JavaScript
1:44:31
representation of the same thing
1:44:34
Unlike an adjacency list each row of the matrix has to have the same number of elements as nodes in the graph here we have a 3 by 3 matrix, which means we have 3 nodes in our graph an
1:44:47
Adjacency matrix can be used to represent a directed graph Here's a graph for the second node has an edge pointing toward the first node And then the third node has an edge pointing to the second node notice how the numbers in the array change There are only ones where a node is pointing toward another node. And since there are only two Points, there are only two nodes
1:45:12
The final way I will show to represent a graph is an incidence matrix
1:45:18
Like the adjacency matrix an incidence matrix is a two-dimensional array, however the rows and columns means something else here the adjacency matrix use both rows and columns to represent nodes and Incidence matrix uses roads rose to represent nodes in the columns to represent edges This means that we can have an uneven number of rows and columns
1:45:42
Each column will represent a unique edge Also, each edge connects two nodes to show that there is edge between two nodes You will put a 1 in the two rows of a particular column as you can see in the diagram Edge one is connected to nodes a and B Now look at the column for edge 1 in the incidence matrix table You will see a 1 in both the a row and the B row this shows the edge 1 connects to nodes a and B here is a directed graph for a directed graph use 1 for an edge leaving a particular node and
1:46:15
Negative 1 for an edge entering a node and here Is a JavaScript implementation of the incidence matrix?
1:46:24
Graphs can also have weights on their edges so far We have unweighted edges where just the presence and lack of edges binary 0 or 1 you can have different weights depending on your application a Different way is represented as a number greater than one Well now, you know about different types of graphs and how to represent them in JavaScript
1:46:48
I'm gonna talk about how to find the distances between two nodes in a graph This is one of the main uses of graphs and is called graph traversal
1:46:57
traversal algorithms are algorithms used to traverse or visit nodes in a graph The main types of traversal algorithms are breadth-first search and depth-first search in this video I will be showing how to implement breadth-first search in JavaScript as You can see the algorithm starts at one node first visits all its neighbors that are one edge away Then goes on to visiting each of their neighbors. The point is to determine how close nodes are to a root node
1:47:28
There are different ways to implement breadth-first search in This version you pass in an adjacency matrix graph and the index of the root node
1:47:39
remember an adjacency matrix each Nested array in the matrix shows which nodes in the graph are connected to the node at that index for example this array is at index 0 so it shows which nodes that node 0 is connected to if It is connected to a node there is a 1 at that index. But if it is not connected there's a 0 at that index Before I go through the code, let's see it in action So here is a graphical representation of this adjacency graph
1:48:14
Check out my previous graph video to see how this adjacency graph goes into this graph
1:48:20
so we ran the breadth-first search function we passed in this graph up here and Then we pass then the number 1 so that means we're trying to find out How far away every node is from the first node? So you can see this graphical representation of the exact same graph And if you see the first node right here, that's to know we passed in to the the breadth-first search function We're gonna see how far away each node is so you can see right here. It shows how far away is
1:48:52
So node 0 is 2 nodes away see because of the direction of the graph. We can't just go straight across as 0 First from one we good at to then we go to zero that's two nodes away one The the note itself is always zero notes away. And then the second note is one note away Just one third note is three nodes away. See if first you have to start at one then you go to 2 then 0 then three, so that's three hops and
1:49:21
Four is infinity because when you're not from the first note, it's impossible to get to the fourth node Because the fourth note only points back to the first node
1:49:33
This function will output an object of key value pairs Where a key is the node and the value is its distance from the root
1:49:43
This object will be used to store the distances to the root node
1:49:49
We will start all the distances at infinity which in this version of breadth-first search Indicates that a node is not reachable from the start node
1:50:01
Here the distance the root node from the root node is set to zero instead of infinity we are going to create a simple queue to keep track of nodes to visit and The purpose of this variable is to keep track of the current node that we are traversing
1:50:20
Now we will start a while loop to keep traversing nodes until there are no more nodes in the queue to traverse
1:50:28
We'll start the loop by popping off a node from the queue to traverse Which at the beginning is the root node?
1:50:38
Here we get all the nodes connected to the current node Remember each index of the graft is an array that shows what nodes are connected to the root node
1:50:50
Associated with that index. So in this example we are first looking at node 1 at node 1 the array show is that it is connected to nodes 0 & 2
1:51:02
Now we set the neighbor index variable to an empty array This will keep track of a list of nodes that are connected to the current node
1:51:13
This lime gets the first note connected to the current node when it says Index of one this finds the first connected node Because the number one in our array means that the node is connected to another node at that index If there is no node with an index of one the index variable will be set to negative one So while index does not equal negative one, push the index onto our list of neighbors This line searches for the next connected node
1:51:46
We look for the next one in the array starting after the previous one we found that's what this plus one means Now that we know all the nodes connected to the current node. We loop through these connecting nodes and get the distance If the value in the nodes Lin array at the index of the neighbor from the neighbor index array equals infinity That means we haven't set the distance of that node yet
1:52:15
So we will set now we are going to set it to the value of the the nodes length array for the current node plus 1 Then we'll push that neighbor to the queue so the next time we go through the while loop, we'll check the neighbors of that node to This for loop is the most complicated part of this and you may have to read through a couple times to completely understand it at the end we returned the nodes length array and
1:52:45
That's breadth-first search of a graph. Thanks for watching. My name is beau Carnes Don't forget to subscribe and remember use your code for good
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat