Data Structures in Golang - Binary Search Tree

hello Hawaii today in this video you'll learn the basic concepts of binary search trees how they work and why we should use them and after I explained the basics I'm going to guide you through the process of searching and inserting data in a binary search tree in Indo Liang so yes let's let's see what we have okay so as you can see this is a tree structure we call the top node the root and the nodes that are directly under a node are called children so the node above would be the parent and if you see at the bottom of the tree there are nodes with no children these are called leaves here you can see that there are two children coming from one parent in this diagram in this case we call this a binary tree a tree that has nodes with no more than two children is called a binary tree so each parent is going to have a left and right child and when the smaller child is placed on the left and a larger placed on the right we call this a binary search tree but most cases a binary tree actually wouldn't look as perfect as the sum of the left or right children nodes will will be empty so it would be more looking kind of like like this so in a tree like this we're going to like talk about how we're going to insert and no nodes are always inserted as a leaf let's say we want to insert a node with 56 as a key in this tree we're going to start at the top and compare 56 to the root so 56 is smaller than 100 so go left and it's larger than 52 so go to the right and it's going to be smaller than like 76 so go to the left but that spot that left spot is is empty so 56 would be placed there and that is how a node can be added into a tree as as Li it's also similar to when you want to search a node in this tree so let's say you want to find a node with 24 you also start at the root at the top and compare 24 to a hundred it's smaller so go to the left smaller than 52 so go to the the left larger than 19 so go to the right and it's there so we found it so we can say that 24 is in this tree yes it's very similar how you insert it and how you search nodes the the advantage of using binary tree is speed so when the tree is is well balanced when we search or insert data into a binary search tree the the Big O is going to be Oh H which is better than an O n it's it's log and even though the tree is perfectly unbalanced which is like the worst case scenario it would still be linear which would be equivalent to a linked list so a binary search tree would be pretty useful when you're handling a large amount of data so this time we're going to go and try to implement this in code okay so we're going to do three main things we're going to define a node and we also need to make an insert method because we're going to have to insert nodes in the binary search tree and another method we're going to do search okay so these are the three main things that we have to do let's first define a struct for node and inside for the fields are of the node struct where we're just going to use int for the key here we just needed to to compare it with the other nodes we're going to compare the key each node will be a parent so if it has any children it needs to have two pointers which are going to point to each left and right child and let's just go and try to make one so I'm going to make a tree use a struck literal - and keep 100 and because node the tree should be an address I'll have to put that there tree has to be an address when I call methods I'm going to call it as as a pointer and let's see what we have oh okay so you can see that the key is a hundred we didn't give anything full left and right so for by default they're going to be nil so right now it's just a node with no children right now okay nice so now let's go do the insert we need to manipulate the receiver so we need a pointer receiver and we have to take in a key which is not already in the video so our plan is to compare the key with the receiver and go to the child on the right if it's larger and go to the child on the on the left if it's smaller so the basic structure inside the brackets in this method should be it should look like this so in N the key if it's if the key if K is larger then we're going to move right and if n dot key so if K is smaller then we should move lift so that's going to be the basic structure and so when we move to the left child if the child is empty we'll just put a new note there so we're going to write that up in code so this would mean if that right child is empty group they can you note and the key should be K but if there is a node at the right child like right now we're assuming that there's nothing on the right child so that's why we're inserting it here but what if there is something we're going to repeat this method this insert method again on that right child that existing right child in other words we're going to recursively call this method onto the right child so it's going to look like this and so we're calling this insert method not on the parent but on the right child and this goes same for the left but it left so just to clear things up this method consists of two parts when K is larger than the key and when it's smaller than the key so when it's larger we're going to move right if that place is empty we're going to make a new node and put it in there with the key K but if that place is not empty then we're going to put we're going to call this method again on that non empty that existing child node and the same goes for the left okay let's go tree insert okay so right now what it looks like is there's one hundred and we put in 50 so 50 is smaller than 100 so it has to go inside the left child which is over here so it's stored as as an address as a pointer let's say let's put in 200 and in that case this time it went into the the right child and again let's do something let's put 300 in it so we're going to put 100 200 and 300 and in this case when we print tree because 300 went inside that the right child node of 200 we can't see it in tree so you can still see that the the left position left child of tree is still nil okay so we just checked that it works fine I think it works fine okay so now let's implement the the search method actually don't need to use a pointer receiver but just to be consistent I'm just gonna use a pointer receiver and and as a parameter we're going to take in a key so we still need to do this and it's going to return a boolean value so if K is if a key value K exists in the tree it's going to return true if not it's going to return false so here we're going to do something similar to what we just did in the insert method so if if the key of the node we're at is smaller go left if not go right so it's the same thing if and if it's not smaller and not larger then it means that it's a match it's equal to so in that case we need to return true so that's the big structure of this method okay let's fill in these brackets so after we go right we're going to repeat this method so we're going to repeat it on right and search and we're going to keep on searching for K and we're going to return this so this method search method is going to continue to be cold and it's going to move down the tree and return through when it meets a match so it's not a if when K is not larger or not smaller than the key then it's going to return true but what if we don't meet a match what if there is not a match in that case we need to return a false so if n is nil so the note that we're calling the method on if it's nil then that means that it's the end of the tree and we didn't meet a match to sum up a little bit if if the node is not empty II here this part so if there is actually something very this is going to be ignored if K is larger it's going to go to to the right and call this again if it's smaller then it's going to go to the left and call this method again and if it's exactly the same then it's going to pass all this and it's going to return a true so now let's go and see if this works I'm going to add a bunch of nodes and let's try to find 76 we need to print it out okay so let's see if this works okay it's true so we do have 76 here let's try to search something that's not there okay so we get a false so I think it's it's working fine we'll just try a couple of more yep okay so um just out of curiosity let's see how many nodes that is actually involved in this search outside of the the method we have to make a variable I'll just call it count and let's put it here inside we're going to count one up every time so every time this is cold it's going to count one up and so here I'm just going to so let's call this right so it says four when we are trying to find 276 it's going through four nodes okay I hope you got a good understanding of how binary search trees work yeah that's it for today I thank you so much for watching this video please subscribe and I will see you in the next video bye [Music]

Channel: Junmin Lee

Views: 9,810

Keywords: data structures, golang, leetcode, coding, programming, coding tutorial, programming tutorial, algorithms, computer science, stacks and queues, software development, binary search tree, binary tree, leetcode solutions, go

Id: -oYitelECuQ

Length: 14min 20sec (860 seconds)

Published: Mon Jul 06 2020