Skip to main content
Loading Explore guides…
Data Structures · Acedra
Home
Explore
Computer Science
Data Structures
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
465 segments
Copy
Hide video
0:00
This course will teach you data structures. That means you'll learn about arrays, heaps, stacks, queues, linked lists, binary trees, all of those topics that fall into the data structures category are covered in this course, and they're covered in a very practical way. I don't get into every tiny little nuance detail. I cover the important topics that you need to understand for real world use, whether that be passing your computer science course or getting ready
0:27
for technical interviews, or preparing to dive into something like LeetCode. That's how this course was designed. And you'll notice that this is actually 11 smaller videos that are all combined together for your convenience. That came from a prior course of mine that was premium that you did have to pay money for. That course has since been discontinued, so I'm slowly going to be releasing some of that content onto YouTube. And this is the first example of that.
0:49
Now with that in mind, I know that a lot of you watching this course are doing so because you're preparing for technical interviews. Maybe you've never learned this topic before. What? You're getting back into it because you want to land a new developer job. Now, if that's you and you want assistance with this in a more premium, hands on one on one way, consider applying for my dev launch program. You can see a link to it in the description.
1:10
In that program, I work one on one with developers as well as with other experienced software engineers to help you land a job in today's difficult market. We have a large emphasis on interview preparation, including running through mock interviews, giving you real evaluation and feedback, as well as working with you one on one to create a custom plan and roadmap for what actually makes sense for the highest leverage activities you can do to land a job.
1:34
the price of that program will be increasing as soon as Black Friday is over. So if you do want to join, now is the time to get in. Anyways, that's it for this. I hope that you enjoy the video. Let's get into it. And just one last thing before I forget. In case you are not familiar with time complexity analysis, I'll put a video right here and linked in the description down below that you can watch to familiarize yourself before we get into the content. Okay, now let's dive in. Hello everybody,
1:59
and welcome to a new section in this course where we will be discussing data structures. Now before we get into this first video where I'm going to talk to you about the array data structure, I want to give you a quick primer on what data structures are. So really data structures are a way for us to store, organize and manipulate data. Now data structures are not specific to one programing language. They can be implemented in many different ways and can exist in really any language.
2:25
These are more theoretical concepts and ways that we can go about manipulating our data. They can provide more efficient operations based on what it is that we're trying to do. So in one program, we may use data structure A because it's faster for that specific use case. And another program we use data structure B because we have a different set of uses. Now again that's going to be very vague and kind of hard to understand right now. But as I start going through these different data structures,
2:51
you'll start to see how they can benefit us depending on the type of code that we're writing. So let me give you a quick kind of overview of the different data structures that we have. I'll give you kind of a high level explanation. And then we'll get into arrays and then move into some more complicated ones. So first of all, I just want to say that data structures are not the same thing as data types okay. So our data types are kind of like normal pieces of data like an integer
3:17
a boolean a string. These are all the data types. And these data types will be different across different programing languages. Data structures are typically storing those types that you just saw. So we might have an array. And that array is storing say a number or storing a string okay. So we have data structures. Now our data structures are split into two categories. We have linear structures and then non linear structures. Now I apologize for the horrible handwriting.
3:46
You don't really need to see everything that I'm writing here. I'm just trying to give you some visuals here. So we have linear and non-linear and these are all kind of in the data structures category. Now for our linear data structures we have
3:58
an array. We have a linked list. And we have a stack as well as a queue. Okay. So these are kind of the four main linear data structures that we're going to have a look at. Now for our non-linear data structures. We have trees. We have graphs. Let's spell that correctly. And we have something known as trees. Now these are a bit more complicated. And we're not going to be looking at trees in this course. Okay. So again linear this means we kind of store
4:31
in a straight line and non-linear as it kind of defines here. We don't store in a straight line. In some instances it's going to be a lot better for us to use a non-linear data structure. In other instances, we want to use a linear structure. Again, really depends on what we're trying to do. So let's begin this video now by looking at the array data structure which is a linear data structure. So obviously we've already seen arrays. So a lot of this you're going to know already.
4:54
But I'm going to talk to you more about the implementation of arrays and the time complexity on different operations related to them. So let's draw out a basic array.
5:05
So an array is really an ordered collection of elements okay. In our arrays we have different indices. So index 012 and three. And then we have some values that we could store inside of our array. Now what I want to talk to you about here is first of all the different types of arrays that we have. And then what happens when we do things like add values to our arrays, initialize arrays, remove values, etc.. So when we're talking about arrays we have two different types.
5:34
We have a fixed sized array and we have a dynamic sized array. And this really applies to all of our different data structures. We can have a fixed size or a dynamic size. You can also refer to this as a static size. Now a fixed sized array or any fixed size data structure is something that cannot change its size. That means that we define the size of it when we initialize or create that structure, and we can't expand that any further,
6:02
whereas a dynamically sized array or structure can increase or decrease its size based on the number of elements that we have. Now, so far in JavaScript, we've seen dynamic arrays. We can push elements. We can pop elements, and we don't have to worry about the space inside of the array. But in a lot of programing languages, you have both fixed and dynamic arrays. And they have different performance impacts. So we're going to start by talking about a fixed array.
6:31
So let me just clear everything on the screen here.
6:34
So when we have a fixed sized array we actually need to decide the number of slots or the size of the array when we initialize it. So we might create an array of size. Let's not do ten because it's going to be quite large. Let's do a size four. So if we create an array of size four then we're going to create four empty slots in memory. And our computers Ram where we can have different values. Now these values can be initialized at really anything that we want.
6:59
But typically they'll be initialized at something like zero or undefined or null or false depending on the type that we're storing inside of our array. So we have these four different slots and we have our indices. And now the first thing to talk about is how long it takes to initialize this array. So when I create a fixed sized array this is a big O of n time operation. That's because if I have four elements which is size my array, I need four operations
7:26
to initialize or allocate each of these individual memory slots. And when I talk about memory slots I'm talking about my computer's Ram, which is where our program lives. And we'll talk about that more in just a minute. Okay. So it takes big O of n time to initialize a fixed sized array. Now what about accessing or changing different elements inside of our range. That's really the main thing we do, right, is kind of access them or change the values.
7:50
Well, in order to understand how long that takes, we actually need to quickly look at what happens in our computer's memory when we create an array. So on the right side of my screen this will kind of represent Ram okay. Random access memory, which is where we store all of our different kind of components of our programs, all the different pieces of data. So when we initialize an array, what happens is each one of these slots are actually addressed in memory.
8:15
Now I won't go through what the address actually looks like, but we'll just do something like 0X10X2, 0X3 and 0X4. Now that means that in our computer's memory we have a slot. Okay. The slots have an address and that address stores a specific value. Those values again are the what we have inside of the array. So we might have B slot here of zero x1 storing the value zero zero x2. Storing the value 00X30 and zero x4 storing zero as well. Now what happens when I initialize this array is
8:50
obviously I create these different slots. I allocate them in memory and then I store a reference here to this first slot. Now having the reference to this slot allows me actually to access each of the elements inside of my array in constant time. Now, the reason I can access elements in my array in constant time is because I can use the index for those elements. So let's say I have slot zero x1, and I know that this is the slot for my first array element.
9:18
And I want to access something like index three. Well, if I want to access index three all I have to do is add three to the slot here because my slots are going to be going in order, and that's then going to give me the slot of zero x4. And then I can go directly to that address in memory and find what's inside of it. Now I can either change what's inside of it or just view it whatever I want to do there, but I have access to it in constant time.
9:45
That means that I don't actually need to go and loop through each of these individual slots to get to a further slot in my array. It doesn't matter what index I'm accessing. If I have access to where my array exists inside of memory, I can simply add to where that memory address location is, and then find the next memory address location for the index I'm trying to access. I'm not sure if that makes a ton of sense, but that's why you were able to access
10:11
elements inside of your array in constant time, because you can do essentially an address lookup to find that. Now, in case this is a bit confusing, whenever we're dealing with variables or any data structures in our program, what we're doing is we're interacting with memory. Now we don't have to do that ourself. The computer's doing that on our behalf. But you should kind of understand that what's going on behind the scenes is you're looking for some specific address in your computer's Ram,
10:37
and then you're either writing to that address where you're reading from that address. So if we want to access something, we need to know the address. And to find the address within array, we simply add to whatever the first memory address location is. It might work a little bit differently than that, but this is the general premise. And then that will give us the next slot or the slot that we want to be using to access our index, or to access the value that exists at that index.
11:00
So it doesn't matter how large our array is, accessing an element always happens in big O of one or constant time. Okay, so that is the basics on index access. All right. So now that we've had a look at that, let's see what happens when we try to insert, delete, append and pop elements from R. Right now I'm just going to remove my computer's memory space here because I don't want to confuse any of us. We kind of know what is happening now behind the scenes. We don't need to look at that anymore.
11:28
So let's say I want to insert an element here in between index one and index two. Well, first of all, let's just change some of these values here. So it's a little bit easier to read this. Okay. So let's change this like 3456. Okay. So I want to insert an element here. First thing we need to understand is since we're using a fixed sized array, if we insert an element we're going to lose access to some of the other data that we have. That's because we only have four slots here in memory.
11:54
We can't create any more in the fixed size. So if we want to insert a new element we're going to have to remove a different element. And I'm also going to have to kind of push or change the indices of other elements to get this element to go inside. So what I need to do here, if I want to insert in this position is the following. Well index zero and index one will stay unchanged. I'm then going to insert my new element. Let's say my new element is zero.
12:18
That's the element that I wanted to insert okay. Then what I need to do is I need to essentially push these other elements or shift them over to the right inside of my array. So right now is zero is in the position where index five would have been. So actually before I can even put the zero here, I need to first take this element five. And I need to put it in the position where the next element is in my array. And I actually need to do this
12:45
from the back of the array to ensure I don't lose any data. So what I do here is I first take six and I remove this from the array. That means that I'm pretty much just deleting its value. So six kind of comes outside here. And since there's no slot for six it essentially gets deleted. Then I take five and I move five over to the right. So now five exists at index three. Then what I'm doing is inserting the new element here, which is element zero in the position where element five was okay.
13:14
So that means that our new array now looks like this 3405. So even though yeah, you can imagine I'm kind of inserting a new element here. Really what I'm doing is changing the elements that come after where I'm inserting this element. And that means that this operation here is going to take big O of N time. Now, the reason this takes big O of N time is because we could be inserting at any position in the array if we insert at the last position in the array. This takes constant time
13:42
because we just need to change one element to be whatever the inserted element is. However, if we insert at the beginning of the array, we need to move every single element over to the next box before we can insert this element inside. So doing an insertion inside of an array takes big O of n time. Okay.
14:04
Now the exact same thing applies if we want to do a deletion. All right. So let's say we want to delete the first element here from our right. So actually let's change the color here. Let's say I want to delete this element right here. Well if I just remove this element or I change this to be null or something like that, then what happens is I now have kind of an empty index here. And then I have index one, two and three. Typically that's not what I want.
14:30
Typically what I want to happen is to remove this box and then have this be index zero, this be index one and this be index two. If that's the case then this operation is going to take big O of N time again because of what I need to do. So let's kind of write this in here. So if I want to delete the element here in this box, first of all I can kind of clear the element from here. And then I need to move element four over here. So I kind of write element four there and delete it from this box.
14:56
Then I need to write element five here. Then I need to write element six here. And then this is going to be no okay. Or just like an empty box. We still have it because we have a fixed size array. So this still exists in our computer's memory. But we've kind of removed the value that existed inside of it. So now our ray has changed to be 456 at index zero one and two. And that's what happens when we deleted the first element okay.
15:22
So if we want to do a deletion again that's going to be big O of N time. Now the only time there's an exception to this. Let me just clear all of this on the screen here is when we're deleting or adding elements at the end of our array. And then additionally if I want to delete an element I can just remove it from the end. And that will happen in constant time because there's no changes that I need to make to the other elements. Okay. So hopefully that makes a bit of sense.
15:45
But this is kind of what occurs here when we're talking about fixed sized arrays. Now though, let's quickly move on to dynamic sized arrays, because we do have the ability to change the sizes of our arrays. Now, just like a fixed size array, we're going to need to initialize this dynamically size array. We can have zero elements, one element, two elements, etc. doesn't really matter. What I want to talk about now is what happens when we want to resize this array.
16:11
So this is going to be dependent on the programing language and how this array is implemented. But I just want to give you a bit of insight into how we actually do this. Because essentially we're always using a fixed sized array. But when we're implementing a dynamic sized array, we just create a new fixed sized array of a different size okay. There's all kinds of different approaches to doing this. But let's imagine the scenario where we have an array of size four.
16:35
Now let's say I actually want to add a new element to the end here. So I don't want to just like kind of swap out what's here at the end. I actually want to add a new box or a new slot here and push the element inside, just like we might do inside of JavaScript. Now again, this depends on the implementation strategy that's being used. But if this is the case in the naive approach, what we'd need to do is the following. We'd actually need to initialize a new array of size five.
17:03
So we're creating a brand new fixed sized array of size five. And then we're essentially copying all of the values from the original array inside of here, and then adding the new value at the end. Meaning if we want to add another element here to a dynamically sized array, this array needs to be resized, which means this is a big O of N time operation. Okay. However, that's not always the best way that we can resize dynamically sized array.
17:32
For example, we can set the original size to be larger than we need it to be, or when we need to increase the size of the array, we can increase it by more than one slot. So let's say that we get rid of kind of all this stuff that we've done here and now we use a different approach. So now again we have this kind of fixed sized array of size four. And we want to add another element to it. So we want this to act like a dynamic array. This time when we resize the array rather than just adding
17:59
four slots, we actually double the size of the array. Now this is a pretty common approach, so I think I got enough boxes there. Maybe I'm missing one. Okay, let's add one more. Anyways, what we'll do now is we'll essentially double the size to be the size of eight. So now we'll have 34567. And then we have three empty slots. So if I do three more insertion operations here I don't need to resize the array for those additional three operations. I also could quadruple the size of it.
18:27
I could do it by a fixed size every single time. It's up to me how I want to resize the array, but I'm just trying to show you that sometimes when you're using a dynamically sized array, depending on the programing language you're working in, what will actually happen is in the back end, kind of in the memory, you're going to be allocating more spaces and copying values into a brand new version of the array. Again, really depends on the way that this is implemented in some programing languages.
18:53
This is not how it works, but sometimes this is how it works. Okay, so you're actually going to be making a brand new fixed sized array, but you're just increasing the size of that array, which then means you need to copy all of the values from the original array into the new array, and then add the new value and then dispose of the old array. Okay. So that is kind of dynamic and fixed sized arrays. All right. So that's going to start to wrap up this video.
19:18
Now what I want to do is just move to one more slide here where I just quickly go through kind of a summary of some of the main operations that we had. So we have the initialization operation okay. When we're initializing a fixed or dynamic size array, this takes big O of n time when we're inserting into a dynamic or fixed size array. If this is at any position other than the end, then this is going to be a big O of N time operation. That's because we could be inserting at any single point.
19:46
The closer to the beginning of the array that we insert, the longer this is going to take because of the number of elements that we need to shift when we do this insertion. Same thing applies with the deletion. If we were deleting, say, the first element in the array, then we need to shift all of the other elements, kind of in the array to take up that space that was then deleted from the beginning of the array. Okay. Doing index access. We know this happens in constant time.
20:09
Appending this means adding to the end of an array. Typically we can do this in constant time. Now again this depends on how the array is being implemented. In the previous example with that dynamically sized array, I showed you that sometimes when you do an append operation, it will actually take big O of N time. But a lot of programing languages have optimized this such that you can pretty much guarantee it's going to happen in constant time.
20:32
We won't talk about exactly how that implementation is done, but typically you can assume that when you're appending to the end of the array, it's constant time. Again, the example I showed you before was just to illustrate kind of why you need to think about computer science principles and data structures. Popping this means removing from the end of the array. Again, same thing here. This is going to be a constant time operation.
20:53
That's because you simply need to delete whatever's at the end of the array. There's no what do you call it? Kind of shifting that needs to occur when you are popping at the end. You can just remove that element. It doesn't require the length of the input operations to perform that. So with that said, I'll wrap it up here. I hope you found this helpful. And you learned a bit about arrays. And I look forward to seeing you in the next Hello everybody, and welcome to the next video in this section
21:16
where I'll be talking to you about something known as a singly linked list. Now, a linked list is an additional linear data structure that works a little bit different than an array. On the surface, it may seem like the same, but its implementation is different and allows us to have some faster time complexity.
22:09
Singly linked list. We have essentially different slots in memory, just like our array, that are linked together with something known as a pointer. Okay, so let's say we're using numbers here. And these are the elements in our list. Now we have what's referred to as the head of the list. The head of the list is what we're actually going to store. We're going to have some var call it x. And this is going to have a reference to the head of the linked list.
22:36
Now when we have a reference to the head of the linked list that allows us to access the different values in the linked list by moving through the pointers that exist here. Also, I just realized I kind of wrote this a little bit strange. So let's get rid of that variable. Okay. So what's happening here. Well we have what are referred to as nodes in our list. Now every single node in our linked list has the following property. It has a value and it has a next property.
23:05
Now the next property is actually a reference to the next node that exists inside of the list. Now every single one of these nodes is going to have a memory address location right? Might be location one. Location 234. Doesn't really matter what it is. This next property will store the next location to the node that comes next in the list. Okay, so that's the basics on a linked list. We have nodes. Those nodes have a value and they have what's known as a next pointer or a next reference.
23:38
When we actually create the linked list we store the head of the linked list and then the head of that linked list allows us to access all of the different values. So now let's talk about a few operations on our linked list. So with this structure let's say that I want to access the last element inside of the linked list. Well to do that I need to traverse through all of the different nodes that exist inside of this list. And in fact, we can actually write some pseudo code
24:09
that would allow us to do that. So we have access to the head. Remember that all of our nodes have the value and they have the next node. So let's say that we want to access the fourth element. Okay. Well to do that we can create a variable and we can say current is equal to head. Now this is not going to be valid. Code is not going to work if you type it in your JavaScript console. I'm just writing what's known as pseudo code, which is just something that we can
24:32
quickly kind of look at to see how we would go about writing the code. I'm going to say, wow,
24:38
current dot next does not equal no. And that's because the next property of our last node is going to be equal to null, because it doesn't point to any other node. Okay. So we say well current dot next does not equal no. Then what we're going to do is say current is equal to current dot next. And then when we get to the point that this is equal to null, we know that we're on the last node. So we can do something like print current dot value. Okay.
25:16
So if we read through this code I know it's a little bit messy. Essentially what we're doing here is we're creating some variable. This is storing the head of our linked list. Now we want to traverse through the entire linked list. So to be able to do that we need to constantly access the next property of our notes. So we come here to our while loop and we say well current on x is not equal. No we're going to say current is equal to current dot next.
25:40
So that means I'm looking now at my head and I grab the next property that points here to four. So now current becomes equal to this node. And then I repeat the process I say is current on next equal to no no it's not. So we continue. Okay. So now I say current is equal to current dot next. And I keep moving through this until I get to the point where this points to null. And then I know that I'm at the very last value. And then I can go ahead and print what that value is. Okay.
26:09
So that was meant to just illustrate to you how you would traverse through a singly linked list. Okay. Hopefully that makes sense. But that's kind of the implementation. Right. So if we're actually going to build this in JavaScript we'd probably create some kind of class. In fact we'd need two classes. We need one class which is a node class, and another class which is the linked list class. The linked list class would be keeping track of the head,
26:30
and then we want to traverse or access any of the different indices here. We'd essentially do this process up to the index that we want to access. So if we wanted to access index three we just do this one last time. Right. So we could just keep track of how many times we've accessed and then move to that next index. All right. So let me just get rid of all of that. We'll move on to the next operations. All right. So now that we've looked at the traversal, let's talk about what happens
26:52
if we want to add or remove an element from the linked list. So let's say we actually want to add another node here at the end of the linked list. Pretty common thing that we'd probably want to do. Well, in order to do that we would actually need to access the last element inside of our linked list and then create the link to that new element. Right. So we'd have to go through that whole traversal process that I just showed you, access the tail of the linked list.
27:21
And then we'd have to write something like the following tail dot next is equal to whatever the new node is. Okay. So we'd pass that new node. That node would have its value. And its next property would be equal to no. Okay. And then again if we wanted to add another node, we'd have to then access this new node that we added, change its next property to be that new node. And then we'd set the value and the next property on that new node. Hopefully that makes a little bit of sense,
27:48
but we have this kind of node object. The node again has the value in the next property. And for us to link these elements together we have to set those next properties. So if I want to add this new element I need to set the next here to be equal to that. That's how you do an insertion. So what that means is that if we're inserting with this type of singly linked list, we're going to have a big O of n time complexity to be able to do that.
28:13
Now in just a minute I'm going to show you how we can reduce that to big O of one. But for now, with this kind of naively implemented singly linked list, it takes big O of N time. Now the same thing applies if we want to do a deletion. So let's say I want to delete this node right here. Well if I want to delete this node what I need to do is I need to change the next property of this node to be equal to this node. So that means I need to do the traversal that I showed you.
28:40
I need to locate this node. Then I need to go to this node. I need to get the node that it points to. And then need to change this next property to point to this next property. Okay. So I'm going to write again some very basic pseudocode that would do this. I'm going to skip the traversal and just assume that we have the node that we want to delete. Okay. So let's just call this n or let's call this node.
29:01
Okay. So this is the node that we want to delete. So I need to first do something like next node is equal to node dot next. Okay. So I'm storing the node that this is pointing to just to make sure that I don't lose it. Then I need to get the previous node. So I also would need to store the previous node. So I'm going to say previous like that. So I'd have to have access to both of those. And then I would say previous dot next is equal to the next node.
29:34
Now I also could have just written node next. Doesn't really matter how I do that. Regardless I have to set the previous nodes next to be equal to the next node after the node that I want to delete. Now this means that this again is going to be a big O of N time complex the operation, because I need to locate both the previous node and the node that I want to delete. And if that's near the end of my linked list, that could take up to N, which is the size of my linked list operations.
30:01
Now if it's the very first node then it's quite simple, right? If it's the head node, in fact there's actually no previous node. So if that's the case then what I do is I simply set my head node to be equal to the next node in my singly linked list. Okay, hopefully this is making a bit of sense. I'm just trying to show you all of these different operations on how you would actually go about implementing this. All right. So let's delete that.
30:23
We've now talked about insertion and deletion, which right now are both taking big O of N time. We also know that accessing is taking big O of N time. So you might be asking yourself, well what's the point of using a singly linked list. Well things get a little bit more interesting when we implement a circular linked list. Okay, so now what I've done is I've simply changed this so that the last node inside of my singly linked list is now going to have a pointer
30:49
or a reference to the head node of my linked list, making this linked list a circle, allowing me to go through it circularly. Now this will change a few of the implementation kind of pieces of code that I've talked about to you thus far. However, this provides a distinct advantage. Now, the reason we have an advantage here is because now, rather than storing the head node, we can store the tail node. So now if I store the tail node, this gives me access
31:18
to the last element inside of my linked list, as well as the first element in my linked list in constant time. That means that if I want to remove the last element from the list, I can do that instantly. Or if I want to remove the first element from the list, I can do that instantly as well. So that's where the real advantage of a singly linked list comes in. If I want to remove an element from the beginning of the list or the end of the list, or I want to add an element
31:44
at the beginning or add an element at the end. When I create this circular structure, I can do both of those operations in constant time. Now remember that's different than an array when I have an array. If I want to do operations at the beginning of the array here, this is going to take big O of N time, because I need to shift all of the other elements over. When I create this circular linked list, I no longer need to do that.
32:09
Now, in case you're confused on why this happens in constant time, it's because now if I store a reference to my tail and I want to add an element, I can simply do the following. I can say tail
32:21
dot next is equal to some new node. And then I just need to make sure that this new node has the next property, which is equal to whatever the tail dot next was equal to before right equal to tail next. Now I'm not really writing this in kind of the correct order. So essentially what we do is we would create this node. We'd give it its value. We'd first set this new node to have the next property equal to whatever the current next property of the tail is, which is the head of the linked list.
32:50
And then we now set the tails next property to be equal to this new node. And now we've insert an element at the end of the linked list in constant time. Now pretty much the same thing applies if we want to do this at the front of the linked list. So if I want to do this at the front, it's going to be a very similar type of operation. I'm going to create a new node here. Right. So something like that. I'm going to set this new node's
33:11
next property to be equal to whatever the tail next property is. Okay. Then I'm going to take this pointer from my tail. And I'm simply going to change that to be equal to my new node. Now I've just added an element at the front of my singly linked list in constant time. So when we add the circular property again we get this constant time insertion and deletion at the beginning and the end of our linked list. Now if we're doing it in the middle again,
33:41
that's going to be a big O of N time operation because we still need to traverse through the list. But still, this is a huge advantage now because we can insert and delete at the front and the back of the linked list, which we can't do in constant time in the array. Okay, so I think with that said, I'm going to start wrapping up the video here. Let's just do a quick summary. Whenever we are using a linked list. We have some kind of node okay. This node has a value and a next pointer.
34:09
The next pointer points to the next node. If you're wondering how this would be implemented in JavaScript, you could literally do it using objects right where the object has the value. And then you have the next pointer that just is equal to whatever the next node is. Okay. Anyways, beyond that, we then have the ability with this linked list when we use this circular structure here to insert and delete elements in constant time at the beginning and the front of the linked list.
34:36
However, if we want to access something within the linked list, that's going to take us big O of N time because we need to traverse through the linked list to find that element. And if we want to insert or delete something in the middle of the linked list or not at the beginning or the end, again, that's a big O of N time operation. So the disadvantage compared to an array is the index access, right? It's going to be harder for us to access an element that's in the middle of the structure.
35:01
But if we want to do operations on the front and the back of the structure, so the head or the tail of the structure, it's going to be much faster for us to do that. Now in terms of code implementations, you can most likely problem solve and figure out most of them just by using what I've showed you in this video. So if you want to challenge yourself, what you can attempt to do is actually build a version of a linked list in JavaScript. What you need to do if you were going to build
35:23
that is, implement the different operations like insert front, insert back, delete front, delete back and then traverse or locate a specific element. You can be as creative as you want here. You can also look up some references online. I'm not going to ask you to implement linked lists or most data structures in this course. The idea is just to understand how they work and to get the theory behind them. And again, once you understand that,
35:45
it actually becomes fairly trivial to write the code to implement them. The important part is the theory which you now have. So with that said, I'm going to wrap up this video. I hope you found this useful and I look forward to seeing you in the next one. Hello everybody, and welcome to the next video. In this section, while we'll be talking to you about a linked list or a double linked list. Now this is the exact same thing as a single linked list, except you have a reverse pointer.
36:09
So So we have something like seven. I don't know when go with like three and two. Now on this linked list we have a pointer that goes to the next node as well as a pointer that goes to the previous node. And we can implement a circle here as well. Okay. So we can actually have a double circular linked list like this. Because the previous pointer of this node would go to this one. And then the next pointer of this node would go to this one. Now traversing this list is going to happen
36:37
pretty much identically to how we traverse a singly linked list. Except we can traverse in both directions. Since we now have a previous pointer, we can go backwards or we can go forwards, which actually provides a lot of advantages and specific scenarios. So let's just quickly go through this. We have our node okay. Our node is now the exact same as the other one except we have the next and we have the previous pointer. Typically it's abbreviated by prev PR v okay.
37:08
So every single time we create a node, not only are we initializing the pointer that goes forward, but we are initializing the pointer that goes backwards to the previous node. The main advantage here is that if we access a specific node. So let's say I traverse and I find node three. Now what I can do with this node is I can traverse backwards and find the nodes that exist before it. That means that now once I find this element, I can find all of its
37:33
neighboring elements quite quickly compared to with a single linked list where I would have to actually traverse the list again to be able to find the previous element. So before we go too crazy, let me just clean up this example a little bit, and let's look at some implementation details related to the doubly linked list. All right. So with the doubly linked list here. First of all it doesn't matter if we store the head or the tail node. The reason for that is
37:59
we have access to the head and the tail node from both the head and the tail. Right. So from my tail I can access my head, and from my head I can access my tail in constant time. So it's up to you what you want to store. Typically you'll store the head. Doesn't really matter which one you store. Now let's talk about what happens if we wanted to add an element into a linked list. Now, just like a singly linked list, this is going to happen in constant time. If we're doing this at the front
38:24
or we're doing this at the back of the linked list. However, it just becomes a little bit more complicated because there's more references that we need to change. So let's say we want to add in this new green element here with value for. I want to put this actually at the beginning of our linked list. Well, what we need to do is the following. We need to update both the next node from the tail and the previous node from the head to be equal to this node.
38:51
But the order in which we do that is important to ensure we don't lose access to either the head or the tail node. So for this to work, a few things need to happen. First of all, this node needs to set its pointers correctly. So it needs to set its next pointer. So this is next to be equal to the head. And it needs to set its previous pointer here to be equal to the tail. Okay. So that's easy. We can do that. Now how do we do that though if we have access to the head node
39:20
I'm going to kind of write some code to do this okay. So this this will be our new node. All right. And we have access to the head. So those are kind of the two variables. Ignore that. We have the tail here. All right. So what we're going to write is the following. We're going to say node dot next is equal to the head. And the node dot previous is equal to the head dot previous right which is going to be equal to the tail. Okay. So that's what we do then.
39:55
Now that we've done that we need to update the references on the head and on the tail. So we do the following. We say that the head dot previous
40:08
dot next is equal to the node. Now that's because we're getting the head from the head. We're going to previous which is getting the tail. And then we're taking the tail. And we're now setting this next pointer to no longer be equal to the head, but to be equal to this new node. I know it's a little bit confusing how I'm drawing it, but essentially we're deleting this,
40:31
okay. And now we're setting the next property for the tail node to be equal to this new node. Okay. Now that we've done that we need to change the previous property for our head to be equal to the new node. So we go head dot previous is equal to the node. I apologize for my atrocious handwriting here. Let's clear that and let's go here and set that. Now that we've done this, this is fine. Although at this point we would have also had these references here. Okay. And then we're going to set head
41:08
to be equal to node. Right. Because we're putting this up front. So we're going to take our head and we'll now write this here. So now our new head becomes this node after we've written these five lines of code. So it is substantially more complicated to do this when you're using a linked list. But hopefully this kind of pseudocode example gave you, you know, a good concept of how you would go about actually doing this. You need to update two different pointers.
41:33
So the tail pointer and the previous head pointer. And then you need to set the pointers on the actual node. And then you need to update the head to be equal to the new head. If you're doing it on the tail you're gonna do the same thing except you won't need to set a new head node, because you'll already be updating the references and just adding in the tail. Okay, so that is the basics on the doubly linked list. Again, let's just go through the time complexity
41:56
and some of the operations to make sure we're clear. And then I'll try to illustrate kind of more in depth why you would actually want to use this. Okay. So just to recap here, if you want to do an insertion or deletion at the front or the back of the linked list, that happens in big of one or constant time. If you want to traverse the list and find any given node, of course that's going to take big O of N time. Do you want to do an insertion or deletion in the middle of the linked list?
42:20
So we wanted to like delete this node and that would be big O of N time. However, this changes if you already have a reference to the node that you want to be inserting or deleting after. So let's say for some reason I have this node like I have it stored in my program. Okay, if I have that, then I can either delete any node before it or after it, or add any node before or after it in constant time, because I have a reference to the previous node as well as the next node.
42:49
So let's say I want to insert a node before this node with a singly linked list that would still take me big O of N time, because I would need to traverse the list and find the node that came before this node. But since I have access to the previous node, I can actually do this insertion in constant time. So that's one advantage here. So if I'm going to do that insertion, then what I need to do is change my pointers right now I won't actually go through the process.
43:16
But essentially one's going to go here right. This new node will point here. This previous node needs to point here. And then this node needs to point back to that note. If I do that then I've done the insertion and deletion. So it's going to be about four changes that we need to make there or four kind of operations to insert or delete. But still we consider that constant time. Now the main advantage of using this doubly linked list is exactly what I just showed you there.
43:39
It's the ability when we have a certain node to insert a delete after that node in constant time, or to access what what comes before it. Sorry. So imagine that this doubly linked list here was actually implementing something like a music player, where each of these different elements we have here were songs that we just played now that allows us to go backwards and forwards in our structure very quickly. Right? We can fast forward and we can reverse because from this given song
44:10
we have access the previous node and we know what the next node is. Then let's say we want to add an element into our queue. Well, if I want to do that and maybe I want to make it the next song, then all I do is insert it right after the current element. Or if I wanted to maybe add something behind this, I don't know why. For some reason I'd want to do that in a music player, but let's say I wanted to do that. Then I could write. I could add it behind this previous to this element.
44:34
Hopefully this is making a little bit of sense, but that's kind of the advantage of using the double linked list is the flexibility that you get here with having these previous pointers, and also the ability to kind of traverse backwards as many times as you need to. Again, if we use the singly linked list, then we would have to actually re traverse this entire list to find the previous element from any given node that we are on. Now, the disadvantage of using this type of linked list
44:59
is that obviously it's more complicated, right. You can see here we want to do any type of update or delete operations. It requires more steps from us in terms of the references and the changes that we need to make. Also, this is going to end up using more space, right? The reason it's going to use more space is because now we're adding this additional previous pointer. And that previous pointer is going to make it more challenging or not more challenging, but just more kind of space
45:23
consuming for us because we have one more piece of data that we need to store. Now, before I wrap up the video here, I'll just mention that it's a good exercise to kind of try to write the pseudocode that I was just writing to do the insertion and deletion operations. If I wrote all of that code, we'd be here for years. So I'm not going to bore you to death by doing all of that. But try to see, okay, if I have access to this node here, how would I add a new node? What would I need to do?
45:48
Well, you need to make the new node and then need to update the references. But the order in which you update the references is important to make sure you don't lose access to the other piece of data. For example, if first I change my reference here and I say okay, I'm going to point that to this. Now all of a sudden I don't have a reference to this node from this node here, which means I need to first change the reference from the previous node to be equal to this.
46:13
And then after I've done that, since I still have access to this, then and only then do I change this reference here, right? And then obviously these ones are needing to be pointed to the correct areas as well. Hopefully that makes a bit of sense, but something that you can try out on your own if you want to go through some kind of practice examples here. With that said, I'm going to wrap up the video here. I hope you found this helpful. I look forward to seeing you in the next one.
46:36
Hello everybody, and welcome to the next video. In this section I will be talking to you about a queue. Now a queue is an additional linear data structure which allows us constant time operations to access and remove elements from the front and the back of the queue. The purpose of our queue is to process elements in the order in which they are received. The main property you need to remember when we are talking about queues is something known as Fifo. This is first in, first out.
47:05
Okay, so whenever you think of queues just remember this acronym Fifo first in, first out. That means the first element we add into our queue is the first element that comes out of the queue. Now we see queues everywhere. The most basic example of a queue, sorry is a line. So if you're waiting in a line to do something, get some item, whatever it may be, you are in a queue. If you were the first person to enter the line, you're the first person to get the item that you're looking to receive.
47:29
If you were the last person to enter the line, then you're going to be the last person to get whatever item it is. Okay, so that is the basic property of a queue. Now if we draw out a queue here, we always have a front and a back of our queue. Now when we're implementing the queue, we need to make sure all of the elements get inserted in the back of the queue, and then they come out of the front of the queue. Okay, so just like back of the line,
47:52
front of the line, now you can actually insert elements from the front and remove them from the back. If you wanted to do that doesn't really matter. You just have to make sure you do it in the same order every time you do the operation. So in our case, we're going to always insert from the back and we're going to always remove from the front. So that means someone new comes into our line. They go to the back and then they will move throughout the queue to the front as elements get processed.
48:15
Now, a basic example of when you might use a queue is to process different requests. So let's say you have a bunch of people that are trying to access a website. Well, on that website there's some different operations that are being performed. And your server, you have a kind of a back end computer that's running this website needs to handle all of those different requests. So you would put all of those requests inside of a queue,
48:35
you would pop them off of the queue and then you would start actually processing the elements one by one, going through the queue in the order in which the elements were received. There's other ways you could go about doing that, but this is kind of a basic example of a queue. You also can have a queue for something like a music player, right, where you have different songs. So you're going to be processing and playing for the user.
48:53
Now when we have a queue, we have some different operations that we can perform. So we have the ability to put or two on queue and element okay. That means we're going to be adding an element to the back of the queue. And we want this operation to happen in constant time. Now the way we implement the queue will determine how fast this operation actually is. And we're going to talk about that in a second. Okay. Then we have a pop or a dequeue operation.
49:21
I know I'm kind of butchering the spelling here, but you get the point. Again, we want this to happen in constant time. This means that we are removing the first element and returning it from the front of our queue. So this is essentially trying to grab this element so that we can process it. Then we want to have the operation which is seek sorry not seek peek. Although seek kind of work as well
49:43
or front. Now what this is aiming to do is tell you what the top element or the front element of the queue is. So the element that would be popped or dq'd if you call that operation. Okay. Now again, we want that to happen in constant time. And then typically we have some kind of method like is empty, which will tell you if the queue is empty and again we want that to run in constant time okay. So this is the basics of the queue. You insert elements from the back.
50:10
You remove elements from the front. These are the four operations that you typically need to implement when you are writing a queue the put or the on queue, the pop or the DQ, the peak or the front. And then this is empty and sometimes you can have an is full operation as well. We don't need to talk about that right now okay. So now that we've seen this queue I want to show you how we would implement this. Now before I do that, I want to quickly explain to you that all of these data structures
50:33
that we're looking at are used to solve different problems, right. So what I just explained to you, where we have the music player or we had the queue of requests or we have some kind of line, that's when we would use a queue. Then we have these different operations that we expect to be implemented on a queue. Someone else could build the queue for us and we could use that, or we can build the queue ourself when we're building the queue, we want
50:55
to make sure that the different operations have these time complexities. Okay. So the property of a queue is that the put operation has time complexity of constant time pop operation has time complexity of constant time, etc. that's the value in using this data structure. However, for all of these data structures, as I've been describing, we need to actually build them, right? We need to implement them. We need to write the code that allows this queue to function.
51:20
And based on how we write that code, we could have different time complexities for these operations. So I'm going to start right now by showing you what would happen if we tried to implement a queue that uses an array in the back end, because even though we have these different operations, some data structure, some other data structure is going to be storing all of the elements inside of our queue. So if we're going to be building the queue ourself, we have to be careful what data
51:43
structure we use to build this data structure. So you're going to end up seeing that quite a bit. That one data structure kind of lends itself to another data structure. And we can use multiple data structures to implement other data structures. Hopefully this is making a bit of sense, but these are the properties of the queue. Now let's have a look at how we implement the queue using an array. So if we use an array this is not going to be optimal. But I just want to show you what would happen.
52:07
So let's say we have an array here okay. And we can make this. Maybe size five doesn't really matter. Don't concern yourself with the size right now. Remember that if we want to add an element to the end of our array, that's going to be a constant time operation. Okay. If we want to remove an element from the end of the array again that's going to be a constant time operation. That's what we're going to assume as we kind of go through this.
52:31
However, if I want to remove an element from the beginning of my array, sorry is not constant time. This is a big O of N time operation. The reason for that is I then need to shift all of the other elements in my array over to fill the empty space that I've now kind of created. When I remove that element. Okay, same thing. If I want to insert an element at the beginning of the array. If I do that, that I would need to shift all of the other elements in the other direction in the array.
52:59
So kind of remember that because that's important when it comes to this queue okay. So we're creating this array and this array we're going to use for our queue. And that means we need to define a front. And we need to define it back. Now we can define these in any order that we want. But for now I can make the front of my array, the front of my queue and the back of the array at the back of my queue. That means I insert elements at the back or the end.
53:21
I remove elements from the front or the beginning. Okay, so let's go through a sample where we insert a few elements into the queue. So let's say we want to insert three for seven, two and one okay. We want to insert it in this order. So we're going to put these elements into the queue or push these elements into the queue. You can refer to that as whatever you want or on queue these elements again there's a whole bunch of names we can use for the operations okay.
53:46
So if we're doing that we're going to be inserting at the back. Inserting at the back happens in constant time. So we'll start with three. Then we'll have four. Then we'll have seven. Then we'll have two and then we'll have one. All of that happened in constant time okay. So we've now placed all of these elements onto the queue. Now what we want to do is dequeue them or pop them off. So if I want to pop an element I'm going to be removing from the front of my queue.
54:11
Now, since my queue is an array that means that if I grab my element three here, I need to now shift all of the other elements over one position in my array, which makes this a big O of N or linear time operation. Okay, so that means that this queue has a big O of one time complexity for pushing or on queuing, but it has a linear time complexity for popping or removing. So this is non-ideal implementation of the queue. Now what happens is if we decide to switch the front in the back
54:46
here, we're actually just going to reverse these time complexities. So if I make the front of my array the back of the queue and the back of the array, the front of my queue, then that means that now we're just going to switch these. So we're going to have a big O of N push operation and a big O of one pop operation. Okay. Because now I'm going to be pushing to the front, meaning I have to shift elements the other direction in my array. And then I'm going to be popping from the end,
55:12
which will happen in constant time. So an array is not ideal. So before I go any further, ask yourself what data structure could we use that would allow us to have a big O of one time operation for both popping and pushing? Give yourself a second here. Pause the video if you need to. I'm about to reveal the answer to you, which is a linked list. Okay, now we can use both a singly or linked list. In this case, it's totally fine to use a singly linked list,
55:39
so if I want to implement a queue that has those type of time complexity operations, I use my linked list. The reason for that is the following. If I draw out a linked list, let's say we have three elements inside of here a three nodes
55:53
okay. And we have this circular structure. Remember that we always store our tail okay. So now I've created this linked list. And let's decide where the front and back of my queue are going to be. So we can say the front of my queue is going to be at the front of the linked list, or the head of the linked list, and the back of the queue is going to be at the tail or the back of the linked list. So now what happens if I want to insert a node or an element on my queue?
56:19
Well, I need to push that or on queue that at the back. Now since I have access to this tail pointer here, all I do is I write that code right? Which is tail.
56:30
Next is equal to my new node and my new node. So node next would have been equal to whatever the tail
56:40
next was. Okay. By doing that I essentially add a new node here. This kind of gets removed. I'm not going to erase that. And then this node. Now points that new front. Okay I know this is really messy, but you get the idea. We've already looked at how we do an insertion at the back of a linked list. So doing that happens in constant time. Right. So that's the advantage here of using the singly linked list. Now what happens if we want to remove an element from the front of our queue.
57:07
So we want to dequeue it or pop it. If I want to do that then all I need to do is remove the reference to this front element here and change the table's next pointer to go to the next element in the queue. Right? So what I do is I say that my tail dot next is equal to the tail dot next dot next right. Because I say tail dot next which is this. And then tail next next is this. So if I simply change my reference here to go to this, then this front node will be deleted.
57:43
And of course we can return that front node so that it can be processed. So that again happens in constant time. So using the singly linked list allows us to have constant time operations for both removing from the front and adding from the back, which means this is the implementation we would go with when we are building the queue. Okay, so with that said, I'm going to start wrapping up this video here. I just want to do a quick recap for you
58:07
and kind of make sure you understand the most important parts of a queue. We use a queue when we want to process elements in the order in which they are received. We don't care about the elements in the middle of the queue, we only care about what element is next for us to have a look at. If that's the case, then we can use something like a linked list to implement our queue, because it gives us constant time operations for adding at the back and removing at the front.
58:29
That's really the main important part here is that we can push and pop in constant time. When we're thinking of a queue, we always want to remember the Fifo property, which is first in, first out. Let's just go over here quickly and have a look at kind of the cheat sheet for the operations. So I know where do we know these. But pushing or on queuing is o of one popping or queuing is over, one peaking or looking at the front is of one and checking if the queue is empty should be o of one as well.
58:54
We haven't talked about exactly how that works, but if we use this singly linked list example, then we could just check if the tail node was equal to none, and if the tail node is none, that means we have no elements inside of our queue. All right. So with that said, I'll wrap up the video here. I hope you found this helpful and I look forward to seeing you in another one. Hello everybody, and welcome to the next video. In this section I will be discussing the stack data structure.
59:17
Now the stack data structure is another linear structure that is similar to the Q. However, we are going to add and remove elements from the same side. So with a Q we had this Fifo property which is first in first out. However, with the stack we have the opposite which is first in last out or last in first out. That means the most recently added element to the stack will be the first element that we removed. So that would be like the first person to enter
59:47
the line is actually the last person to get the thing. So the most recent person to enter the line is the one who gets processed first. Let me show you a quick example here. It's easy to visualize this. So a stack is named appropriately because we have things like stacks of plates. So if you have a bunch of stacks of plates, or you have a stack of plate in your kitchen, the plate that you most recently put on the top of the stack will be the first one that you take off right
1:00:10
after you take the one off the stack, then you can remove the next one, etc. and the first plate that you put put down, sorry, it will be the last plate that you take off of that stack. So hopefully that makes a bit of sense. But that is the basic properties of a stack. Okay. So let's just draw one out here and let's go through the different operations and their time complexity. So when we have a stack again we're going to have a front and a back. So we'll call this the back and this the front.
1:00:34
It doesn't matter the direction that we do these operations on, so long as we do them on the same side. What I mean by that is if we add elements to the front of the stack, we need to remove elements from the front. And if we add elements to the back of the stack, we need to remove them from the back okay. So you can pick either the front or the back doesn't really matter what side. So let's say we want to add a few elements to the stack. Well we can add the element like 234.
1:00:58
So I'm kind of adding them here and stacking them upwards. This was the first element that I added on to the stack. It will be the last one to be removed. Now if I want to remove elements from the stack, then I remove them in the order in which they were added. Okay, so remove the top element first. All right. So what are the names of these operations. Well the first operation is known as put or push okay. This is essentially stacking elements or adding them on top.
1:01:22
We want this to happen in constant time. We then have pop or get okay. Now this is going to be again another constant time operation. There's some other names we might use for these, so don't worry about it too much. Essentially it's adding or removing from the stack okay. Then we want to have again that peak or front operation telling us what's currently on the top of the stack. And that will be a constant time operation. And then generally we want to see if the stack is empty.
1:01:50
And again, we want that to be a constant time operation. So really the exact same as the queue, except we're doing all of the operations from either the front or the back. So now let's quickly look at the implementation of a stack. And then we can go through an example or two. Okay. So for the implementation of a stack we can use a bunch of different data structures. But we actually can use an array here. Now the reason why we can use an array
1:02:14
is because we're doing operations at the same side of the array. So if we say that the back of our stack is here and the front of our stack is here, and we add elements from the front of the stack, then that means that our pop and push operations will all happen in constant time, because whenever we're operating at the end of the array, we can do constant time operations. So if I want to push onto the stack, that's constant time. Now, if I want to pop off of the stack
1:02:44
again, that's going to be constant time as well, allowing us to use this array. Now of course, we could use a singly linked or doubly linked list, but it's unnecessary for the implementation of a stack. So just having a simple array kind of allows you to build this stack data structure. Okay. So now let's see why we would use a stack. Well stack can actually be useful for something like navigating in a web browser. So imagine we have a web browser here.
1:03:08
And on the web browser we have the back arrow. Right. So let's kind of just do an arrow here. So what happens is I'm going to be going to different pages in my web browser. So let's create a stack here. All right. So for the stack we're going to add different web pages onto here as we navigate to them. So it's possible maybe we have some button on our web page that brings us to something like page A. Well if I press this button then what I'm going to do
1:03:33
is add the current page onto my stack. Okay. So I'm going to push this onto the stack. Let's just call this something like page one. Or it will kind of label our pages here. And then I navigate now to page. Really we should have called this something like page two. Okay. So now we're on page two. Maybe page two allows us to go to page three. And then on each of these pages we have this back arrow okay. So now if I decide to go to page three I'm going to take this page.
1:04:02
And I'm going to push this onto the stack, which now means I have page two on the stack. So now from page three let's say I want to go back. Right. Well for me to go back, all I have to do is actually just grab whatever the current element is on the top of the stack, and that's the page that I would navigate to. So when I click this back arrow here, all I do is pop this element off of the stack. And then that will bring me back to page number two.
1:04:29
So hopefully this is making a little bit of sense. But now I'm on page two. This element will now be removed from the stack because we're currently kind of on this page. We navigated to it trying to race some of these lines here, although it's not really working very well. So now if we're on this page and we press the back arrow, then all we need to do is kind of delete this page. Here pop whatever's currently on the stack, and then that will bring us back to that page.
1:04:52
Hopefully that makes a little bit of sense, but this is a stack of different pages that we're kind of building. Right. So the idea is we keep stacking our different pages. And every single time we want to go to the previous page, all we have to do is pop off of the stack. Okay, so we're just popping it. That's going to then remove it and give us the page need to go to and just keep popping popping popping popping until you get to where the stack was originated from which was this first page.
1:05:15
So doing a web browser kind of back and forth. So forward arrow, back arrow, etc. you can kind of implement that using something like a stack. Now another interesting example here is actually using a stack to build a queue or in fact using two stacks to build a queue. So before I go through this example, think about how we might go about using two separate stacks to actually implement a queue data structure. Remember, when we have a queue,
1:05:40
we're going to be inserting from the back and removing from the front. So we do operations at the opposite side. So how do we do that using a stack. So hopefully here you've had a second to think about this. This is a pretty decent exercise to go through on your own. Now the first thing to understand here is that one of the operations either push or pop, is going to end up happening in linear time. Okay, so big o of N time. Now that's fine.
1:06:03
It's still a good exercise to go through because you're going to see how we can use these different data structures together. So we have two different stacks here okay. And we want to build a queue. Now we're going to label these two different stacks. We're going to have an input stack. And an output stack. Now there's multiple ways to go about doing this. But the way that I'm going to show you here is probably the most common okay. So we need to define either a special way
1:06:24
to push elements on to the stack or to pop elements off. Now it's either going to be that this push operation is going to take linear time, or this pop operation is going to take linear time. So we need to decide which one we want to optimize. In our case I'm going to say that pushing on to the stack is what I want to take longer than popping. So I want to able to instantly pop off the stack in constant time pushing. I can take a little bit longer. Okay, so what are we going to do?
1:06:50
Well, what we're going to do is we're going to push elements onto our input stack. So what I will do is if I have an element one here, I'll put this directly on the input. Now since there's only one element, there's nothing special that we need to do. We can just add this directly here. However now let's say I want to add element two. Now if I just put element two onto this stack and then I pop off that stack, then I don't actually have a queue. Right.
1:07:14
Because I want to process one before I process two. And I want to make sure that I can process one instantly. So what I'm actually going to do before I take my new element, two, which I want to place on to my queue, I'm going to take whatever's on the input stack and I'm going to put it onto the output stack okay. So I'm going to pop all the elements in order from my input stack and push them on to output. So I'm going to take this here and push that over. Okay. So we've pushed one over here.
1:07:40
Then we're going to push element two onto our input stack. And then we're going to pop all the elements from the other stack and push those back onto the input stack. So let's just kind of erase some of this here. Essentially what happens is the one gets moved over here, the two gets placed here. So we've now inserted two. And then we go back to our output stack. And we place one back on the input stack. And now one is ahead of two in the stack.
1:08:04
Which means if I pop this off the input stack I get the correct queue order. Okay. So when I'm doing a push operation, I need to first take all the elements on the input stack, place them on the output stack for my new element at the bottom of the input stack, and then push the elements back to the input stack. I know, seems complicated, but this is how we do it with two different stacks. That now means if we pop from the input stack,
1:08:29
we get the correct queue order because one was inserted before two. So we want to remove that first. Okay. Let's try this with three now. So if we have three we need to do the same process. So we're going to pop all the elements off. So we take one and two and put that on the output stack. When we do it notice it reverses the order okay. Then we put three
1:08:48
back on the input stack. And then we pop off the output stack onto the input stack. And notice we maintain our order here. So we're essentially reversing the order that we'd have. We were just using a normal stack one last time. If we have four again we're going to pop this off. So one two and then three place four on to here. And then we'd have three, two, one. Because that's the order that we pop off of the output stack. There you go. You've just used two stacks to implement a queue.
1:09:20
Now as a quick recap here we have the different operations. So pushing or putting, popping or getting peaking or front or is empty. All are going to run in constant time. And again. The main property of our stack here is that the first element in is the last element out, or the last element in is the first element out. Hopefully you found this video helpful. I'm going to wrap it up here. I look forward to seeing you in another one. Hello everybody, and welcome to the next video
1:09:44
in this section where I will be discussing binary trees. Now this is going to be the first data structure that we're looking at, which is non-linear. I won't lie to you, it is a bit more complicated than the other data structures we've seen thus far. But it is interesting, and there's quite a few optimizations we can make to code by using a binary tree. So let's start by discussing a binary tree. And I just want to be clear here in case you're familiar with this topic
1:10:08
I am not talking about binary search trees. Now binary search trees are a specific type of binary tree. We're going to talk about those in the next video. Okay. So what is a binary tree. Well binary trees are simply trees that satisfy the property that any given node in our tree can have at most two children node. Now it might only have one child node. It might have no child node. Those are fine, but it can have at most two children nodes.
1:10:37
Which means again, for any one of these nodes, you can have at most two, you could have one, you could have none. Now when we're looking at our binary tree, we have a few different definitions here. I know this one's pretty messy, but this here is what we refer to as the root of our tree. Okay. Having access to the root allows us to access all of the other nodes inside of the tree. The nodes that don't have any child nodes are referred to as our leaf nodes. Okay.
1:11:06
So a leaf node has no children nodes. Then these right here which connect our nodes are referred to as edges okay. These are kind of edges in the tree. And then we have the height of the binary tree okay. Now the height or age for the binary tree is the largest number of edges that exist between any set of nodes. So that means in this binary tree the height is equal to two. Because if we look at the longest path in our binary tree, we see that we have two edges. Okay.
1:11:39
I'm just going to keep going through definitions. I know there's a lot here, but once I get through all of these, then I can actually explain more of the concepts in the tree. So let's say we had one more node right here. Then the height would change to three because we can count three edges here in the binary tree okay. We also have something known as the depth of a node. Now the depth of the node is how many edges we have to go up in the tree to reach the root node.
1:12:06
So from this node here we have a depth of three. From this node here we have a depth of one because we just need to reach the root node right here okay. So for every single node if we count the number of edges that are required to go back to the root node, that is the depth of that node, we also call that the level of the nodes that's on level one. This on level two this is on level three okay. Now the advantage of using a binary tree is it can allow us to access, delete
1:12:33
and find information in a fairly fast time complexity. So let me erase all this and let's start from the beginning. Here and go through some more kind of properties of our binary tree. All right. So we have a tree here. Now we're going to have nodes okay. So every one of these things that you see here is a node on the node we have a value okay. That values kind of storing the different data. So our nodes can have numbers inside of them. They could have strings. They could have arrays.
1:13:00
They could have other nodes. They can store whatever they want. And then we have a left
1:13:05
and a right child okay. Or pointer. So here from this root node this here would be the left. And this year would be the right. And then from these nodes there left and right would both be equal to null. And then they would have whatever value kind of is the data that they're storing. So that makes a bit of sense. But we have a node, we have a value. And then we have the left and the right child for that node. And those left and right properties here are pointing to another note. All right.
1:13:39
Now that we've seen that I'm going to draw out a binary tree. And I'm going to show you how we would actually traverse a tree and also how we insert values inside of it. All right. So I have a binary tree here. And unlike a stack or a queue, it's not necessarily intuitive how we would actually go about for example, printing all of the different values that exist inside of this tree. So for the first exercise here I'm going to write some pseudocode that will illustrate to you
1:14:03
how we can do something known as traverse a binary tree. Once we look at the traversal process, then I can talk to you about what happens when we insert or delete elements from the tree, because we need to know how to traverse before we can actually do that. So the whole idea here with this binary tree is that we're storing nodes in different levels. And by doing this, we can actually quickly access different nodes in our tree and insert and delete them as well.
1:14:27
Again, you're going to see that as we go through those different operations. But based on the properties of our binary tree, we can have some faster time complexity operations for insertion, deletion and retrieval of different elements. Okay. So let's see how to start. We would very simply take this binary tree structure where we have access to only the root node, and print out all of the different nodes that exist inside of the tree. Well, to do that, we're actually going to use a queue.
1:14:54
Now you can try to write this algorithm yourself if you want to. It is going to be a little bit challenging, but I'll write it out for you on the right hand side of the screen in my horrible handwriting. Okay. So we're going to start by creating a queue. All right. Inside of the queue we're going to place our root node which is node one okay. Remember that on our nodes we have the value and we have the left and the right property. We're now going to create
1:15:19
a while loop. And we're going to say well not queue. Dot is empty okay. So we're essentially going to loop through all of the different elements inside of our queue. Don't worry too much about the actual code that I'm writing here. Again this is kind of pseudo code. It wouldn't actually work if you typed it into your computer. I'm just trying to illustrate the process that we would go through. So what we're going to do is we're going to pop the first element off of the queue,
1:15:44
and then we're going to print that out. Okay. So what we're doing is we're just trying to print all of the different elements in the queue. So we're going to say something like current. So CR here is equal to Q dot pop. Now that's going to give us whatever the current element is. And then we can simply say print and then CR dot value. And it's going to print out what the value is. Then what we need to do is add on to the queue the left and the right child of this element. Okay.
1:16:17
So we're going to say if CR dot left then q. So push cr dot left okay. And then we'll do the same thing for right. If CR dot right then q dot push current dot right okay. Hopefully you can read that. What we're doing is we're setting up a while loop. We're making sure that our Q is not empty. We are popping the first element from our Q, and then we're going to print out what the value is. Then we're going to look at this element that we printed out.
1:16:56
And we're going to say okay does it have a left child. If it does we need to process that element. So let's add that to the Q. That's what we do here. If it doesn't there's nothing we need to do okay. Does it have a right child. If it does have a right child then we are going to add that element to the Q so that we can process it. So I'll kind of walk you through what would happen here if we have a sample. Q so let me do this in a different color. So let's say that this is our Q here okay.
1:17:19
We have a front and we have the back. We start with element one on the Q. So what happens is we come into our while loop we say is the Q. No it's not. So we pop the first element off the Q. So that means we take one
1:17:35
and that becomes equal to current okay. We're then going to print out what the value is which is one. So we'll do kind of the print stack here on the left hand side okay. So we've now printed that value. Now we check if current has a left. Well does one have a left. Yes it does. It has a left of two. So we're going to add that on to our Q okay. So we add that to the front of the Q then we check if it has a right. Well it does have a right. That's right here.
1:17:57
So we add that onto our Q from the back okay perfect. So now we have these two elements on the Q. Now we return back to the top of the while loop. And we ask ourselves is the Q empty. Well the Q is not empty. There's two elements inside of it. So we pop the element off of the Q. So let's write two here and pop that and remove it okay. Now we print out the value. So we get two. And then we check if it has a left. Does this have a left. Yes it does. It has left a four. So we add that onto the Q.
1:18:26
Does it have a right. Yes it does.
1:18:29
So we add the right child of this element onto the Q okay. Now we continue the process. So now we come here we pop the top element off which is three. So remove that. Here we print out the value. Then we check if the current has a left. So does our three here have a left. No it doesn't. So we don't have to do that. Does it have a right. No it doesn't. So we don't have to do that okay. So we just continue. We move back into the while loop here. The Q is not empty.
1:18:57
So we pop the top element which is four okay. So now we print out four. And then we check if it has a left. Doesn't have a left. No it doesn't. Does it have a right. No it doesn't. So we don't need to do anything here. And now we can pop the last element five. Print that out. And we see it doesn't have a left or right. So we're good. And we have now processed the binary tree and gone through all of the different elements. Okay. So what I just showed you
1:19:21
here is actually what's referred to as the breadth first search algorithm. Now we're going to have an entire video on this where we actually look at writing this in real code. But for now what we've done is we've set up a queue, we placed an element inside of the queue, and then we're constantly looking at that element. So we're processing the element, and then we are checking if it has a left or right child. If it does, we add the left and the right child to the queue to be processed. Next.
1:19:44
So we process this by level of the binary tree okay. We do one level at a time. So we start with one. Then we go to two. Then we go to three. Then we move on to the next level. Then we do four, then we do five. If there was more elements here, we would have done those in that order. Okay. So that's how this works. We're going to process elements in the order in which they exist inside of our binary tree. And we'll keep going level by level until we get every single element.
1:20:09
So that is the first way that you can traverse a binary tree. Now though, I want to show you what happens if we want to traverse a binary tree in a depth first search approach. Now a depth first search approach essentially means that rather than going level by level, how we did here, we're actually going to go as deep as we possibly can on every single node while we traverse it. So let me set up another example here and then I'll be right back. All right. So I've set up another binary tree here.
1:20:38
And I want to show you how we traverse this tree using the depth. First search okay. This is a different type of search that rather than using a Q is going to use a stack. So in this instance we are going to print out all of the different node values. But we're going to do this in a different order. So the way we're going to set this up is we're going to say s is equal to a stack. And we're going to place on the stack our root node, okay. We always are going to start with this root node.
1:21:02
Whenever we're doing some kind of traversal. Then we're going to set up our while loop again. And we're going to say well not S dot is
1:21:11
empty okay. So just making sure it has some elements. Now we need to pop the top element off. So we're going to say C I'm just going to do C this time rather than current is equal to S dot pop. That removes the top element. Then we're going to again print C like this. And now we are going to push the left and right child onto the stack. Now the order in which we push this is important. So we need to decide do we want to traverse right first or left first.
1:21:40
Now in my case I'm going to traverse right first. But you can do this in any order that you want. Okay. So I'm going to say if C dot left okay then s dot push c. Let's do it like this dot left. And if c dot right then S dot push c dot right okay. Hopefully you guys can read that I know that it is pretty messy. All right so there you go. That is our algorithm. And now let's actually simulate this algorithm with our stack. So where do I want to put my stack. Let's kind of draw it right here.
1:22:21
Let's say this is the front and this is the back. And then we can write what's being printed on the left hand side of our screen okay. So we start with element one. So element one is going to start at the front of our stack or node one. We're going to pop that off okay. So we remove that from the stack. And we're going to print it out. So we have one right there. Then we're going to check if it has a left or if it has a right okay. So if it has a left we're going to push this onto the stack.
1:22:44
So in this case we can see that we do have a left. So we push a two. Let me just put it right here onto the stack okay. And then we check if we have a right. And then we push that onto the stack. Now all of the operations we're doing from the front of the stack here. So that means I'm going to be pushing my right node on to the top of the stack. Okay. So now those elements have been added. Now we need to part from the stack. So we're going to pop three off right.
1:23:09
Because we're using a stack not a queue saw popping from the front. All right. Now we print out three because we're processing that element. We see if it has a left. If it does we're going to push that left on so it doesn't have a left. So we don't need to do that. We see if it has a right. It does have a right which is five. So we push that element onto the stack okay. Now we are done here. Let's erase this and move to the next element okay. So now we're going to pop five off the stack.
1:23:34
So pop that off. We're going to print it out okay. And then we're going to see if it has a left and a right. It does. It has left and a right. So we're going to push those on the stack. Let me just increase this a little bit. So we have six and we have seven that get added to the stack in that order because we pushed the left first okay. Now we need to pop. So we pop off seven. We say does seven have a left or right. No it doesn't.
1:23:57
So we just print it out here and then we move on to the next element okay. So now we pop up six. So six becomes current okay. We print six doesn't have a left or right. No it doesn't. So we continue moving okay. Now we move on to two. So we pop two off. We print it and we see this have a left or right it does. So we add four here onto the stack. And then you get the point. Here we are going to now make this equal to four.
1:24:28
And then print four out. And then we are done. Because now we will have no elements inside of our stack. All right. So let's just draw out the traversal order that we actually went through here. And we just kind of erase the stack here. So it's a bit more clear. All right. So we started at one. Then we went down to three. Then we went to five. Then we went to seven. So we didn't go in the level order like we did before. We went as deep as we could possibly go on the far right node.
1:24:56
That's kind of the first thing that we did. Okay. We went as deep in the tree as we could go. So that's what we did here. Then as soon as we reached this depth, we continued going as deep as we could on the other child. So in this case, we went as deep as we could on the left side from this node here. Okay. Then we were all the way back up here and on to two, and then we went to two, and then we went to four, and we would have continued going as deep
1:25:20
as we possibly could have on any single branch that we had inside of this tree. Okay. So this is the depth first search. And this is not necessarily the opposite, but a different way of traversing a tree. The depth first search, depending on how you set up this left and this right here is going to traverse as deep as it possibly can on either the right direction or the left direction first. Now, if I had swapped out these blocks of code here, and I had pushed the right and then pushed the left,
1:25:46
we would have looked on the left side of the tree first and then the right side of the tree, because we were pushing that left child to be on the top of the stack. Right. So again, I would have to reverse that if I wanted to then move to the left side, then go to the right side. Okay. So that is our basic traversal of a binary tree. Now let's look at what happens if we want to insert or delete elements into the tree. Let me clear this and we'll get a new example. All right.
1:26:11
So I've kind of butchered another drawing here of a binary tree. Get used to the bad handwriting. Hopefully it's still visible. So you guys can read all of this. Regardless, the question that I kind of want to ask you here, and then we're going to go through is how we would insert the node six in the correct position here, which is the first kind of empty position that's available. Okay. Now there's about a million questions I could come up with related to binary trees,
1:26:32
but this will show you a basic insertion order. Okay. So how do we go about inserting six into this binary tree. And what is the time complexity of that operation going to be. All right. So to insert six what we essentially need to do is find the first position in which we don't have a left or right child. But we need to do that by traversing this binary search tree, using a level order traversal or a breadth first search. What I essentially want to do here is I want to look at the nodes
1:27:04
so the left and right node of my root node here. And I want to first ask okay, does this have a left child. If it doesn't have a left child then I'll just insert this node right here. Then I'm going to ask doesn't have a right child. If it doesn't have a right child, I'm going to insert the node as the right child. Now if it does have a left and right child, I need to repeat the process first, starting with the left child, then the right child. Because again, I'm looking for the first empty slot
1:27:29
that I can insert this node into. I could insert it here, right? I could insert it here. That's fine. But I don't want to do that. I want to insert it in the correct position in the binary tree okay. So again we're going to repeat this process now. And what I would do is I would first process the left node then process the right node using that breadth first search which is the first traversal approach I showed you. So I'd come here to this left node. I'd ask okay, does it have a left child.
1:27:57
Does it have a right job. Well it does not. So I wouldn't do anything for this node. Right. What I would do is actually just add these two nodes to a queue so that I can process them. Next. Then I would come to this right node because that's the next node in the queue. And in the level order that I need to look at. And I would check does this have a left child. It doesn't have a left child. So then I would just insert this as the left child and then I would be done.
1:28:19
So again we're looking level by level here and finding the first node that doesn't have a left or right child. As soon as we find that we insert the node there okay. So that is the insertion process. Now I won't write out all the code because we pretty much know how to do that. We just do the traversal until we find that we don't have a left node. Then we would insert and then just stop doing the traversal. Now what is the time complexity
1:28:40
of this operation going to be now for this insertion operation, based on how we have the time complexity laid out here, this is going to be big O of N time, where n is the number of nodes that exist inside of the tree. The reason it takes that long is because we don't know where we're going to find the first node that doesn't have a left or right child. For example, if this was actually what the tree was and we wanted to insert a node into here, we'd have to look through this node,
1:29:07
this node, this node, and then this node, and then do the insertion. But we also could have a situation where we have nodes like this. And we're adding the node as the far right most node in our tree. Right. So we want to be adding it here imagining these already are existing nodes. If that's the case I need to look through every single node in my binary tree before I can perform the insertion operation. Now there is other ways to speed up this type of operation,
1:29:32
but not in this specific type of tree that we're looking at right here. Okay. So that's that insertion operation. All right. So I've just cleared the screen here and came up with another example where now I'm going to show you how we can delete a node. So you saw in the previous example there that we inserted a node and that took a big O of N time. Now that's because of how the tree was set up. If we're using something known as a binary search tree,
1:29:54
which I'm going to talk about in the next video, you'll see that we will actually get some better Big-O notation time complexities. But in this video, when we're just using standard binary trees, that's not necessarily the case. So yes, binary trees can improve our time complexity, but they don't always improve it. It depends on the structure and some of the properties of the tree. Regardless, let's say that we want to delete node two here. Well, if I want to delete node two from this tree,
1:30:18
it's not quite a trivial operation because I have two children nodes that are connected to this node. So it's not as easy as me just removing the reference from this node right here. The parent node. In fact, what I actually need to do is I need to find a node that I can delete that doesn't have any children node, and then swap that with this node. Right here. So really what's going to happen is the following. If I want to delete this node or any node inside of the tree, I'm
1:30:47
going to locate the furthest rightmost node in my tree. Now in that case that node is going to be seven. The way I can locate that is using a depth first search approach, which is what I showed you already, right? Where we're traversing the tree, looking on the right side of the tree first. Now as soon as I find a node that doesn't have a left or right child, I know that I found a leaf node and it's safe for me to delete a leaf node,
1:31:08
because if I delete a leaf node, I'm not deleting any children nodes, right? Because it's not connected to anything. So what I want to do is I want to take two and I want to create that or move that to a leaf node. So then I can delete that node. Okay. So what I do is I locate this node. Once I locate that node I'm going to store kind of the parent of the node okay. The reason I need to store the parent of the node is because for me to delete this node, I need to actually have the edge
1:31:35
from the parent to this node removed. So I go through my tree doing my depth first search. And I essentially look at every single node and I say, are your left or right children a node that doesn't have any left or right children? If that's the case, then I've located the parent node that contains a node on the left or right side that I want to delete. Okay. So in this case I locate this node here. And I know that on the right side this is the node that I'm going to be deleting
1:32:01
which is going to be on the left or the right side okay. So we find this parent. And now that we've located this parent we want to find the node that we want to delete. So if we wanted to delete two we now need to do a breadth first search. We could do a depth first search as well. Doesn't really matter. But we'll probably do a breadth first search to locate that node. So I've now located this node two. So all I do is I take the data and I swap it on these two nodes. Really.
1:32:27
Actually I just take seven and I place that here on this node. Okay. So I turned that into node seven. Now that I've done that I can safely delete this node because I've stored its data in another node. So now all I do is delete the node here. And I have actually deleted node two. I swamping the data with that edge node. Okay. And the way I do the deletion is I just say that this node next is equal to null. And as soon as I do that I now lose the reference to what used to be the node seven.
1:33:00
And now seven is on the left hand side of my tree. Okay. So again the basic algorithm is find the furthest rightmost node. Then you need to find the parent of that node. So you kind of do that while you're finding the node. Then you are going to find the node that you want to delete. You're going to take the data from the furthest rightmost node and essentially put that or copy that inside of the node you want to delete.
1:33:22
Then you're going to delete the furthest rightmost node, and you delete that by changing the reference of the parent of that node. Okay. That's how you perform a delete. I'm not going to run you through all of the code here because it is a little bit complicated, but I just wanted to conceptually kind of give you that information. All right. So now we are almost done. But I need to start talking to you about a few different types of binary trees.
1:33:42
And some properties that we need to have a look at here. So one of the most important things of our binary trees is being able to determine the maximum number of nodes and the minimum number of nodes that we can have. Now I'm going to do this on the whiteboard. And then I'm going to go to a PowerPoint slide where I'll give you some more formal definitions. So we know that when we have a binary tree like this, that the property of the binary tree
1:34:05
is that every single node can have at most two children nodes. We also have a height of this tree. Right. Which is the maximum depth of any given node. So one property of our binary tree is that the maximum number of nodes that can be contained inside of the tree is two to the exponent of the height of the tree, plus one minus one. Okay, this is just something that you kind of need to know n. So the maximum value of n, which is the number of nodes inside of our tree,
1:34:37
is always equal to two of whatever the height is plus one minus one. So let's punch this in. In this case the height is two. So that gives us two to the exponent three which is eight. And then we subtract one. And this gives us seven. And you can see this binary tree is completely full here up to height two. And we have seven nodes inside row 4 to 1. That is seven. Let's go one level deeper just to prove this to you again. Right. So now I don't know why I'm writing eight there
1:35:06
because I wanted to add eight nodes. We'll add some more nodes here okay. Now our height has increased to three. So now if we punch in the formula we get two to the exponent four minus one which is 15. And if you start adding this up we have eight plus the seven which is going to give us 15 nodes okay. So the maximum number of nodes in any binary tree is always going to be two to the exponent. H plus one. All right. So just remember that very important okay.
1:35:33
That the maximum number of nodes you can have in your tree is two to the exponent h plus one minus one. And that's just due to the properties of this tree. The height of the tree is an important factor. Again that's going to be the maximum possible depth between any given node in the tree. And there's some other properties we can look at at the tree where the height is always going to be a maximum of n minus one, where n is the number of nodes in the tree.
1:35:56
The reason for that is we could potentially have a tree that is actually just a linked list, right? Where we don't have any. Right children, we just have all left children. In this case, we've really just implemented a linked list. Right now, the height of this is three, and that is what the maximum height can be when we have four different nodes. Okay. Now we could have also just had only right children. So if we only had right children then again you get the same thing.
1:36:22
You get a linked list here. In this case the height is four going to the right. All right. So those are a few of the properties I wanted to show you. Maximum number of nodes two to the exponent each plus one minus one. And then the maximum height is always going to be n minus one. Now let's go to a power point. And I'm going to talk to you about a few different types of binary trees that we can have and some of their properties. In fact, I think I'm going to throw that
1:36:45
in another video because this one's getting quite long. So just wait for that video and I will talk to you about the different types. Hello everybody, and welcome to the next video in this section where I will be continuing and talking more about binary trees. Now, before we get into this video, I just want to mention that there is a lot that we can cover related to binary trees into data structures and algorithms in general.
1:37:05
The goal of this section is not to be a comprehensive overview of everything in terms of data structures, algorithms. It's meant to give you almost a crash course in kind of a high level overview of most of these topics. Yes, we've gone into examples. Yes, I've shown you some details and some pseudo code, but I don't want to get into full code examples. Are we showing you tons of implementations? Because that's going to take a massive amount of time
1:37:27
and not be the most beneficial thing you can learn at this point in time? For many junior developers, you're never actually going to have to use data structures and algorithms, but it will be kind of assumed that you know what they are and you have some understanding of them. So that's really the objective here of this section. Give you a high level overview, give you a few examples, and make sure that you're not caught off guard. If this were to come up in something like an interview
1:37:48
where you were to see these in some kind of production code environment. Hopefully that makes sense. With that said, let's keep going. Okay, so Binary Tree recap just to make sure we're all on the same page here. Every node in our binary tree contains a value or some data, and then a left and a right property. Each node can have at most two children, and we stored the root of a binary tree, which then gives us access to all of the other nodes.
1:38:11
Now the depth of a node is the number of edges between that node and the root, and the height of a binary tree is the maximum depth of a node. Okay, so that's everything we already learned. Just want to quickly go through that again. Now let's talk about some binary tree traversals. So I showed you that we can traverse a binary tree in a variety of different ways using the breadth first search or the depth first search approach. Now there's actually a few other ways
1:38:33
that we can traverse this, structure that I haven't yet shown you. So depending on the order we add nodes into our stack or Q, we can traverse from the left side first or the right side first. We saw that in the previous video. And we saw how we can kind of go through and search for different nodes. However, there's three kind of famous ways to go about traversing the tree. They don't actually need to use a breadth or depth first search approach.
1:38:57
I'm not going to show you the code for actually performing this traversal, but you can come up with it fairly easily once I talk to you about what these different traversals are. So we have an in-order traversal, a preorder traversal, and a post order traversal, which are used commonly a lot in a lot of data structures and algorithms style questions where we are trying to get different values of nodes. Okay. So let's look at the inorder traversal.
1:39:19
The inorder traversal traverses the nodes in our tree from left to right. Specifically what it does is it processes the left node, visits the current node and then processes the right node. Now I'll walk you through the inorder traversal of this tree. But you'll see that it's fairly easy to actually look at a tree and very quickly come up with this when you know the difference between in-order preorder and post order, which is fairly intuitive.
1:39:42
So when we look at this tree here, what we're going to do is essentially follow this algorithm process. The left node, visit the current node, process the right node. And we just apply this to every single node. So we start at node one and then we process the left node. We are now at node two. We process the left node which is four. And then we process the left node which is eight. Now from eight we try to process the left node but there is no left node.
1:40:04
So that means we then visit the current node. So we would mark down eight in our in order traversal. And then we process the right node. There is no right node. So now we are done with eight. So that means now we go back to four. Because we finished processing the left node. So from four we visit the current node. So we mark that in our inner in order traversal sorry. And then we visit the right note or process the right node.
1:40:25
Sorry. So we come to the right. Now we try to process the left doesn't exist. So we visit the node. So we mark down nine. Then we try to process the right doesn't exist. So we now we go back to four. At this point four has processed the left visited itself and processed the right. So now we go to two. So now we're at two. We've just processed the left subtree of two here. So now we say that we're going to visit this node. So we mark down two in the inorder traversal.
1:40:48
Then we go to five from five. Here we have to process the left tree. So we go here and we process the left tree. When we process left of ten we see that we don't have a node. So we visit ten. We mark that down try to process the right. We don't have one so we go back to five. Now we've processed the left of five. So now we visit this. So visit the current node. We mark down five and our inorder traversal. Then we process 11. Here come back up to five. Five is now done.
1:41:14
Come back up to two two is now done because we've processed left visited and then processed the right. Now we come to one. Now that we've processed the left subtree of one, we marked down one in our in order to traversal, and then we continue on the right side. So we go here to three from three we need to process the left. So we process six. Six has no left subtree. So we visit it which we do right here. Then we process the right. 13 has no left or right.
1:41:37
So we visit it come back up to six come back to three. And now at three we've processed the left. So now we visit three. Then we go to the right. We see that we have a seven from seven. We need to process left subtree. So we do that. We visit 14. Then we come back up to seven and we visit back. Now I just went through the whole thing which might be a little bit confusing, but you can see that I'm essentially just reading these node values from left to right. Okay. So 84925 1011 one.
1:42:03
And then this is 613 three 714 okay. So I'm reading it literally from left to right. That is what the inorder traversal does. Okay. Next let's move to the preorder traversal. So the preorder traversal visits a node and then traverses both its subtrees okay. So it's going to visit and then go left and right. So the not inorder sorry let's just say preorder. My mistake here. Traversal of this tree is 124895 okay. So let's go through this. So we start at one. We visit the node.
1:42:33
We then go to the left. We visit the node. So mark down two. We then go to the left. We visit the node. We mark down four. Then we go to the left. We visit the node. We mark down eight. Now that we've done the left we need to process the right. So we go to the right. We mark down nine. We come back up to four. We've already looked at that. We come to two. And now that we've processed the left and visited, we need to go to the right.
1:42:53
So we mark down five because we visit that, then we process the left. So we mark down ten, come back up, process the next one which is 11 okay. Now we're done with two and we go to one at one. At this point we've visited the current node and processed the left node. Now we go to the right. Now we're at three. So we mark down three because we visited that first. Then we process the left. So we go to the left mark that down and then we process left. Doesn't exist.
1:43:16
Process the right 13 Mark that down. Come back up to six. Six is now done. Come back up to three. Now we need to process the right. So we mark down seven. We mark down 14. And we have finished the preorder traversal. So you're kind of going in the same order that you would in an in-order traversal. But you're visiting the current node first okay. So you can kind of practice on this tree if you want. But you can see that this is the answer right here of the not inorder.
1:43:40
Again sorry. Let's just say preorder traversal. My apologies on the mistake okay. Next slide. Here we have post order traversal. The post order traversal traverses both a node's subtrees. Then visits the node. The push post order traversal of this tree is the following. So for this we're processing the left, processing the right, and then visiting the current node. So let's start at one okay. So we're going to process the left then the right then visit. So we go to the left from two.
1:44:04
We're going to go to the left from four. We're going to go to the left okay. Now we're at eight. It has no left or right. So we visit this node. Then we come up come back up to four. Sorry. We've now finished the first step. We now need to process the right. So now we marked out nine because it has no left or right. Come back up to four. Now that we've processed the left and the right we can visit this node. So we visit four. Okay. Come back up here to two.
1:44:26
We've now done the left subtree. Now we need to do the right subtree. So we go to five again we need to process the left and the right first. So we process ten. Mark that down process 11. Walk that down come back up to five. Now we can visit that because we've done the left and the right subtree okay. Now we come to two. Two has now completed the left and the right subtree. So now we mark down two which is what we do right here. Coming back up to one. We've now completed the left subtree.
1:44:49
We now need to do the right subtree. So we go to three okay. We need to process the left and the right. First we go to six. Same thing. We need to process both the right and the left. So we process 13 okay. Few that here come back up to six six now is done on the left and the right. So we marked down six. Come up to three. We're now done the left subtree. Now we need to do the right subtree. So from three we visit seven okay seven needs to do the left and the right first. So we do 14 okay.
1:45:14
So we mark down 14 here. Then we come back up to seven. Seven is now done. We mark down seven three is now done. We mark down three and then one. Our root note is always going to be last because we need to do the left and the right subtree of the root node before we can mark that down. That is the post order traversal okay. So those are the three different types of traversals. In order preorder post order, you should be able to look at a tree
1:45:38
and perform any one of those traversals by remembering this order. Okay, so it's process, process and visit. And the order of that is what's switched around. So in the inorder traversal you are processing left visiting processing right in the pre order you are visiting, then processing left, then processing right. Then the post order you're processing left, right and then visiting. Okay. So those are kind of the three combinations that we have. All right. So moving on here
1:46:03
we have various types of binary trees each of which have different properties. We have a full binary tree complete binary tree, balanced binary tree and perfect binary tree. Let's look at the different types okay. So full binary tree A full binary tree is a binary tree in which all of the nodes have either 0 or 2 children, meaning only leaf nodes have no children. Okay, so have a look at these three trees here and try to determine if they are full or not based on this definition.
1:46:29
Again, this means that we can only have 0 or 2 children for every single node. So let's look at this first one right here. So this node has two children okay. That checks this node has two children okay. That's okay. This node has no children. That's fine. This node has no children and this node has no child children. Sorry. That means this is okay. And this is a full binary tree. All right. Let's move on to the next one. Is this one full or not okay.
1:46:54
So here we have a node has two children. That's fine. Here we have a node only has one child okay. Let's not find this means this is not a full binary tree okay. Moving on to this one. Is this a full binary tree? Well this node has two children. That's okay. This one is two. That's okay. This one has two. That's okay. The rest of them only have one, which means yes, this is a full binary tree. Okay. So that is full binary trees. All right. So now we move on to complete binary tree
1:47:20
a binary tree is said to be a complete binary tree. If all of its levels except possibly the last level, have the maximum number of possible nodes and all of the nodes in the last level appear as far left as possible. Okay, so there's two pieces of criteria. First of all, all levels except the last have to be full of nodes. Okay. Have the maximum number of nodes. And if we have any, any nodes in the last level, they have to be as far left as possible. So have a look at these examples
1:47:43
and try to determine if they are complete or not okay. So example one. This is a complete binary tree. The reason is a complete binary tree is because we have all levels except the last filled. So this has two nodes. So it's a filled level and the nodes it exists in the last level are as far left as possible. Okay. Moving on to the next one. This is a complete binary tree. The reason it is complete is the same reason this one is complete. These levels above the last level are filled.
1:48:09
And then we have one node that is as far left as it could possibly be. If this node was the right child of node two, it would not be a complete binary tree because the node would not be as far left as possible. Okay, moving on to the last one. This is not a complete binary tree. That is because even though this level is filled here, the last level we have, node five is the right child of node three, meaning it's not as far left as it could possibly be. So this is not complete.
1:48:34
Now let's actually just go back to the previous example, and let's look at these trees and determine if they are complete or not. So tree one this was the same as before. So that's complete tree two yeah same one as before. So that's complete as well. But what about this tree. Is this complete. Well having a look at this we can actually see that no it is not complete even though everything is as far left as it can possibly be.
1:48:53
The reason why it's not complete is because this level here is not filled. Okay, we need to have two more nodes on node three here. For this to be a complete binary tree. All right. Let's now move on to the next one which is a balanced binary tree. Now a binary tree is said to be balanced binary tree. If the height of the left and right subtree of any node differ by not more than one. So the way you actually check for a balanced binary tree is you look at the left and right
1:49:20
subtree of every single node, and you see the height of that tree. Then you take those two heights, you subtract them by each other. And if the absolute value of that height is less than or equal to one, then it means that it is balanced. If it is greater than one, it is not balanced. So it's better if we just go through examples rather than try to look at the definition. So let's look at example one. Is this balanced? Well the way we do this is we start by looking at node one.
1:49:43
And we look to the left and to the right. We check the depth of the left tree and the depth of the right tree, or the height of the left in the right tree. So in this case, the height of the left tree is two okay. Because we have two elements and the height of the right tree is one. All right. Or you could say one and zero, like the height of the tree rooted at two is one. And the height of the tree rooted at three is what he called zero. So you can kind of say it in any way that you want,
1:50:07
as long as you do it the same across both the left and the right side. So when we take the height of the left and subtract it by the height of the right, we get negative one or we get one, depending on how you do subtraction. Anyways, that's within our range here. So that means this is balanced okay. So this is a balanced tree. Next we have this one here. So we look at our root node and we look to the left. To the left we can see we have a height of two okay. We have two elements here.
1:50:33
And to the right we see we have a height of zero. So that means if we take two we subtract by zero we get two. That means that we have a difference of two. So this tree is not balanced. Okay. Moving on to our last, side right here. Is this a balanced tree? Well, at first glance it might look like it is. The reason for that is that we have three nodes on the left side and two nodes on the right side. Three minus two is one. However, this property needs to apply for every single node, right?
1:50:59
So if I now go here to node two I see I have a height of two on my left subtree and a height of zero on my right subtree, meaning that this is not balanced. Okay, not just because the root node is balanced makes the whole tree balanced. You have to balance every single node. Hopefully that makes sense. Again, when we look at node two here, we have a height of two on the left side and a height of zero on the right side, making this not balanced. All right.
1:51:22
Now let's move on to the last example or last type. Sorry, which is the perfect binary tree. Now a binary tree is said to be a perfect binary tree. If all levels of the tree are full of nodes. So really, that's exactly what you see right here. Okay, this is a perfect binary tree because every single level is completely filled. If we're missing any of the nodes here, then that would mean that this is not a perfect binary tree. This is probably the easiest one to determine.
1:51:45
Okay, so those are the different types. I'm not going to tell you that you necessarily need to memorize every single one of them, but it can be important to know what type of tree you're working with. Because if you know that, you can assume some things about the tree. For example, if we're dealing with a perfect binary tree, then we know how many nodes are inside of the tree. Given the height of the tree, or given the number of nodes, we can figure out the height of the tree.
1:52:08
You see what I'm saying here? If we know certain aspects of the tree, there's certain other aspects we can imply about it and that we can know to be true with a perfect binary tree, we know that the number of nodes in the tree is going to be, two raised to the exponent of the height of the tree plus one minus one. Okay. In this case we know the height is two. So we take two. Raise it to the exponent three because we have two plus one right h plus one. That's going to give us eight. Subtract one.
1:52:34
That's seven. We know there's seven nodes inside of this tree a likewise if we know that there's seven nodes then we can actually do the reverse. And we can determine that the height of the tree is two. Okay. There you go. That is all I wanted to share with you about binary trees in the next video, we're going to talk about a binary search tree, which will allow us to actually have some more performant operations when we are searching for deleting or inserting different elements.
1:52:58
With that said, I hope you found this video helpful and I look forward to seeing you in the next one. Hello everybody, and welcome to the next video. In this section we will be discussing binary search trees. Now a binary search tree is a special type of tree that has an additional property on it. This property is that any time we have a node, all of the values that are in the left subtree of that node are going to be less than that node itself, and all of the values
1:53:24
that are on the right subtree, or in the right subtree of that node are going to be greater than that. Now, we do need to handle the case in which we have values that are equal to each other. If that's the case, you can decide to put those values on the left side or on the right side. But you can't decide on both. Okay. So you need to pick is it going to go to the left or is it going to go to the right in this situation or for this video sorry,
1:53:44
we're just going to use values that are all unique to make things a little bit simpler for us, but you do need to handle the case in which you have values that are the same, right? So if I have another three, then we could maybe put this on the right side. But that would mean I can't have that on the left side. Okay. Hopefully that makes a bit of sense. But essentially all of the values that are less than a value are in the left subtree.
1:54:04
And all of the values that are greater than the value of a node go in the right subtree, that is the binary search tree. So let's draw out a simple binary search tree. And then we'll talk about some different operations and why we would actually want to use something like this. So let's say we have our root node of four. This means anything in the left subtree of this node has to be less than. So maybe we have a node like two. And then we have a node like three. Now notice what I've done here is
1:54:30
I've placed the node three as the right child of the node two. The reason for that is that node three is less than four. So it's okay to be in the subtree. The left subtree of this node. Here. However, it needs to be on the right subtree of node two because it's greater than value two. Okay. We can come here. We can add one. Now on this side maybe we have value say like eight okay. And then maybe we have a value like six a value like seven. I'm just drawing out a few different values here.
1:55:01
So we kind of get the idea of how this works okay. So this is an example of a valid binary search tree. The reason this is valid is because every single node satisfies the properties that I discussed. We have only values that are less than the node value in the left subtree, and only values that are greater than or equal to the node value in the right subtree. Now, having this type of binary search tree structure allows us to efficiently search for, add and delete different elements.
1:55:31
The reason for that is that we know this property. We know that elements are either less than or greater than, depending on their position in the tree, so we can more efficiently search through the tree when we're looking for a specific element. So in this case here, let's say that we want to find if the element ten exists inside of the tree. Well, with any other binary tree, since we don't know this property, we would have to look through every single element
1:55:54
inside of the tree to attempt to find ten. However, in the binary search tree, we don't have to do that. What we can do is we can start at our root node, and we can compare the value that we're looking for to the root node. We know that it's greater than. So that means that we can move to the right. So now we have the element here on the right which is eight okay. Now we moved to eight. And now we can say okay is this equal to ten. No it's not.
1:56:17
So what do we need to do. Well ten is greater than eight. So we're going to look in the right subtree of eight. So we come here and then we find ten. And we now have found the element. So rather than having to look through potentially every single element in the tree, we only had to look through three different nodes. Now the time complexity of searching for an element inside of a binary search tree is big O of H, where h is the height of the binary search tree.
1:56:43
Okay, in this case, the height of the tree is going to be three. That is because the furthest depth or highest depth that we have is three. So whatever the furthest possible depth is, or I guess the highest depth in our tree, that's the maximum number of operations it will take us to find any given element inside of a binary search tree. Hopefully that's making sense, but that is the basics on a binary tree or binary search tree I should say. All right.
1:57:08
So now that we've looked at searching a binary tree, let's look at inserting some elements. And then we'll look at some pseudocode to do both of those operations. So let's say we want to insert the element of I don't know let's go with five inside of our binary search tree. Well we need to place this in the correct location such that our binary search tree satisfies the correct properties. Now, the way we do this is the exact same way
1:57:32
that we actually search for an element inside of our binary search tree. We take our node five and we start moving to where node five would be in the tree. And then we simply place it there. So we compare it to the root node we say is a greater than or less. Then if it's greater, then we move to the right subtree. We look at the right subtree and we say is a greater than or less than. Okay, well it's less then. So we move to the left subtree.
1:57:55
We look at this and we say is a great but a less then it's less then. But in this situation there's no left child node of this node right here. So all we do is we simply add this node in as the left child. Okay. So as soon as we find a situation where we're going to move into a subtree, but that subtree doesn't exist, i.e. there's no node there, we simply place the node that we're trying to insert in that position. So this is where five goes.
1:58:20
And you can do this example with really any type of numbers you want. If you try to do negative one then you're going to go to four. Here you're gonna go to the left subtree, left subtree. And then you try to go the left subtree. It doesn't exist. So you simply place negative one here is the left child of that element okay. So that is the binary search tree insertion. Now let's create a binary search tree and do multiple insertions.
1:58:41
And then we'll look at a few pieces of source code or not source code I guess. But just kind of pseudocode for doing these operations okay. So let's say we have the elements 473, two, one and four. Now what I want to do and actually let's not make this forks I don't want have the same element. Let's go with eight here. Let's try to create a binary search tree here by inserting all of these elements into the tree. Now when we don't have any elements in the tree,
1:59:05
the first element we insert just becomes the root. And if you'd like, pause the video and attempt this on your own and see if you can figure out what the binary search tree would look like. If we insert elements in this order, I'm going to start drawing it out now okay. So we start with our root node of four. Then we go to insert node seven. When we insert seven we know we need to make that the right child of four because there is no right child.
1:59:29
And this is greater than node with value four okay. So now these two are done. Now we're on node three. Here we want to insert node three. So that's going to go and be the left child of node four okay. Now we need to insert node two. So that's going to be the left child of node four. And then left child of node three. So two comes here. Now we need to insert one okay. So we go left left again and insert one. That's going to be the left child of two I apologize. That messy drawing.
1:59:57
And then we have eight. That's going to be the right child of seven. So we're going to place that there okay. That is that binary search tree. Let's do another example here. So let's do maybe something like seven for 259631. And I don't know let's go with eight okay. Let's see what this binary search tree would look like. So let me just draw the numbers out here. We're going to have seven. We're going to have four. We're going to have two. So cross those off. We're now going to have a five.
2:00:31
The five is going to go over here because we have to go left and then right okay. Now we're going to have a nine. So nine is going to come over here. Now we need to have a six. So six is actually going to be sorry. Not on that side but over here because it's less than seven. But it's greater than four and it's greater than five. So it needs to be placed over here okay. So that's those done. Then we have a three. Our three is actually going to go here because it's less than seven.
2:00:57
It's less than four. But it's greater than two. So it needs to go there. Then we have a one. One is going to go over here and be the left child of two. And then we have an eight. It's going to be the left child of nine okay. So that's what this binary search tree would look like. Go through this practice. You can kind of write out a bunch of numbers for yourself and try to create what the binary search tree would be. Obviously, I can do this quite quickly because I've done it many times before,
2:01:18
but you're just looking and seeing, is it less than or greater than and then placing it in the correct order? Okay. So that is the binary tree insertion. Now when we do that insertion, just like when we have the search, this is going to take a big O of each time. Now the reason it takes big O of time is because we simply need to search for the location where we want to place it, which takes big of H time, and then place it in that location. Right?
2:01:41
So it's really the exact same rationale as why the search takes big O of time, because we are going at most whatever the depth of the tree is. Now, one thing to note here, let me just erase this. Is that how efficient the operation is going to be is based on the height of the tree. Now, that means that the order in which we insert elements in our binary search tree is going to affect the height, and that can affect the time complexity of the different operations that we're doing.
2:02:06
So when we look at a binary tree right, we could potentially have every single one of the elements on the left subtree, or every single one of the elements on the right subtree. Just because we're using a binary search tree doesn't necessarily mean that our operations are going to be faster, because if we insert, items in kind of an inefficient order, then that means that we're going to have a bunch of items that are all kind of in a linked list structure.
2:02:31
So imagine we have a binary search tree, but there's no right trees at all. We only have left subtrees here. If that's the case then H is actually going to be equal to approximately n or n minus one. In this case where n is the number of nodes. So even though yes, the time complexity is still Big-O of H, it actually ends up being big O of N because we have to look through every single node, potentially whenever we're doing some kind of operation with the binary search tree.
2:03:00
So that includes searching as well as inserting. And we're going to talk about deleting in a minute. Hopefully that's making a little bit of sense. But I just want to be clear here that it's big O of H. And it's important that we're using H here, because that can represent a binary tree that has a very small height, which is great for us. That means we have very fast operations or a binary search tree that has a very, very, high height. Right. That is almost n minus one.
2:03:24
Okay. So let's erase this. And I'm just going to kind of explain this one more time and show you the advantage of the binary search tree when we have it relatively balanced. Okay. So in the previous example I kind of explained to you the worst possible situation for the binary search tree, which is we have this kind of linked list structure of all of the different elements. However, we can have a really, really good situation where we have a balanced binary search tree.
2:03:47
Now, we can't ensure that we're always going to have a balanced binary search tree. Well, there is a way to do that, but I'm not going to talk about that in this course. It's a little bit more advanced. There's things called self-balancing binary trees. They have some fancier names as well. Anyways, we're not going to get into that. But if we do have a balanced binary search tree, that means our time complexity actually gets really, really good for operations. So let's say we have a tree here.
2:04:09
Okay. Let's kind of just draw this out a little bit.
2:04:12
And I'm going to get 15 nodes inside of this tree okay. Now this is going to be a perfect binary tree. And it's also going to be a balanced binary tree. It's also a full binary tree. It's pretty much all of those ones that we talked about in the last video. Okay. So in this case if we have a balanced binary search tree and we are searching for a specific element, well the time complexity is still big O of H. But in this case, since we know the tree is balanced,
2:04:39
we can actually say that the height of the tree is equal to the logarithm base two of n, where n is the number of nodes in the tree and the number of nodes. I mean, we can calculate with height as well. We need to know one of them either the number of nodes or the height. Regardless, the reason this is important is because that means as our binary tree gets larger and larger and larger, the height doesn't increase at the same rate
2:05:02
that the binary tree nodes increase, it increases logarithmically. So in this case,
2:05:08
if we take the log base two of 15, which is the number of nodes that we have, we get approximately 3.9, right? If we look at the number of operations we need to do to find a node in the tree, it's about four. Okay. So we look here 12I guess this would be two sorry three and then four okay. So we have to look through four different nodes at most going through three different edges to be able to find the node that we're looking for in our binary tree.
2:05:34
So that's the same for insertion as well as searching. We have the log base two of n as that kind of time complexity operation. Now again this is only the case when we have a balanced binary tree. If we don't have a balanced binary tree, then we can't imply this because we could have very, very large paths here that we have to go through. And in that case, we still want to represent this with big O of H. But the point of me telling you this
2:06:00
is that with binary search trees, typically H is going to be less than N, I mean is going to be less than n, but typically it will be much less than n. And if that's the case, then you get a way better time complexity operation for searching, inserting and deleting, which I guess we can get into now. Okay, so at this point you should understand the main property of a binary search tree, and you should know how we insert elements into the binary search tree
2:06:24
and how we traverse the tree and look to see if a specific element is inside of it. Now I want to talk to you about deleting an element in a binary search tree, which is not trivial. And then I'll start writing out a little bit of code and showing you how we would kind of go through the tree. Again, this is not going to be a comprehensive overview. This course is not meant to go into everything related to data structures and algorithms, but I want to give you a solid foundation. Okay.
2:06:46
So let's create a binary search tree. Let's have node seven. Let's have four. Let's have 5312 okay. This can be ten 911 and then eight. And actually let me just redraw my eight year because that's a little butchered. All right. So we have a binary search tree here. And let's say that we want to remove an element from this tree. Well there's three possible cases that we have when we want to remove an element. The first case is that we want to remove a leaf node.
2:07:19
Now just like we saw with our regular binary trees, if we want to remove a leaf node, that's quite simple, we just remove the reference to that node from the parent of that node. Okay. So case one very straightforward. And we can do this deletion of the node. And again big O of each time. Now the reason that's going to take big of each time is because we first need to locate the node. We need to then get the parent of the node and then simply remove that reference okay.
2:07:43
So to locate the node we know we can do that in big O of each time because we will go through the tree in that traversal structure that I already showed you. Okay. So that was case one. We can kind of put a checkmark here for case one where we're deleting a leaf node. That's very straightforward okay. So now that we've handled case one let's move on to case two which is when we're looking at a node that only has one child okay. So case one is no child. And this is one child okay.
2:08:12
So when we're looking at a one child node that we want to delete, an example of that would be node nine. Now how do we delete node nine. First of all we can't just cut this right here. The reference to node nine like we would with the leaf node. If we do that we're going to lose access to any of the people or any of the not people. Sorry children of this node. So in this case it only has one child. It could be the left child of the right child.
2:08:34
Either way, we'll lose access to that entire branch coming off of this node. And we don't know how far down the tree that goes. So how do we do this? Well, first thing we need to observe is that anything that's in the left subtree of the parent of the node that we want to delete is going to be less than that parent. Okay. So important property to understand here. So we want to delete this node. But we're going to get access to the parent node which is ten.
2:08:58
And again anything in the left or right subtree of this node, since it has a parent of ten is going to be less than this parent. All right, because it's in the left subtree. And then same thing. If it was in the right subtree we know it would be greater than. So in this situation all we actually have to do is we have to take the parent node's left pointer and change that to be equal to the left pointer of the node we're going to delete.
2:09:24
So I simply change the pointer here for ten and then delete this reference. And now what happens is since there's no reference to this node nine, node nine ends up getting deleted. And now the binary search tree property is still satisfied. Again, the reason this worked is because anything that's in the left subtree of this node is going to be less than. So I can change this to anything that this child points to. So let's switch this example up a little bit more just to make it a bit more clear.
2:09:52
So let's say this is 11 okay. This will be 12. And then let's change this to be eight. And then this here can be nine okay. So if this is the case the exact same thing happens if we want to delete node eight. So we want to delete this. So what we do is we find the parent and we simply change the parent left reference here to be equal to whatever this was pointing to again. And only has one child. This is why this is working. So that gets rid of this.
2:10:20
And then if this had a subtree down here, that would still be maintained. Right. And again, that works because of the reasons that I've stated I won't repeat myself, you know, the fifth or sixth time here. You get the idea though. Okay. So that's how you delete it. If it has one child now this works. If it's the left child or the right child. And let's just have a look here. If I want to delete node 12, this works the same way, except this time
2:10:42
I'm going to update the parent's right pointer, not the parent's left pointer. So essentially what the algorithm is, is find the parent of the node that we want to delete. Figure out if the node is the right child or the left child of this parent. In this case, we know that it's the right child. And then point the parent's right pointer to whatever this node's single child is. So in this case, the only child is 13. So we just change the pointer to be here, remove that.
2:11:09
And now 12 gets deleted okay. So that's case two where we have one child. But case three is when we have two children. All right. So moving into case three things get a bit more challenging obviously because we have two children. So either of the approaches that I just showed you don't work. So for example if we're looking at node 11 I can't use approach one or approach two because there's just no way to do that when we have two different children. So the main thing we need to think about here
2:11:35
when we're trying to solve this is how do we maintain the property of our binary search tree when we do this removal? Well, there's two ways to do this. The first way is to locate the maximum value in the left subtree, or the minimum value
2:11:55
in the right subtree. So we can pick either of these either the maximum, the left, or the minimum of the right. Swap the value of whatever this is that we find with the node that we're trying to delete, and then delete that value that we found using case one or case two. Okay. So let's look at this. The maximum value in the left subtree would be nine. All right. The reason why we're looking for the maximum value is because we need to maintain the binary search tree property.
2:12:24
I can't find the minimum value because if I found the minimum value. And then I were to swap this here, we now break the binary search tree property because nine is going to be greater than eight. So to find the maximum value in the left subtree we're just looking for the node that's the furthest right. Now the furthest right node here is going to be nine. Now notice that the furthest right node will never have a right child okay. So if I have another node here like ten.
2:12:48
Now this is the furthest right. And it doesn't have a right child. If it had a right child, then whatever node was the right child would be greater than the node that I was just looking at. So that's an important property, the maximum value in the left subtree. So the furthest right node never has a right child, which means it has at most one child and it could have none. So in this case we find nine. Now when we find nine, what we're going to do
2:13:11
is take nine's value and we're going to copy that to node 11. Then we're going to delete node nine. Now, since we know that node nine is either a case one or case two has no children or has one child, we can delete it using the methods that I just showed you. So to delete node nine all we're doing is setting the parent node, which is the node that we're actually swapping conveniently to be pointing to the node the node nine was pointing to. So in this case we just get eight.
2:13:37
So if we were deleting 11 this was one valid way that we could go about deleting it by searching for the maximum value in the left subtree, then essentially copying that data to the node we want to delete, and then deleting that node, because again we can delete it because it's in case one or case two. I know this is complicated. This is probably the most complicated algorithm we've looked at this far, but hopefully this is making a bit of sense.
2:13:58
Okay, so now how do we delete the node using the second approach, which is finding the minimum value in the right subtree. Well again the same thing applies here. We need to find the minimum value. Now the minimum value in the right subtree is going to be the node that's the furthest left. Now in this case the node that's the furthest left left sorry is 12. Now if this node had any left children. So it had like a value like 11, then this would be the minimum node.
2:14:23
So same thing applies kind of in the reverse order here on the right side, the node that's the furthest left or the minimum node will never have any left children okay. So we know that we're going to be in case one or K0 sorry. Case one or case two is what I meant when we grab this node and attempt to delete it. So in this case we find node 12. So we swap this here to be 12. And then we delete node 12. Now since node 12 has one child, the way we delete it is the same way
2:14:50
we just deleted the other node. So we simply set the right pointer of this node to be equal to 13. So now we have deleted node 11. So both of those deletion processes are valid again either using the maximum in the left or the minimum in the right. And now we have a valid binary search tree. And you can see that the properties are still adhered to with all of the nodes that are less than being in the left, and all of the nodes that are greater than or equal to being in the right. Okay.
2:15:17
So that is how you do an insertion deletion. And what do you call this here? Traversal of a binary search tree. Now how long does this operation take to run. Well this is also going to take big O of each time. Now there will be some additional steps that we need to perform here. Essentially, the first thing we need to do is locate the node. And we also need to locate the parent of that node. Now locating that node will take us big O of each time.
2:15:40
And then deleting that node is going to involve finding the maximum on the left or the minimum in the right, subtree. Now, to do that, we'll take us another big O of each time because for example, we could be deleting the root node. If that's the case then we need to locate whatever the node is in the left subtree or the right subtree, which could take us again up to big O of each time. So if we're kind of writing this out more formally,
2:16:03
we have one time operation to locate the node that we want to delete. Then we have another time operation to locate either the maximum node in the left or the minimum node in the right. And then once we do that, the deletion operation will happen in big O of one or constant time. Okay. So that means that we have two H. We can reduce the two here. And that gives us a big O of each time complexity for performing the deletion in a binary search tree. All right.
2:16:30
So with that said we're going to wrap up the conceptual aspect here. And I want to look at just a little bit of code for how we would actually search a binary search tree okay. So let's do a simple example. You're just writing the code to traverse through the tree just so you have that under your belt. So let's do a simple example here. We'll have 321. And then something like five four and then seven okay. Now this is our root node. And let's say
2:16:59
we want to traverse through this tree and find if a node exists inside of the tree. Well how would we do that. Well the way that we would write this algorithm is we'd essentially have some value, which is the target value that we're looking for. So in this case we can actually refer to this as the target okay. Now in this case we can say the target is equal to something like seven. Doesn't really matter. Now what I'll do is I'll write an algorithm where we'll start
2:17:22
and we'll say the current node is equal to the root node. We're then going to say, well the current node does not equal null. We're going to loop okay. We're going to first check and see if the current node value is equal to the target that we're looking for. If it is then what we want to do is simply return the current dot value or not value. We can just return that node itself doesn't really matter. We can return the node. We can return true.
2:17:57
I'm just trying to indicate that in this situation we did find the node. Okay. Now if that's not the case then we can have another if statement here. And we're going to compare the value of the current node that we're on to the value of the target node. So we're going to say if the target is greater than or equal to the current value then current is equal to current dot. Right. Because we're going to look in the right subtree. Now we know that this operation will be okay
2:18:26
because the current node is not equal to no. So we can access the right subtree. And if the right subtree is null, then that means that we don't actually have this node in the binary search tree. Okay. Then we'll have another if and we'll say if the target is less than the current dot value, then we're going to do the opposite. We're going to say current is equal to current dot left okay. So that's our entire algorithm. This will actually be able to locate any node for us
2:18:53
in the binary search tree in big O of H time. So let's run through a quick example here where we're looking for the target seven. So when we're looking for target we start and the current node is equal to three because we're looking at the root node of the tree okay. We say is the current equal to no. Well no it's not. So we're going to continue to loop. So we check this first if statement. And we say is the current value equal to the target value. No it's not. So we move to the next
2:19:17
if statement we say is the target value greater than the current value. Well it is because seven is greater than three. So that means current is equal to current out right. So now the current node becomes equal to five because that's the right node from the current node okay. Now we repeat this process again. We say while current does not equal no okay. So it's not know is this equal to the target. No it's not okay. Is the target greater than the current value. Yes it is.
2:19:41
So we move to the current node right. Which is going to be seven okay. So now we check is the current value equal to the target. Yes it is. So we return current okay. So that is the binary tree pseudocode for searching through a binary search tree. And sorry I kind of said that weirdly. But you know what I mean. That's the code for actually doing the traversal of the binary search tree in Big-O of each time. Now, I'm not going to ask you or even show you here how we do
2:20:09
the insertion or deletion in a binary search tree. But if you want to test yourself and write an algorithm that does that, go ahead with what I just showed you. You know, conceptually what needs to be done and you need to kind of problem solve and figure out the code that you would need to write. Obviously, you can access a ton of resources online that would just tell you what the implementation is. But I'll tell you that
2:20:28
if you want to do an insertion or kind of like a creation of a binary tree, then what you need to do is you need to find where you're going to insert that element, which will be done using something like this. And as soon as you get to the situation where you're about to set the current equal to the current right for the current, equal to the current dot left, you simply check does this current node have a right node? If it doesn't have a right node, then that means that you're just going
2:20:52
to set the right node to be equal to the node that you're inserting. And if it doesn't have a left node, then you're setting the left node to be equal to the node that you're inserting, because you just found the position where this element needs to go. Hopefully that makes a bit of sense, but you can kind of test that out on your own and try to write the code. And then if you want to test that code, you can run through it, just like I was doing here, and see if that actually works, to construct
2:21:13
a binary search tree that has that binary search tree property. Okay, with that said, I'm going to wrap up the video here. I hope you found this helpful. I look forward to seeing you in another one. Hello everybody, and welcome to the next video in this section where I'll be discussing heaps. Now, a heap is another non-linear data structure that allows us to access either the minimum or maximum value out of some collection of elements in an efficient time complexity.
2:21:39
Heaps can be useful when we constantly need this maximum value or minimum value, and we can actually use heaps to do things like sorting. I'll talk about that more later in this video, but for now, understand that we have two variants of a heap. We have a max heap or a min heap. Now there's a bunch of other versions as well, but for our case, we're just going to concern ourselves with the max heap and the min heap. Now, the minimum heap is going to allow us to access the minimum value,
2:22:03
and the maximum heap will allow us to access the maximum value. Okay. So when we draw out a heap, it's going to end up looking something like a binary tree. So let's say I have a value like seven here. Now first of all this is going to be a max heap okay. It's important that, you know, if we're using a max or min heap because that's going to change the structure of the heap. So to the right of seven we can have a value say like four to the left maybe a value like three. Here we have one, two.
2:22:32
And for now we'll just leave it at that a very simple max heap. Now the property of a max heap is that every child node of one of the nodes that we have here needs to be less than that node, whereas with a min heap it's the opposite. So with a min heap all of the children need to be greater than that node. Now what that means is whenever we look at any single node here, we can treat this node just like a smaller version of the heap itself. What I mean by that is that this node here is a heap.
2:23:01
The reason it's a heap is because every single node that's a child of this root node, if we're looking at this one here is less than this node okay. Same thing would apply over here. Over here. You get the idea. Hopefully this makes a little bit of sense, but essentially every single node that we have here needs to have a node that is less than it as one of its children. Now it doesn't matter if that node's the left child or the right child,
2:23:25
but the way that we create a heap is that we'll always be creating a complete binary tree. Okay, so notice that as I kind of created this heap here, I didn't randomly go off and add a value on this side. I did it in level order. So that's exactly what will happen when you are making the heap. And that's actually important for the implementation of the heap, which we'll talk about later on. Okay. So that is a max heap. Just to give you an illustration of a mini.
2:23:50
Let's draw another one on the right side of our screen. So let me just move this over so I have a bit more space. So for the min heap we would have value like one as our root. Because this is the least value or the smallest value in our heap. Then we would have values that are greater than one on the right hand side. And then again we need values greater than these values to be to the left and to the right of them. Sweet of value. Like for
2:24:13
and like five and maybe a value like six. Now I'm just kind of going in numeric order here, but you obviously won't necessarily have kind of perfect values like I have here. Okay. So this is a max heap and this is a min heap. Again in this situation all the values that are children of these nodes are greater than the node itself. Okay. So that is the basics on a heap. Now let's actually talk about how we would implement a heap and some of the kind of operations that we can do on it. Okay.
2:24:43
So let me erase all this and let's create a heap. So when we make a heap well we're actually going to use is an array. Now the reason we can use an array to implement our heap is because we know that we're going to be creating essentially a complete binary tree. Now, since we have a complete binary tree that allows us to assume some properties about the structure of our heap or the structure of our tree. And that means that we can actually utilize an array.
2:25:10
So let me show you what I mean by this. Let's just make an array kind of at the top of the screen here that has a few different slots inside of it. And then let's insert some elements into kind of like a tree structure. And I'll show you how we would represent them using this array. So let's just write out the indices here because we'll need these in one minute. Okay. So let's create a heap. In this case we can do a max heap. So I can have a value like seven
2:25:36
for 632
2:25:43
and then one. Okay. So a valid max heap again because all of the children are less than the node that they have as a parent. Okay. So how would we use this array that we have right here to represent this heap. Well the way we do this is we place our root node into index zero. Okay. So root node goes here. And then we're just going to place all of the nodes in the level order traversal here in the positions in our array. So we're going to have four because that's the next node that comes.
2:26:09
Then we'll have six. So six goes here. Then we'll have three okay. Then we'll have two and then we'll have one. So visually it should be very easy for us to actually kind of see how this works. In the first section of our array we have one element. And that represents the first level of our tree for the next two elements in our array. That's the next two elements in our tree. And then the next four elements in our array would be the next four elements in the tree.
2:26:37
Now using this array like structure allows us to make a lot of inferences about how we actually reference our find the children or parents of different nodes. So let me just move this over here so I have a bit more space. Okay. So let's say we're looking at this node right here. So index one in our array. And we want to find the children node of index one. So in this case that's value for now. Obviously if we're visualizing the tree it's easier for us to do that. We can see that's three and two.
2:27:04
But how do we do this mathematically if we couldn't actually see the tree. Because obviously our code is not going to be able to visualize some tree here, it's going to have to use this array structure that we're using to implement the heap. So if I'm looking at four here, the way that I find the children is I use the equation of the following. I say that the left child. So actually let's do an uppercase L here. And this is going to be two I plus one.
2:27:30
And then the right node is going to be equal to two. I plus two where I is the index of the node that we're looking at. So anecdotally let's just have a look at this. Here we have index one. We can pass that into the equation here. So we're going to get two times one which is two. And then plus one which will give us index three. So L in this situation if we're plugging in our value I gives us three. And then over here for R that's going to give us four.
2:27:57
Now if we look at index three and index four here inside of our array we see element three and element two which are the child elements for index one or element four. Okay. So this is the equation that you can use to determine the children for any given node. Now the reason this works is because we know that we have a complete binary tree. Meaning there's no kind of gaps in our tree. And we have two children for any given node.
2:28:25
So you can kind of go through this and you'll see how it works. Right. So if we're looking at the root node and we're finding its children well this is zero. So two times zero zero plus one gives us this. If we have the right note here that's two times zero which is zero plus two gives us two. Now you just continue this process throughout the array. And you will always find the correct child for any given node. So kind of an important thing to understand here since again
2:28:48
this is a complete binary tree and we know we're filling it from left to right, we can always use this equation here to determine the left and right child of any given node in constant time. Now in addition, we have the next equation which is p standing for parent is equal to and this is I minus one divided by two. And then this is a math.floor okay. So let's just plug this in and we'll see why this works. So if we're looking at five here well we plug in five.
2:29:16
So five minus one over two that is equal to two. And then we don't need to round this. But if we were rounding it then we would just floor this. So when you see these brackets here that stands for floor which just means round down okay. So that's with the left child. We'll see an example with a right child if we're looking at index four here okay. So we take four minus one. That gives us three over two gives us 1.5. We floor that right. And then that gives us element four here
2:29:44
or index one which is the parent for this node. So for any given node we can figure out the left and right child of that node. And we can figure out the parent of that node, specifically the index of those elements or nodes in our array. So that's why we use an array for this heap data structure. Now that we understand kind of how we represent the structure using the heap, and we have a way to go from any given node to its children node
2:30:10
as well as from any node to its parent node, we can start looking at some different operations that we can perform on the heap. So the first thing we should look at is what happens when we're building a heap or when we're inserting elements inside of it. Then we will talk about how we delete elements or access the maximum element from it. So let me erase this and we'll start a fresh example here on the screen okay. So I'm going to do a bit of a smaller array here.
2:30:33
So we have some more room to draw. And we'll have a few slots here inside of the array okay. Now let's say that for this example we're doing a max heap. All right. So we have our array. This is going to be a max heap. Now let's try to insert some different values into this heap and see what would happen. So let's start by just inserting one. When we have no elements inside of our heap this is quite easy. We're just going to add this as the root node for our heap.
2:30:59
So we can just kind of make that the root right there okay. Next let's say we want to insert four. And actually let's insert a larger value. Let's insert something like ten. So when I insert ten what I'm going to do is I'm going to place that as the last element inside of my array. So just the next kind of space to be filled, that means that ten right now will be the left child of one. However, the max heap property is not satisfied right now because every node has to have values
2:31:26
that are less than it being their children. So what that means is I actually need to shift up this ten node. So it now becomes the root node, and then one becomes the child node. So the algorithm here is we simply take the node. We insert it at the end of the array. And then we look for the parent of this node. We then check the value of the node we're inserting with the value of its parent. And if the node that we're inserting is greater than the value of its parent,
2:31:52
we do a shift up operation, which essentially means we just swap the values. So that means that now ten will become the root node. So let's draw that in here. And one will become the end node or the leaf node. Let me just put this in the center okay. So now let's say we're inserting the value for okay. So I want to insert for I put that at the end of the array. Now that means that right now it's going to be kind of represented as the right child of ten.
2:32:22
What I do is I look at my parent node which is ten, and I say, okay, am I greater than or less than this while I am less than this, which means there's no operation I need to do because the heap property will be satisfied. Perfect. Now let's say we want to insert three, so I insert three at the end. That means three is kind of now here, right? And then I need to check the parent node of three and see if I'm greater than the parent node.
2:32:46
So just to recap here by the way to find the parent node for this element in the array we would have done P which is parent is equal to. And then this is going to be three minus one over two which is going to equal one. So this will be the parent node. So that's what we're comparing to okay. So now we need to perform our swap because we see that we are greater than that. So we have three and one which now means we do the swap. Here we have three and one okay. Now we continue the process.
2:33:11
So now let's insert the element 11 okay. When I insert 11 here now the same process is going to continue I need to check the parent node. Now in this case we know the parent is going to be three. So I have 11 here.
2:33:24
And I check the parent node. I obviously am greater than the parent node. So what I need to do here is shift this value up and swap it with the parent. Okay. So I do that. So now three comes here and 11 comes here. However I'm not done yet. And the reason I'm not done yet is because at this point I actually need to now check the parent of this node and see if I need to continue shifting this value up in my binary heap or in sorry, this heap. It's kind of referred to as a binary heap
2:33:52
because we have two children nodes, we can have three, four, etc. children nodes as well. In this case we're just doing two. All right. So again we're now here. We've done this first sift up operation. But since this node still has a parent node and we haven't yet checked that, we now need to check that parent node. So we now check the parent node. We see it's ten. And that means we do actually need to do a swap. So now we're going to swap this. So this becomes an 11 and this becomes a ten okay.
2:34:17
So let's rewrite this in our array. So we have ten and 11. And now the binary heap property is satisfied where every single node has values that are less than it in the heap. Okay. Let's do one more just to make sure we're clear. Let's insert 12. So we insert 12 at the end of the array. So currently 12 is here. Now we check the parent. Well how do we get the parent. Well we take five minus one over two which is equal to two. So that means the parent is four. So we now compare to four.
2:34:46
We say we are greater than four. So we do our swap here
2:34:53
okay. So this is now 12 and this is four. So four and 12 okay. Now we're not done yet because this node has a parent. So we now need to compare to the parent node. We see that the parent node is 11. That means we are greater than the parent node. So again we do the swap here. So now this becomes 12 this becomes 11. So we come here 12 and 11. And the binary heap property is still satisfied. All right. So that is essentially how you create or insert elements into a heap. All right.
2:35:24
When we do an insertion we simply add it as the last element. And then we sift this element up in the heap by continually looking at the parent element until we get to a situation where there's no parent elements or we are less than the parent element. Okay, there you go. That's the insertion process. Now let's talk about the time complexity for this.
2:35:44
Well, the time complexity for this is actually going to be log base two of n. So the reason why this is the time complexity here is because all we need to do when we're doing an insertion is shift this node up. And the number of Sift operations that we need to do is always going to be at most log base two of n, where log base two of n is actually equal to the height of the binary tree. Now, the reason why that's the height is because we have a complete binary tree.
2:36:11
So we know we're always inserting elements in this level order. Right. We're never having kind of a long linked list structure where we have only elements on the right or the left side. We know we're always going to have this perfectly balanced tree. So since we have that, we can assume that log base two of n is H will always be correct in that assumption, which means that we can write either the time complexity is big O of H or just log base two of n. Now log base two of n is more correct.
2:36:38
So we're going to write this instead. And again that's because every single node has two other nodes. So as our tree gets larger and larger and larger, the operation actually becomes even more efficient for us to either insert an element or to do some other operations. So we're going to talk about in a second. So hopefully you can understand why this is log base two of N. It's because log base two of n is equal to the height of the tree.
2:36:58
That means that we have to do a maximum of the height of the tree operations when we're doing an insertion, because we're simply looking up to the parent every single time and doing that swift operation, which happens in constant time. Okay. So that is doing and insertion. Now that we've looked at an insertion, what we need to talk about is how we do a removal. So when we're viewing a heap, typically the purpose of the heap is to constantly
2:37:20
be removing or looking at what the maximum value in the heap is. Now, the maximum value in the heap is always going to be the root node, or conversely, the minimum value will always be the root node, depending on if you have a maximum or minimum heap. So if we want to access what the maximum value is, what we can do that in constant time, because that's the root node. However, when we remove this node which quite frequently we're doing
2:37:45
so we're popping this off of the heap, then that means that we actually need to essentially rebuild the heap here, such that it maintains this property. So now if I want to delete and retrieve this node off the heap, what I actually do is I take whatever the last value is in my heap, which in this case is four. And I make that the value of the node that I'm deleting, which in this case is the root node. And we're only ever deleting the root node. Right. So we make that four.
2:38:10
Then we delete this value here. So if I'm doing this in my array I'm deleting the last value and setting that equal to the root node which then essentially removes whatever the last root node was. Then I perform pretty much the opposite operation that I was doing when I was sifting up. Now I'm going to sift down. So all I do now is I have this node and I look to the left and to the right, and I figure out whatever the maximum value is to the left or to the right.
2:38:38
So I look at both ten and 11 and first of all, I see, okay, are either of these values larger than me? Well in this case, yes they are. That means that to satisfy the heap property, one of them is going to have to come up here and I'm going to have to swap with them. And then continually I need to find the largest one of these two values. Because if this value now becomes the new root node, then that means that whatever value is the existing left
2:39:01
or right child needs to be smaller than that node. So in this case we look at ten and 11. We see that 11 is the largest and 11 is larger than us. So we perform a swap here downwards. So now 11 comes up here and four comes here. So now if we're writing this in our array then we're going to take the 11 here and erase that. That's going to become four. And 11 is the new root node. Now we can continue this process and remove all of the elements from our heap.
2:39:27
In fact let's do that. So now we want to remove 11. So what we do is again we take our last node. In this case the last node is going to be three. So we take three. We put this up here okay. And then we delete three. So we get rid of that from over here. And now we do this shift down operation. So I look to the left I look to the right. When I look to the left and the right I find the maximum value. I see if that value is greater than I am. So I see ten. So I now need to swap with ten.
2:39:54
So ten comes up here. And then what was this three comes here. So we'll do the swap
2:40:00
three and ten okay. But now that I've moved the three here I need to continue shifting this downwards to ensure that the left and right tree are still going to maintain this max heap property. So I look now to the left and right child of three, and I say, okay, are either of these children greater than me? Well they're not, so that means okay, we're good. The max heap is satisfied. However, if for some reason we had like a seven here. So let's just swap this out. So change one to be a seven.
2:40:31
Now we would need to do the swap again okay. So then seven would come here and three would come here. So we'd swap. That is three. And this is seven okay. Then we could continually keep doing this process and removing all the elements. I won't go through all of them. I hope you get the idea now. Okay, so now that we've looked at that, I just want to quickly write some pseudocode that would show us how we actually perform the insertion of elements inside of our heap.
2:40:58
Then we're going to talk about a heap creation. And then we'll pretty much be done okay. So again we have some array here. I'll just make it a little bit smaller for this example.
2:41:08
And we want to write some code that allows us to insert elements inside of our heap. Well we have the array. We can call this array something like a okay. So let's write the code to do the insertion. All right. So for our code the first thing we're going to do is we're going to say dot push. Then whatever this value is then we're going to get access to whatever the last index is. So we're going to say I is equal to a dot length minus one okay.
2:41:38
Now that we've done this operation, what we actually need to do is we need to write some function called heap ify. Now this is just typically what it's called. You can call this whatever you want. So I'm going to say function
2:41:49
heap ify and heap ify is going to take some index. Now what heap of will do is perform that sift up operation from whatever index we pass. So what we need to do for the sift operation is we need to look at the parent, and we need to check if the parent is greater than the current value. Now again, this will change if we're doing a max heap operation or a min heap. So what we'll do here is just assume that we are doing a max heap. So this function could be like max heap ify.
2:42:17
Okay. As opposed to min heap of fun. So first thing we're going to do is get the current value. So we're going to say val is equal to a at index I we're then going to say the parent node or the parent index is equal to. And then this needs to be I minus one divided by two. And then we're going to floor that. So I could write math.floor but we'll just indicate this is being floored okay. Now we need to check the value of the parent. So we'll say p value is equal to.
2:42:47
And then this is going to be array at index p. And then we need to check if this value is greater than the p value. So we're going to say if
2:42:58
val is greater than the p value then we need to perform this swap. And then we need to heap ify on the parent index. So for our swap we're going to do the following thing. We're going to say that array at index I array at index p is equal to. And then we just do the reverse array at index p and then array at index I. Now I'm just writing some kind of shortcut code here. This won't actually work if you use this in JavaScript. I'm kind of writing some variant of like Python code.
2:43:31
Then what we do here is we're going to call the heap ify function again, except this time we're going to do it at the parent index okay. So if the value of our node that we're inserting is greater than the value of our parent, then we need to move that upwards. So to move that upwards we simply swap the values at these two different positions okay. So we're swapping the parent value with the node that we're inserting value. Then we need to repeat this process.
2:43:57
But this time we're going to keep ify on the parent node. So just quickly looking at a tree here okay.
2:44:04
So imagine we're inserting some node here. Well we swap that with the parent. Then once we swap that with the parent we need to check. Now if this new node needs to be swapped with its parent. So that's why we are recursively calling the heap ify function. Now this heap ify operation runs in big O of log base two of n. Okay. So just remember that where n is the number of nodes that we have inside of our heap. So hopefully that makes a bit of sense. But that is heap ify.
2:44:32
Now if you're going to be removing or extracting the maximum value that pseudocode is a little bit more complicated. I'm not going to write that for you right now, but I just wanted to show you some basic code here for performing this operation, which is the insertion into the heap. Okay, so now that we've looked at that insertion, I'm just going to quickly mention that we can actually build a heap by just continually inserting different values.
2:44:54
Now, this is not the most efficient way to go about creating heap. But let's say I have n elements okay.
2:45:00
And maybe this is just an array that contains some randomly ordered elements. If I want to sort these different elements, then what I can do is I can use a heap. So what I'll do is for every single element. So for every n I'll perform an insertion into my heap. And that's now going to give me a heap that contains all of my elements in this kind of heap structure. Right. So what happens is I will perform the insertion for all of these. And that's going to take me big O of n
2:45:34
log n time log base to event. Now the reason that's going to take n log n time is because the heap ify operation that we're performing every single time we do an insertion is going to take log base two of n time. We have n elements we want to insert into the heap. So we say n multiplied by log base two of n. So that's how long it takes us to insert every single one of these elements inside of the heap. But now that we have them in the heap, so we'd have all of our elements
2:45:58
inside of the array heap here, we don't actually have them in a sorted array. If we want to get them in a sorted array, then what we need to do is just continually extract every single value out of our heap. So we're constantly getting that maximum value from our heap and then insert that into an array. So imagine we have some heap right. So seven this needs to be less than like six for we're just doing a very basic heap here. And then we want to get all of the elements from our heap
2:46:25
to be in a sorted array. Well all I do is I grab the maximum value. So I take the maximum value. I insert it here in the array. Then once this is removed we would have shifted up six right? Okay. So six comes here. Then we extract the next maximum. So six comes here. Then we extract the next maximum. So four comes here in a new array. And now we have built a sorted array using this heap structure. Now this is actually one of the more popular ways to go about sorting something.
2:46:53
This algorithm that I just showed you is called heap sort. We put everything inside of a heap, then we extract all of the maximum or minimum values we can do again, a min or a max heap from the heap, and then push all of those values in the order in which we extract them into a new array. Now that gives us a sorted array in that operation takes two multiplied by n log base two of n time. The reason this is two multiplied is because the first thing we need to do
2:47:19
is push all of the values in the heap, which takes n log n time. Then we need to extract all of the values from the heap, which takes again n log base two of n time. So we multiply by two. But we know the constants don't matter. So we remove that. And that gives us the big o notation of n log base two of n to sort an array using a heap. Okay, so let me just kind of recap some of the operations here to do an insertion into a heap that takes log base two of n time
2:47:44
to do a extraction operation where we get the maximum value that takes log base two of n time to create a heap that takes n log n time. And if we want to sort using a heap again, that's n log end time okay. So a heap is an efficient data structure when we constantly want to access or update some kind of maximum or minimum value, retrieving any arbitrary element isn't really useful to us. We don't do that with a heap, and we can implement the heap using the array data structure.
2:48:13
Okay, so with that said, I'm going to wrap up the video here. I hope you found this helpful and I look forward to seeing you in another one. Hello everybody, and welcome to the next video in this section where I will be discussing graphs. Now, a graph is another non-linear data structure that allows us to represent some more abstract data. Graphs can represent something like road systems, right? Where we have different roads going between different cities, locations, etc.
2:48:37
and traversing those roads or traversing this graph in this case can allow us to figure out something like the shortest path between two different cities. Additionally, we can use graphs to represent something like the exchange rates between different currencies. I know that seems like a weird concept, but there is actually a way to use a graph to do that. Regardless, graphs are very flexible. They're used all over the place in computer science. And the goal of this video here
2:49:00
will be to give you a high level overview that explains most of the key terminology and types of graphs, so that you're familiar with them. We're not going to get too much into implementation. Later on we will look at a few graph algorithms. And when that happens, I'll start showing you how we can actually do some operations on graphs and talking to you about the time complexity of them. For now though, let's talk about some basic graphs. Okay, so definitions here.
2:49:23
A graph is made up of two sets called the vertices and the edges. Now a vertex or vertices is like a node. And it can be connected to other vertices by edges. So I'm going to use node and vertex interchangeably. Typically in graph theory you refer to this as a vertex, but really it's the same thing as a node. Just like when we talked about our binary trees. Okay. We then have an edge. Now an edge is a connection between a pair of vertices or nodes.
2:49:49
So we may have an edge between vertex a and vertex b. Now an adjacent vertex is a vertex that is connected to another vertex via an edge. So if you have a direct edge between two vertices, they're said to be adjacent. You can also say these are neighbors. Okay. So those are the main definitions. All right so let's look at a graph example here. This is an example of a graph. We have a few different nodes or vertices. And then we have some edges. So first of all what are the nodes.
2:50:16
Well let's have a look here. So we have the vertices or nodes which are 123456 okay. So all of the elements that actually make up the graph. And then we have our edges. And these are all the different edges that exist in the graph. So we have an edge from 1 to 3 okay. We have an edge from 3 to 5. An edge from 1 to 2, 1 to 4, from 2 to 4, 3 to 5, 4 to 6 and 4 to 5 okay. So just kind of reading through them here. Now notice that the way I represent an edge is a set of parentheses with one
2:50:47
node here on the left side, another node or another vertex on the right side. That means we have an edge between these two different vertices. Now if we switch the order so we have like three and then one. In this case that's totally fine because we're looking at an example of something known as an undirected graph. And we're going to talk more about that in a second. But for now I just want to note that I wouldn't necessarily duplicate the edge one three.
2:51:10
So I wouldn't write one three and then three one. I just write one three because it's implied by this type of graph that if I can go from 1 to 3, I can go from 3 to 1. Okay. So basic example of a graph. All right. Types of graphs. We have undirected graphs directed unweighted weighted cyclic acyclic and disconnected sorry graph. Now I'm going to go through all of these different types here. But it's important to understand the different types of graphs because
2:51:35
based on the problem you're faced with, if you know the property of a graph, it can actually allow you to solve whatever the problem is in a more efficient time complexity. So that's one of the main things you'll kind of see here as we go through this section, or as we've been going through this section, is that when we know certain properties of our data structure, we are able to craft more efficient algorithms by using assumptions that we can make about that data structure. Okay.
2:51:59
So undirected graph a graph in which the order of the vertices in the edge set does not matter, i.e. an edge of three two can be written to three without affecting the graph. The edges are bidirectional. So same graph we looked at in the previous example. In this case it's undirected because we can travel both directions across an edge. Go and go from 1 to 3 or 3 to 1, 1 to 4, 4 to 1, etc. that's all it means when it says undirected. All right, moving on. We have a directed graph.
2:52:26
Now this is a graph in which the order of the vertices in the edge set does matter. The edges are directional. So in this case we have an edge from 1 to 3. And that ordering actually matters. It's not an edge from 3 to 1, it's only from 1 to 3. So if I was on three, I cannot go back to one. I can only go to the directed edges or cross the directed edges and go to five or go to four. Okay. So important to understand the difference between directed and undirected.
2:52:51
Typically, if you're drawing a graph, your directed graphs will just have arrows which indicate the direction of the edge.
2:52:58
Next, we have an unweighted graph. Now, an unweighted graph is a graph in which there is no size or weight associated with the edges. It can be directed or undirected. So both of these examples here are unweighted edges. And what that means is that we would imply that the distance or the size of every single edge in the graph is the exact same, meaning we don't need to consider that size, hence why it's unweighted. Okay. So that's an unweighted graph where we don't have labels or weight
2:53:25
sizes on the different edges. Next we have a weighted graph. Now a graph that is weighted has sizes or weights associated with the edges. So if we're looking at the example of a road system then these might be the distances between different cities. Right. So each edge represents a road. And the weight or the size on that edge represents the distance between the two different cities. And when we draw a graph we typically don't draw it to scale.
2:53:50
So in this case you can see I have an edge weight of seven here. But then I have another edge. It's actually larger or longer than that edge but has a smaller weight. That's completely fine. Typically again when we draw the graphs we just kind of label them here. We don't try to make them actually to scale with what the weights of the edges are. Hopefully that's making sense. But unweighted. No labels on the edges weighted. We have these labels or these sizes weights on each of our edges.
2:54:16
All right moving on. We have a cyclic graph. Now this is a directed graph in which at least one cycle exists. And a cycle is a path along the directed edges from a vertex to itself. So if we're looking at this graph right here, we can see that we have a cycle because we can go from 1 to 2, 2 to 4, 4 to 3, and then three back to one. Since from this vertex I can follow a set of directed edges and get back to this vertex. That means I have a cycle.
2:54:43
Now this property of a graph can become important, and certainly rhythms, because if you know that you have a cycle, it may actually disallow you from using a specific solution due to the fact that you may be infinitely kind of moving in this cycle. On the contrary, if you know you have a cycle, you may actually want to be looking for the presence of that cycle. And there's different ways that you can do that. Anyways. This is a cycle that we can see right here.
2:55:05
Now, the reason why we're only looking at directed graphs here is because if you have an undirected graph, then technically you always have a cycle. The reason for that is that if I can follow any edge in both directions, then if I have an edge between two nodes or vertices, I always have a cycle between that edge and those vertices. So for example, if this edge between 4 and 3 was undirected, I could go from 4 to 3, from 3 to 4, from 4 to 3, back and forth, back and forth, back and forth.
2:55:30
So that always makes a cycle. So when we're talking about cyclic graphs, typically we're talking about a directed graph. Now look over here we have another cycle. This one's a little bit harder to spot. We can go from one to 2 to 4 back to one okay. So this is a cycle that contains these three sets of edges. We also have another cycle from one to 3 to 4 back to one. And we could introduce many more cycles if we added more directed edges. Okay. Next we have an acyclic graph.
2:55:57
Now this is a graph in which no cycle exists. A cycle again is a path along the directed edges from a vertex to itself. So in this situation it might look like we have a cycle. But here if I go from one to 2 to 4, then I stop. If I go from one to 3 to 4, then I stop. There's no cycle here. No way for me to get from one node back to itself. Okay, next we have a disconnected graph. Now we disconnected. Graph is a graph that contains at least one vertex that is not connected by an edge.
2:56:25
So pretty easy to spot this if you're looking at the visualization shown. But in this case three is disconnected. And over here two and six are both disconnected from this graph. Okay. Moving on we have graph representations. Now there are multiple ways to represent graphs within a computer program. Some representations provide more efficient access to the edges, vertices, etc., and the two most popular representations are an adjacency matrix and adjacency list.
2:56:52
Now we just looked at visual representations of the graphs right? We're kind of drawing them out. However we need a way to actually represent these in our computer program such that we can traverse the graph and we can look at the different edges and nodes that we have inside of it. So that's why we're talking about these two representations. Now for now just understand what these representations are. Obviously I'll go through them in one second and be able to look at a graph
2:57:15
and write the corresponding representation, or vice versa. Look at a representation and then write the corresponding graph. You'll see that it's not over the complicated. Let me show you the two different representations okay. So adjacency matrix representing an undirected graph. Now first of all you can see that we actually have an edge. Sorry. That is going between the same node. That's valid. And in a lot of cases you can have that okay.
2:57:40
So I just want to kind of show that to you in this example. Regardless we have an adjacency matrix here. And this matrix represents the graph that you see on the right hand side of the screen. The way it works is we have a two dimensional array which we sometimes call a matrix that is a square size. So its size is going to be equal to the number of nodes for the width and the number of nodes for the height. So if we were going to calculate the total number of elements you have inside of here,
2:58:04
it's going to be n squared or v squared where v is the number of vertices okay. So in this case we have four nodes or four vertices. So that means that we have four columns and four rows. All right. So if we go through this here we can see that we have ones and zeros. Now in an undirected graph a one is going to represent that an edge exists between the two nodes that are at the column and row position. So in this case we have a one for a. That means that we have an edge
2:58:34
between A and a right, which is what we can see right here. Continuing with move over, we have A in our row B in our column. That means we have an edge from A to B. So we do have an edge there a to B okay. Now we go to see we have an edge from A to C because we have a one there. So that means there is an edge. Go to D. We have an edge between A and D and we can see that edge okay. Going to be now. So now we're in the next row. We're looking at B and then A. So from B to A there is an edge.
2:59:02
Again this is because it's an undirected graph. So we're going to essentially be duplicating the edges as we write them in this adjacency matrix okay. Next we have b. So there's no edge between B and itself no edge between B and C and no edge between B and d. So we put zeros there. Moving on we have c and a. So again we can see we have an edge from C going to A and then from a going to C. Because this is undirected you could continue going through this.
2:59:26
But you can see that this represents the graph on the right hand side. That's how we use this for an undirected graph okay. Next we have a directed and weighted graph. Now you could obviously just have directed or just have weighted. But in this situation the matrix looks a little bit different. So here you can see that now rather than just putting ones, we're actually putting the weight of the edge between the two different vertices.
2:59:50
And we have a directed graph meaning we are not duplicate these edges. We're only writing the edge one time. So if I'm looking at E here, you can see there's no edge between it and itself. There is an edge between A and B, and that edge has a weight of five. So that's why I indicate five here between C no edge between D there is an edge. So from A going to D right. That's kind of how we're reading it here. From A going to D. We have an edge that has a weight of three.
3:00:14
Now you could read it in the opposite order if you want to, but you have to pick what order you want to read it in. So in this case I'm reading row first then column that indicates I have an edge from the row element to the column element. Okay, not the other way around. That would be incorrect for this specific graph anyway. Is going to be. You can see we have an edge from B to D. So if we look at that that has a weight of two from C, we have this edge from C to D that has a weight of one.
3:00:39
And then from D we have an edge going to see which has a weight of four. So again as I was saying you should after kind of looking at this PowerPoint slide here, be able to look at an adjacency matrix and draw the corresponding graph or vice versa. Look at a graph and write the adjacency matrix for it. Okay. Next we have an adjacency list. Now an adjacency list is different than an adjacency matrix. It has some different time complex these when it comes to accessing the different
3:01:06
edges and accessing the different vertices that are in the graph. But we're not going to get into that right now. As you can see here, what we have is a set of nodes okay. So in this case I have node a node b node c a node d. Now they all have a linked list associated with them that represents all of the different edges that exist inside of the graph. So in this case I have my node A or my vertex a. It then points to a linked list. This linked list could be empty
3:01:32
or it could contain a variety of different edges. In this case, it has all of the nodes that it has an edge with. Because this is an undirected, unweighted graph. So in this case we have an edge from A to b, a to c, a to d, and a to a. And again this is a linked list just like we talked about in the previous sections. Going to be we have an edge from B to A. So that's the same as our edge from A to B. Right. We just have to write that twice because this is an undirected graph.
3:01:59
Now same thing for C we have an edge going to A just like A has an edge going to C. And then we have an edge going to D. And then from D we have an edge going to A and then an edge going to see again undirected unweighted graph okay. Next looking at a weighted and directed graph. So when we have a weighted and directed graph then that means that we have this linked list structure. Again except every single node we contain in the edge list for any given node, we have a weight associated with it.
3:02:27
So in this case we have a that has an edge to D. So we can see that edge right here. It has a weight of three. So we indicate three. We then have an edge going to be that edge has a way to five. So we indicate five and you get the rest. You can see kind of how we represent this here using the adjacency list. So with the adjacency list here you can see that when we don't have that many edges this can actually be a more efficient way to access data than using the adjacency matrix.
3:02:52
So in this case only a five edges right. If I go back to my adjacency matrix you can see that we have so many zeros inside of this matrix. So we're kind of wasting quite a bit of space here when we don't need to be doing that. And then when we come back to the adjacency list you can see that this is very space optimal because we're only storing the necessary edges that we have. We're not storing all of these kind of zeros in positions inside of that matrix.
3:03:15
So there's all kinds of advantages and ways to use these different representations. But these are very commonly seen. So I just wanted to introduce them to you so that you understand kind of how they work. And you're not lost if you see them. So with that said, I'm pretty much going to wrap up this video here. I know this was fast. There's a lot that I can go through on graphs, but I want to save that until we actually get into some of the graph algorithms.
3:03:34
And then I'll show you some basic implementations of those algorithms, and you'll see how we can use these different representations in the relative space and time complexity on both of them. Now, space complexity is not something we've really talked about this far. But just like we have a time complexity where we're looking at the running time of algorithms, we can also analyze the relative amount of space that these algorithms will take,
3:03:55
which is kind of why I was hinting at that with the adjacency list. First, the adjacency matrix. The adjacency list in this situation is more space efficient than the adjacency matrix. Okay. With that said, I'll wrap it up. I hope you found this helpful and I look forward to seeing you in the next one. Hello everybody, and welcome to the next video in this section where I will be discussing hashing. Now I'm just going to give you a basic introduction to this topic.
3:04:17
This can get extremely complicated and extremely math heavy. That's not the goal here. To confuse you. It's to simply introduce you to what a hash is and how this is used as the basis for some different, kind of data structures that will have a look at in various programing languages. Okay. So let's begin by talking about what hashing is. Well, hashing is actually a very simple concept. It's taking some data, passing it to some kind of function,
3:04:44
and then getting some kind of unique output, which we refer to as the digest or the hash. Now, what this allows us to do at a very high level is take maybe a very large piece of data or a small piece of data. Doesn't matter what it is. Pass it to some function and get some kind of uniform output that represents the data uniquely. Now hashing is used quite frequently in things like cryptography, cryptocurrency, digital security, password security.
3:05:11
There's a lot of, kind of implications and use cases here of hashing. But in our instance, we're talking about hashing in relation to data structures. So we're not too concerned about the security component of hashing. We're more concerned about how we can use this process to efficiently access different pieces of data. So let me just give you a more concrete example here. Let's say that I have some string. Okay. Maybe a string like hi.
3:05:34
And then I pass this to what we refer to as the hash function. Now this hash function can be a million different things. So all kinds of different ways to hash data. But really what this is going to do is spit out to us some kind of number or some kind of string, some kind of uniform output based on some criteria that we want. So the different hash function we use will give us kind of a different value. But maybe in this instance it's always going to give us a four digit number okay.
3:06:02
So something like 4732. And then if I pass in a different value here like yes okay then this is going to give us a different value. Okay. 4397 whatever it may be okay. I'm just using some random examples here. Now one of the important properties about this hash function is that every time I pass in some input, I always get the exact same output. And typically hash functions are going to generate unique outputs which means every single input has a unique output.
3:06:33
So high and yes will never map to the same value or high in any other given string, never mapped to the same value. Now that would be an example of a perfect hash function that doesn't necessarily exist. There's a lot of instances where you can have something known as a hash collision, which means you have two different values then for some reason map to the same output. Now that's not ideal. And that causes some problems. And you know, there's a resolution strategy for that.
3:07:01
However, I just wanted to kind of give you this premise here. So the idea is you take some input, you pass it to a hash function and it generates some unique output for you. And the idea is that every single input will give you a unique output. So again, in an ideal scenario you never have two inputs mapping to the same output. Okay. So with this in mind let's see how we could use something like hashing to improve the efficiency of different operations.
3:07:23
So let's imagine that we have some array here on the right hand side of our screen. And for some reason in my array I want to store key value pairs. So there's something like a property associated with a value like we have any JavaScript object. So maybe I want to store the key x. And I want that to be stored with the value seven. Okay. If that's the case I can pick an arbitrary index instead of this array and store it in here. So maybe I store something like x and then set okay.
3:07:55
It doesn't really matter where I'm storing it. Now if we're just using a standard array here, what that means is that if I ever want to retrieve the value associated with the key x, I need to iterate throughout most every single element inside of my array to retrieve the location where x exists, and then get the value associate with x. Meaning this lookup operation takes me big O of n time. Now same if I want to delete this right, I need to find where it exists and then remove it.
3:08:24
And that takes me big O of N time. Now what if there was a faster way? What if, for some reason I just knew what this index was without having to look through the entire array? Well, that's where hashing comes in. So I'm going to give you a very, very simplistic example of this. Keep in mind there's a lot more details that I'm not really showing you here. But let's imagine that now what we do instead is we take X and we pass it now to a hash function.
3:08:49
And then this hash function actually spits out to us an index. And this is where we should store the key and value associated with x. So the index could be something like actually let's not do seven because that doesn't exist in our array. Something like four. So now we've passed that key x and that's given us an index. So we're going to store the key x and the value seven at index four. Now let's say I want to retrieve the value associated with the key x. I don't know necessarily what that is.
3:09:21
Well I just repeat this same process by passing my key x to the same hash function. And that now tells me the index where x exists. So now what I'm doing is every time I'm inserting a value, I'm first passing it to that hash function. That hash function is computing a unique index for me to store that value in. And then I'm taking that value and I'm storing it in that index. So now anytime I want to retrieve something all I need to do is use the hash function.
3:09:47
And it essentially tells me where inside of my array this element exists. And if the hash function works perfectly, then that means that this runs in constant time, because the hash function will be very, very fast to compute. That's one of the main properties of a hash function, is that it's very quick to compute okay. So that is kind of the very perfect situation when we talk about hashing, right, where we have say like an unlimited amount of space, an unlimited
3:10:11
number of indices here or memory address, locations, whatever you want to use. You take some value, some key. In this instance, you pass it to a hash function, and that now tells you the location of where this element exists. And if it doesn't exist, then you insert it into that position. Now that also means that we can check if something exists in constant time too right? Because if this gives me, say, index one and I have a look at index one here
3:10:33
and there's nothing there that means, well, I know this doesn't exist. So when we talk about data structures like sets and hash maps or maps in Java, or it's not JavaScript, JavaScript, these are typically using some form of hashing in the back end to actually allow us to do things like add, remove, and check if something exists in constant time. Okay, now the issue though is that we don't always have a perfect hash function.
3:10:56
In fact, it's very likely that depending on the number of keys that we're using, the two keys end up mapping to the same index. So in the situation in which, say maybe both x and y mapped to the index, for now, we have a bit of a problem right. Where if they map to let's do the index three okay. If they both mapped to the same index then that means that we have to come up with some kind of resolution strategy where we first look at the index.
3:11:23
We say, okay, well is it the key that we pass to the hash function. And if it's not then we need to generate a new hash. Now to generate the new hash we have to change the input slightly by adding something to it or removing something from it, so that we get kind of this unique index for it. Okay. Now I'm not going to talk about exactly how that's done. That's fairly complicated. But that's just what I wanted to introduce to you here, that this doesn't always happen perfectly.
3:11:46
And if you have something known as a hash collision, which means two inputs map to the same output, then you need to do something that will cost you a little bit more time. So even though typically you're going to assume that when you use a hash map where set, which are the two kind of data structures that implement hashing that you're going to run in constant time, it is possible that you can take slightly more time depending on the type
3:12:08
of the inputs that you have, what you're outputting, the amount of memory you have, and if any hash collisions occur. All right. With that said, I'm going to wrap up the video here. I know this is not a comprehensive overview. I just wanted to get you thinking a little bit about this topic and give you the basic premise of what hashing is. Hopefully you understand that, and I look forward to seeing you in the next video.
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