Python Data Structures #5: Binary Search Tree (BST)
Вставка
- Опубліковано 1 жов 2024
- Code below... In this video we'll begin by discussing the basics of the Binary Search Tree data structure, and towards the end, we'll move over to a coding editor and implement the ideas in Python code. Planning an extra video covering the different traversal methods you can choose from when using a BST, possibly another focused solely on the BST deletion function as well.
(PYTHON 2)
► Code for this lesson: github.com/bfa...
(PYTHON 3)
► Code for this lesson: github.com/bfa...
► BST Deletion Function • Binary Search Tree (BS...
► BST Validator Function • Binary Search Tree (BS...
****
► Video series covering various common algorithms in Python:
• Python Algorithms
► Video series covering GUI development in Python (WIP): • Python GUI Development...
In computer science, binary search trees (BST), sometimes called ordered or sorted binary trees, are a particular type of container: data structures that store "items" (such as numbers, names etc.) in memory. They allow fast lookup, addition and removal of items, and can be used to implement either dynamic sets of items, or lookup tables that allow finding an item by its key (e.g., finding the phone number of a person by name).
Binary search trees keep their keys in sorted order, so that lookup and other operations can use the principle of binary search: when looking for a key in a tree (or a place to insert a new key), they traverse the tree from root to leaf, making comparisons to keys stored in the nodes of the tree and deciding, based on the comparison, to continue searching in the left or right subtrees. On average, this means that each comparison allows the operations to skip about half of the tree, so that each lookup, insertion or deletion takes time proportional to the logarithm of the number of items stored in the tree. This is much better than the linear time required to find items by key in an (unsorted) array, but slower than the corresponding operations on hash tables.
The way this guy doesn't put spaces around commas and equality operators drives me nuts
Yeah I've watched a lot of these. This video really helped me to re-grasp the concept well; it's hard to put into words but you are well-spoken and direct, which I learn best from. You do not ramble and wander in your presentations which is helpful for technical subjects.
Fantastic video and great explanations. Rarely comment but please keep this up
Best walk through implementation of BST on UA-cam by far! Thank you so much.
def insert(self,data):
if self.root:
self._insert(data,self.root)
else:
self.root=node(data)
def _insert(self,data,curr_node):
if curr_node is None:
curr_node=node(data)
return curr_node
if datacurr_node.data:
curr_node.right=self._insert(data,curr_node.right)
else:
print( 'Value already exists')
return None
return curr_node
Implemented a shorter version of the insert method :)
Part 2 (deletion) of the Binary Search Tree lesson can be found here: ua-cam.com/video/Zaf8EOVa72I/v-deo.html
the fast forward sounds now reminds me of animal crossing XD
7:39
lmao
A wild Fart Spotted
ha
After searching thousand of videos at ytb, this tutorial is the most helpful and insightful! thanks!
@@chloeliu9207 Awesome news! Happy the video helped you ✌️
Thanks for this! I was having trouble understanding my professor when we learned this today.
It's better to write "is None" instead of "== None":
stackoverflow.com/questions/3257919/what-is-the-difference-between-is-none-and-none
awesome video! in the function ` fill_tree`, you don't need to return tree, it does it "inplace"
could you please explain me a little bit more about _print_tree(self, cur_node) function?
For the _height() function, shouldn't you return cur_height -1 because even if its None, you have already incremented current height by 1 via the recursive functions.
I observed this too, or you can start with -1 instead of zero
What about Adding 0 to childrens that dont existm for example if left child is empty we put None there? What should be the logic.
You know to prnt sth like this
[1 2 3 4 None 5 6 None None]
Thank you, helped me finish my homework without losing my mind x'D
tree.print_tree() in python3. took me a half hour figure out why it wasnt printing out.
The sound at 7:39 super motivating... and the energy level from 7:25-7:40 is just threw threw the roof.
Finally! I undertand BST! Thanks a lot for yoru help
Using Python 3.8 so may be the reason but it is just calling the place in memory and not the value at the pointer so im getting a typeError when calling value
had to set in class node that self.value = value and not None it was overwriting my values in the node constructor
Brian, another amazing video!! I want to ask a question though. What is the main reason you portion a function to private and public? Just want to understand the logic behind. Thanks for the tutorial~
I'm not the creator, but as far as I understood the private function takes as an additional parameter the node to analyze, the public one assumes the beginning of the tree (or the root of the tree).
No. It’s a snake to mouth paradigm. You’ll get it after much practise suqqing on knobs and snake heads.
You find the tree's height much simpler with:
_height(self, current_node):
return -1 if current_node is None else 1+max (self_height(current_node.left), self_height(current_node.right))
So yes, please make a delete node video. What is great about your approach is your commentary as you are writing the code. This is sooo helpful to those of us who are still learning how to write the code as it connects to the logic of the data structure. This teaching technique is hard to find! Please keep this up and thank you.
I guess you dont need to check if self.root == None in the height function since the recursive call takes care of a None condition. you can just have "return self._height(self.root, 0)" as the only line in the height function.
Hi Brain, I met a problem with this code, the "search" function does not return "True" when the number was generated by the "Random function", but inserted number is fine. do you have any idea about this? Thank you !
Can i add the new root value at the binary_search_tree __init__
please make a video on Hashtable with linear probing
Thank you! very helpful, watched like idk 6 or so videos on youtube but they were mad confusing especially on the recursion part. You were clear thank you
Historically BST right node uses ">=," allowing for duplicate keys.
when _search called recursively, doesn't it check the value first and if it is equal to what we are looking for it should return True; I am confused in your first run you got False False; why you had to add return statement before each of those calls?
Hi Mahyar! Yes it does return True if the current value is equal to what we're searching for but if its not it needs to recurse lower into the tree (in the recursive function calls). The issue with the first approach was that when we recursed into the tree we weren't propagating the return values back up the function stack i.e. if one of the lower search calls found True we wouldn't return that, we would continue to the bottom of the function and just return False. Please let me know if this makes sense.
@@BrianFaure1 Thanks Brian
If we only want to write the left view of the tree then how can we do it . I mean with print function when i tried to print only the right part of the tree it worked properly but for the left it's not working. Can you please help me?
def insertTree(self, data):
if self.root is None:
self.root = Node(data)
else:
self.insertHelper(self.root, data)
def insertHelper(self, start, data):
if start is None:
start = Node(data)
print(start.data, "added successfully")
else:
if data
when in search I search for a number which is not in the list instead of false it shows an error saying non-type attribute value
Do you have video in Graph a nd algorithm
Thanks a lot Brian, I was actually looking for this. Well explained.
Don't know how people are saying the style is clean when it could use quite a bit of help (please use more space out operators and operands), but otherwise nice implementation
Adherence to PEP 8 would definitely make it clearer!
@@rockstarjazzcat Absolutely
You are a God!! Mind doing a BST validator too? Also it would be great having access to the repo you post this Code in. Thank you so much!
Thanks Brian! I've just posted the code here: github.com/bfaure/Python_Data_Structures/blob/master/Binary_Search_Tree/main.py , it also contains the logic for the deletion function which isn't covered in this video. Thanks also for the recommendation, I'll definitely do a BST validator ASAP.
Edit: BST Validator lesson can be found here: ua-cam.com/video/azupT01iC78/v-deo.html
Should have recorded the video when you gotten rid of your cold.
18:07 in 0.25x speed.......... lol...
great video man .. thumbs up from me
Great video! I have followed your linkedList video also. The code is clean and easily understandable. Can you please plan on adding DFS and BFS also.
Thanks! Sure thing, I'll do a vid on the different traversal methods and build off the BST code from this video.
@@BrianFaure1 I want to see these videos. Where are they?
isn't this @Corey_Schafer?
Very Nice and clean Code. You know I was thinking of making DS&A with python videos on youtube coz I couldn't find any. But now I have seen way better than I expected.
How to store the tree created permanently even after closing the file. And also on fetching the tree and updating, the updates must also be saved.
Why are you creating 2 classes
Can you demonstrate the code for the case where value == cur_node?
Currently, you are printing "Value already in tree" - can you demonstrate the code to handle duplicate values by replacing the cur_node with value? Thanks.
i am getting an error AttributeError: 'binary_search_tree' object has no attribute '_print_tree' please help me in this one
it is at line no - 38 please help me out
one small thing I ran into; at one point you define the fill_tree function, pass in the Tree object and re-assign the output to variable tree. However, (In my implementation) doing so reset the type of tree from to which rendered me unable to perform the tree.print_tree() method.
in the insert function , in else block why is there a '_' before insert ?? are we just calling the insert recursively?
very good explanation of binary search trees. straight to the point. explained each of the parts very well. thanks a lot!
best binary tree tutorial ever!
nice video, i am not able to understand how does the display method work. can you please explain that ?
easy to understand and pretty well summed up the BST. thanks :)
Thanks for watching!
thanks for the video! well explained, good pace
Thanks for this! Quick question, are the BST's at 00:44 and 01:28 valid or is that a typo? I'm confused by the left side where the child nodes of 7 are 2 and 6?
Really helpful thankyou
Thank You Brian
Thank you so much sir
Thanks a lot for the tutorial. Can you please make a video on creating a Huffman tree., as that is a binary three we create from the leaf to the root ( from below), I am having a hard time figuring out implementing the algorithm.
22:46 Hi Brian, could you give a more detailed explanation for the recursive part of the _height function. Like what will the left.height and right.height return if the cur.height of the left.height or right.height are not None yet.
Hi Bowen, I'll explain using the following line identifiers (A,B,C,D)...
(A) > if cur_node==None: return cur_height
(B) > left_height=self._height(cur_node.left_child,cur_height+1)
(C) > right_height=self._height(cur_node.right_child,cur_height+1)
(D) > return max(left_height,right_height)
Line A is essentially the base case of this recursive function, once we hit the child of a leaf node (which will equal 'None') we return the total height we've accumulated across the recursive calls, 'cur_height'. In line B we are starting a new recursive branch that will retrieve for us the height of the left sub-tree of 'cur_node', and similarly, in line C we start a new recursive branch to return the height of the right sub-tree of 'cur_node'. In line D we return the greater of the two heights, because the height of a node is defined as the longest distance from that node to a leaf node. It may be easier to understand if you realize this function will be called exactly once for each node in the tree (plus the 'None' children of leaf nodes), and the recursive calls would basically trace out a depth-first search of the tree, though we don't search for values rather we simply add to our found height.
In lines B and C, the reason we pass cur_height+1 as the second parameter to the _height function is that we must increment our height value by one because we are traversing down to the next level in the tree. Let me know if this cleared it up at all or if you have any further questions. If you're interested, a resource that helped me understand this function in more depth was this great tutorial by mycodeschool ua-cam.com/video/_pnqMz5nrRs/v-deo.html
Thank you so much!
thank you so much for the explanation
Not related to data structures but can you please do a Github tutorial video? Thanks!
I like your sthoyl
Fantastic video, can be understood quickly :)
THANK YOU!!!!!!!!!!!!!!
For your insert method, I would change the parameter to *args. That way you can input one, or multiple values with one insert command from your main. You just have to iterate through the args first
this is just awesome..sir thanks
Such an underrated channel
for the height can't we just use this function???
def getHeight(self, root):
if root == None:
return -1
else:
return 1 + max( self.getHeight(root.left), self.getHeight(root.right) )
Hey Avhishek, looks like it would work 👍
@@BrianFaure1 thank you.
thx really helpfull
Really nice, I was really stuck at how to start implementing, when I saw the use of 2 classes one for the node and one for the tree itself everything just clicked, I coded and it worked, THANK YOU SO MUCH, I always need a jumpstart to make my brain work and your video was just perfect.
I agree, Two classes is the way best way to implement any non linear data structure!
should give a sample output and input ,
Hi Brian..just as we are printing the value of current node or the root (print(str(cur_node.value))) , where are we printing the values of left and right child?? Only call is being made to the fucntion (self._print_tree(cur_node.left_child)) and self._print_tree(cur_node.right_child)
Hi Kriti, the left child will be printed before the cur_node and the right child will be printed after...
> self._print_tree(cur_node.left_child) # this will print the left_child (if not None)
> print str(cur_node.value) # this will print the cur_node
> self._print_tree(cur_node.right_child) # this will print the right_child (if not None)
...and because it's handled by recursion, we don't need to specifically call 'print str(cur_node.left_child.value)' or 'print str(cur_node.right_child.value)', just passing both as parameters to the _print_tree function is enough. I hope that clears it up.
Thanks Brian for the wonderful explanation
Thank you for being clear about the values on the left and right side of the tree. Very helpful detail.
Great tutorial
thanks bro
Superb explanation and coding.Helped a lot.Thanks Brain
Do you tutor?
fantastic explanation! Thanks again.
THANKS my guy) Definitely deserve the recognition)
Hi, Any chance that you can explain how to take words from a paragraph in a text file and store them in the BST?
Thanks.
No need to BST, you don't sort elements. Hashing does fit here actually
I love you !!!
Video on segment trees,Fenwick trees...
How many times did you guys have to watch this video to finally understand it thoroughly. ?
Bcz once is not enough for me.
If you're theoretically sound enough, you're good to go. :)
10 times
Excellent explanation! Great work!
great
nice
Firstly, Thanks for the beautiful videos. You are the best!!. I have a question, In _insert method, why can't we handle duplicates. Doesn't binary search tree insert the values equal to the current node to the left. In that case, can't we just have the first "if" condition as
It just depends on the specific implementation, some BSTs might put equal values to the right and some to the left, in this case I decided to omit equal values for simplicity. Without actually running it myself, I don't think there would be any issues if you used
Thanks!!
PEP 8
Thanks for your video! I have a question. This tree at first is empty. Then how come it will return 'Value already in tree!' in the first line when printing the tree?
ah, just realize 'Value already in tree' comes from insertion, not printing
@Brian Faure ,in an interview do you recommend to follow your approach , I mean break in two functions. Thanks
Hey David, for interviews I think the best approach is whatever is easiest for you to code and, more importantly, to be able to explain. I doubt you would be asked to code an entire BST for an interview but it's certainly possible, more likely would be just a single function (insert for example). When it comes to coding during interviews it's hard to know how much the interviewer is expecting of you so while you're writing if you come to a point where it would make sense to call a function to perform some action (for example if you were moving an object across a screen and would call a function to perform the x,y coordinate transform) I would say certainly call the extra function, if you have time you can fill in the logic for that later on. It's definitely better to have the higher-level program correct vs getting stuck in the weeds trying to figure out some logic in the beginning, then never actually even finishing the high level logic. For the recursive functions we use in the BST here, you could either break it into two functions (as seen in the video) or use a single function that performs all the stuff of the non-recursive function only on the first iteration (so you would need some sort of variable to check to see if you're on the first iteration or not), in this case I think breaking it into two functions makes sense but I'm sure many programmers would disagree. Good luck with the job hunt!
Very concise and informative! Thanks man
I could not understand why you are returning it .... and how value changed to True, False after returning ...
Hello Gautham! Which function are you confused about?
Thanks for this video.
Best video and code I've seen on this and I've been looking for weeks! Thank you!
💥💥
Nice video! Expecting to see the deletion part of BST :D
Haha sorry about that, I'll be coming out with a video on it soon! I'll reply again to your comment again once it's released.
Brian Faure I'm so appreciate :D Thank you for your effort on these nice videos
Just finished the video covering the deletion function: ua-cam.com/video/Zaf8EOVa72I/v-deo.html , thanks again for the kind comments!
Thank you! I have watched it immediately :D Looking forward to your following videos!
Great video man very useful!
Great tutorial, thanks a ton!
Excellent, thanks!