today's topic is binary search trees [Music] hey everybody welcome back i recently did a video on trees and binary trees and today i wanted to turn our binary tree into a binary search tree so if you missed that last video on trees or have no idea what trees are or just need a refresher you might want to check that previous video out i put a link down in the description also as always source code is available through patreon to all of you wonderful people who support this channel you're the best thank you but now onto trees so in our last video we ended up producing a simple binary tree a binary tree is just a tree where each node has up to two children or subtrees typically we refer to those as a left child and a right child and i also showed you some simple code for how to traverse that tree and print out the notes we also talked about how trees are useful for representing hierarchical data pretty much any time you have data that has a one-to-many relationship a tree might be a good data structure to use and in the previous video i also mentioned that trees can be used to speed up data access and that's what we're going to talk about today because a binary search tree is just a binary tree like this but it has a few particularly useful properties so for today's example i'm going to store numbers in my tree just like this but search trees can be used with any data type that can be ordered meaning that your elements can be greater than less than or equal to each other so of course that's going to work with ins doubles floats but we could also do it with strings using string compare or we could have objects that have dates and we could sort by dates pretty much anything that you can sort you can use in a binary search tree now the main thing we're going to add to our tree today is order we're going to enforce some order specifically if we're looking here at the root or really any node in the tree all the numbers to the left are going to be less than the numbers stored in the node and all the numbers to the right are going to be greater than that node so in this example the root is 15 and everything to the left is less than 15 and everything to the right is greater than 15 and that continues with each of the sub trees when we get down to 19 everything to the left is less than 19 and everything to the right is greater now why is this helpful now imagine that all of these numbers were held in a list like a linked list or an array pretty much some kind of sequential list and say we wanted to see if a particular number was inside this list we just wanted to test to see if we had that number well how long is it going to take in the best case it could be the first one we checked first one in the list but it could also be the last one in the list and i could have to search through the entire list to find what i'm looking for searching in this case would be an order n operation meaning that we have to check up to n different nodes where n is the number of nodes in our list now on the other hand with a binary search tree if we have a nice bushy tree like this searching goes a little differently say you want to check to see if 16 is in the tree well we check the root that's not it we know if 16 isn't our tree then it's on the right side since it's larger than 15. so we check the right child 16 is less than 19 so we're going to keep looking but this time we're going to look to the left because we know that we want something less than 19. and then we find it as long as our tree is bushy more precisely we can call this a balance tree so as long as our tree is balanced we're only going to have to check about log n different nodes to find the one we're looking for and especially as n gets large log n is going to be much smaller than n and so things are going to be a lot faster now let's look at how this works in code so we're going to start with this code this is just the binary tree example code we used last time it basically just had a function for creating tree nodes so we see that right here we also had a struct that defined what our tree nodes look like and then we had some functions down here that basically helped us print out the contents of our tree we're not going to do much with those we will keep them around we'll print out our tree at some point and then down here in main we just added some nodes and printed out the tree now today i want to add two new functions to my tree one that inserts node into the tree in order of course so that we have a binary search tree and we're gonna have a second function that uses that ordering to search the tree okay so let's start with insert now first off i'm going to return a boolean value that's going to simply tell us whether the node was inserted or not we may not need that for this example but it's a useful thing to add so i'm just going to add it and then we're going to take two arguments the first is going to be a pointer to a pointer of type tree node and the second is the value that i want to insert and of course you can see bool isn't working for us so let's run up here and include standard bool.h that should take care of that now please don't panic about the double pointer it's simply there because if the tree root is null i need to be able to change the address that the root pointer points to so with a single pointer i wouldn't be able to do that but just for convenience let's go ahead and create a single pointer here and we'll have it point to whatever root pointer points to so we can use that that'll be a little more convenient and maybe make some of the syntax a little less scary for those of you that are still maybe a little bit uncomfortable with pointers now we talked about before in my last video about the fact that trees lend themselves to recursive processing and this function is going to be recursive it doesn't have to be but i'm choosing to make it recursive so first of all we're going to handle two basis cases one is if our root is null so this is the first case we're going to look at now if the root is null that means the tree is empty so what we're going to do here is simply set our root pointer to a new node we'll call create node with the value this is just the function we had before so i'm passing in the value and then we're going to assign that root pointer to be the value so i'm basically creating a new route for the tree and setting it okay so if that's the case then i can return true and we are done okay our second base case is going to be when our value is equal to the roots value so this is the one where we say the thing you're trying to add is actually already here in this root and here we've got some decisions to make in this case what i'm going to do is i'm going to do nothing i'm just going to say it's already in my tree i'm not going to add it a second time so i'm only going to allow a value to exist once in my tree so we're going to return false because we didn't add it to the tree so those are my two base cases and now we're going to add two recursive cases and these are almost identical you can probably guess what i'm going to do here basically i'm going to say if value is less than the roots value okay so if it's less than whoops if it's less than the root value then what we want to do is we're going to look in the left side of the tree so what we're going to do is we're going to try to insert we're going to basically recursively call our function and we're going to pass in the address of the roots left okay so this is going to pass in the again a double pointer so that we can change its value and we'll pass in the value okay and then our other recursive case is basically the other option which is that the value is greater than the root and so we're going to do the same thing down here except we're going to check the right side okay so what this is going to do is it's going to recursively work through the tree it's going to basically pick a side and it'll go that side and then when it finally finds a spot that's null it will basically create a new node using this base case right here and that's really it this is going to work it's going to handle all of our cases so now let's look at our second function which is how do we find a number so this one is also going to return a bool that's going to tell us whether it found the number or not we're going to again pass in a pointer to our root and the value we're going to pass in note that this time we didn't pass in a double pointer that's because we're not changing the tree at all all we're doing is searching for it we're just going to be looking through the tree and so a single pointer is going to work just fine so once again let's look at our base cases we're going to check first to see if the root is null okay in this case we can just return false this basically just means our tree is empty there's nothing to search there's nothing to find we just it's not here the next base case is if our roots value is equal to the value we're looking for then we're going to return true right because then we found it obviously it's right here so then we're basically going to mirror what we did previously except we're not inserting we're finding but we're going to say if the value is less than the roots value then what we're going to do is return find number of the left child and pass in value and this is basically going to then search again recursively in the left side of this tree and we will do the exact same thing on the right side of the tree okay again this looks very similar to up above except we're just searching we're not actually inserting or changing the tree at all and again that's all we have to do this function will just keep recursing until either we find the node with a matching value or a null node and in that case we know we were not successful okay so just to test things out let's jump down here into main and i'm not going to create all of these again this was a little manual instead let's just make a route we'll start out empty just remove this we'll leave our tree down here to print out our tree once we're done but then all i'm going to do is call insert number and we'll pass in the address of root and let's just make the tree that i used in the diagram before let's add 15 and then 11 and then 24 and then 5 16 and 19. actually i think 1916 i don't remember anyway it's fine may not be exactly the same tree that's fine but the point is here we're just going to keep inserting things and that is great so then let's run down here let's compile our example that looks fine and let's run it and you can see that we basically constructed the tree looks a little different from the diagram but you can see that we have the lesser values on the left side of the root which is 15 and on the right side we have the values that are greater than 15. it's fairly balanced it's definitely going to allow us to search fairly quickly okay so that works now let's also go in here and search for a few numbers just so that we can see if we can find them here we're going to print out a couple of numbers we'll print out the number we're searching for and let's just print out whether we found it or not and so let's search for my 16.99 root 16 and let's search for we'll do 16 and 15 and 5. those are all numbers that are in our tree and then let's search for 115 1 and 7. so these are all not in our tree okay so this will just give us a good idea of whether our find number function is actually working so we compile it and let's run it and so you can see yeah of course we printed out the tree that's fine i won't look at that but you can see that yes the ones that are in the tree we found them the ones that are not in the tree we did not find them so our binary search tree is working okay and this is going to provide much faster searching than we would get from putting these numbers in a list but i want to emphasize that this is not guaranteed to be the case so consider what would happen here if i inserted my nodes in already sorted order instead of just randomly like i did now you would get a tree that looks like this which is basically just a linked list it i mean it's it could be a tree but it's not it's this is a degenerate case it's basically just a linked list and so in this case you get no speed improvement at all and we just wasted a bunch of memory on extra pointers and that's something that you need to keep in mind when working with binary search trees is that they're only fast if the tree is fairly balanced so when we're working with just a regular ordinary binary search tree the order in which we insert our numbers matters a lot and that can be really annoying especially if the data that we want to store is already sort of almost sorted then we're going to get really bad trees and so in order to deal with this problem we do have other variants of binary search trees these include avl trees and red black trees please let me know down in the comments if you'd like to see a video on either of these at some point but these trees basically automatically balance themselves as they go so if your data happens to not be random but it's already roughly sorted or maybe it's perfectly sorted they're still going to work of course if your data is perfectly sorted and it's static then just use an array and use binary search there which is very similar and maybe we'll do a future video on that so let me know which of these topics you'd like to see more about in future videos but i hope this helps you understand what a binary search tree is and how you could use it in your projects like this video if it was helpful subscribe so you don't miss the next one source code's available through patreon and i'll see you in the next video