Python Data Structures #5: Binary Search Tree (BST)

Просмотров 168 тыс.

% 2 938

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/bfaure/Python_Data_Structures/blob/master/Binary_Search_Tree/main.py
(PYTHON 3)
► Code for this lesson: github.com/bfaure/Python3_Data_Structures/blob/master/Binary_Search_Tree/main.py
► BST Deletion Function ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-Zaf8EOVa72I.html
► BST Validator Function ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-azupT01iC78.html
****
► Video series covering various common algorithms in Python:
ru-vid.com/group/PLEJyjB1oGzx2h88Tj90B5_HadLq339Cso
► Video series covering GUI development in Python (WIP): ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-IpTG4KixVew.html
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.

Опубликовано:

11 сен 2017

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 207

@nackyding 4 года назад

Best walk through implementation of BST on RU-vid by far! Thank you so much.

@BinaryAdventure 2 года назад

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.

@chaoticpringle2578 5 лет назад

Thanks for this! I was having trouble understanding my professor when we learned this today.

@chloeliu9207 5 дней назад

After searching thousand of videos at ytb, this tutorial is the most helpful and insightful! thanks!

@BrianFaure1 5 дней назад

@@chloeliu9207 Awesome news! Happy the video helped you ✌️

@nancycarlson548 4 года назад

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.

@davidarthurpaul 6 лет назад

Fantastic video and great explanations. Rarely comment but please keep this up

@HarveyXE 3 года назад

Thank you for being clear about the values on the left and right side of the tree. Very helpful detail.

@333robel 5 лет назад

The sound at 7:39 super motivating... and the energy level from 7:25-7:40 is just threw threw the roof.

@akizzlebrand4657 4 года назад

Best video and code I've seen on this and I've been looking for weeks! Thank you!

@BrianFaure1 6 лет назад

Part 2 (deletion) of the Binary Search Tree lesson can be found here: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-Zaf8EOVa72I.html

@karthikudupa5475 4 года назад

Thanks a lot Brian, I was actually looking for this. Well explained.

@autismo1969 2 года назад

very good explanation of binary search trees. straight to the point. explained each of the parts very well. thanks a lot!

@rwothoromoelijah 5 лет назад

Very good explanations. Much appreciated!

@vishesh_soni 4 года назад

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.

@Samuel-lm1wb Год назад

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

@boohoo334 4 года назад

Such an underrated channel

@fredesch3158 2 года назад

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.

@shreehari2589 2 года назад

I agree, Two classes is the way best way to implement any non linear data structure!

@jennaalden3658 3 года назад

awesome video! in the function ` fill_tree`, you don't need to return tree, it does it "inplace"

@ankittank2098 4 года назад

Amazingly explained!! Hats Off

@siddharthadas86 6 лет назад

fantastic explanation! Thanks again.

@zakiahmedqureshi4358 5 лет назад

easy to understand and pretty well summed up the BST. thanks :)

@BrianFaure1 5 лет назад

Thanks for watching!

@bright1402 3 года назад

Very concise and informative! Thanks man

@arturfil 4 года назад

Excellent explanation! Great work!

@wahtsfgsgwwwsxq 4 года назад

Excellent explanation! Thank you!

@nikitaizmaylov4888 4 года назад

THANKS my guy) Definitely deserve the recognition)

@natalieweishuhn521 5 лет назад

Fantastic video~ You're the first person that has explained this in a way that makes sense!! THANK YOU

@shrikantkarki4966 6 лет назад

Superb explanation and coding.Helped a lot.Thanks Brain

@marco.nascimento 5 лет назад

Amazing explanation, very nice!!

@carlavirhuez4785 2 года назад

Finally! I undertand BST! Thanks a lot for yoru help

@nicknaik 5 лет назад

Excellent, thanks!

@jasonzhang6534 3 года назад

thanks for the video! well explained, good pace

@azizas9366 6 лет назад

Very clear since I am coming from Java.

@joshiravishankar 4 года назад

Fantastic video, can be understood quickly :)

@MCNeko6554 Год назад

Thank you, helped me finish my homework without losing my mind x'D

@AbhishekSingh-cx5dr 6 лет назад

this is just awesome..sir thanks

@alexsugarman9511 4 года назад

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

@tomporkka5273 4 года назад

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?

@JoaoCfgc 5 лет назад

Great video man very useful!

@rakheekulkarni2708 6 лет назад

excellent video, very informative

@BrianFaure1 6 лет назад

Thanks Rakhee!

@EnglishRain 3 года назад

Great tutorial, thanks a ton!

@brianwahome5789 6 лет назад

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!

@BrianFaure1 6 лет назад

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: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-azupT01iC78.html

@ashwinimandani2829 4 года назад

Great explanation sir..

@wenchehsu8915 6 лет назад

Nice video! Expecting to see the deletion part of BST :D

@BrianFaure1 6 лет назад

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.

@wenchehsu8915 6 лет назад

Brian Faure I'm so appreciate :D Thank you for your effort on these nice videos

@BrianFaure1 6 лет назад

Just finished the video covering the deletion function: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-Zaf8EOVa72I.html , thanks again for the kind comments!

@wenchehsu8915 6 лет назад

Thank you! I have watched it immediately :D Looking forward to your following videos!

@rahularvindshinde 6 лет назад

this is really helpful...

@RomanMamedov333 4 года назад

Thanks for this video.

@rizkifitrarrijal9138 3 года назад

thank you so much for the explanation

@wojohn6441 2 года назад

best binary tree tutorial ever!

@shibajichatterjee3190 6 лет назад

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.

@mrhobojim6098 2 года назад

Really helpful thankyou

@yaseen1478 5 лет назад

7:39

@BrianFaure1 5 лет назад

lmao

@GurfatehSinghDhaliwal 5 лет назад

A wild Fart Spotted

@Draco-pe4fg 3 года назад

@sifagayev7793 Год назад

Great tutorial

@djuka8121 4 года назад

could you please explain me a little bit more about _print_tree(self, cur_node) function?

@subashchandrapakhrin3537 3 года назад

Thank You Brian

@vincentluong6238 6 лет назад

Needs more views

@ardsnijders7777 5 лет назад

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.

@mykinvincible 5 лет назад

nice video, i am not able to understand how does the display method work. can you please explain that ?

@neuralnets6656 5 лет назад

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.

@arthurzhang7868 5 лет назад

great explanation!

@BrianFaure1 5 лет назад

Thanks Arthur!

@daliacruz759 6 лет назад

This is a great video! Did you ever make a video on the different traversals? If not, it would be cool to see one.

@BrianFaure1 6 лет назад

Hi Vanessa, unfortunately I haven't yet gotten around to making that but it is on the queue. Thanks for watching!

@davidgutierrezarias3309 6 лет назад

@Brian Faure ,in an interview do you recommend to follow your approach , I mean break in two functions. Thanks

@BrianFaure1 6 лет назад

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!

@gokulraviteja5209 6 лет назад

Video on segment trees,Fenwick trees...

@kajalmondal9745 2 года назад

Thank you so much sir

@yuanyuan23191212 4 года назад

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?

@yuanyuan23191212 4 года назад

ah, just realize 'Value already in tree' comes from insertion, not printing

@johndu9255 4 года назад

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 !

@kirimi782 5 лет назад

thanks @BrianFaure.

@irisx6619 5 лет назад

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.

@ilkinaliyev1044 5 лет назад

No need to BST, you don't sort elements. Hashing does fit here actually

@ayeinsayali1340 3 года назад

great video man .. thumbs up from me

@rohitkumarj632 4 года назад

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.

@MahmoudElgassier 6 лет назад

Thank you so much, this is amazing. Only have one question: I want to traverse ALL nodes that are under a SPECIFIC node that is specified by user. I know I can use the height method as an example, but I can't comprise the logic necessary to return every single value under a specific node. Any help with that?

@josephnke9324 3 года назад

My answer might be too late. It is pretty simple to do that. you can use the search function on the tutorial and once you found the target node, you can use the *pointer* that has that value and pass it as a parameter to the _print_tree function. It will print you all the leaves of that node including the target node.

@faheemkamel7952 3 года назад

@@josephnke9324 2 years late mate

@oishikachaudhury3718 5 лет назад

Not related to data structures but can you please do a Github tutorial video? Thanks!

@-mwolf 3 года назад

thx really helpfull

@kritiohri2950 6 лет назад

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)

@BrianFaure1 6 лет назад

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.

@kritiohri558 6 лет назад

Thanks Brian for the wonderful explanation

@user-hs7qg5tt8t 6 лет назад

thanks

@avhishekbiswas4251 5 лет назад

in the insert function , in else block why is there a '_' before insert ?? are we just calling the insert recursively?

@isha6510 5 лет назад

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?

@adeolaogunleye7965 2 года назад

Can i add the new root value at the binary_search_tree __init__

@jingyuchang1885 6 лет назад

Thank you very much Brian!! Really good video! I noticed in your code which you posted in github is actually not the same as the code in the video. You added parent pointer in github. You used the parent pointer in insert function and deletion function. I wonder is there any advantage to have the parent point? Or it's just easy for the deletion function?

@BrianFaure1 6 лет назад

Hi Jingyu, the parent pointer is mostly just to simplify the deletion function. When we delete a node we need to alter the parent (so it no longer points to the node we wish to delete) and if we didn't include a parent pointer we would need to traverse through the tree to find the parent before we could actually perform the deletion, which could take a while if our tree was fairly large. The parent pointer is also involved in the insertion function but all we do there is set it correctly when we insert a new node. I explain it a bit more in the deletion video but when we call delete_value (which is a passed a value in the tree) we still _do_ have to traverse through the tree to find the node with that value, so the parent pointer only really increases the efficiency of the 'delete_node' function.

@jingyuchang1885 6 лет назад

Thank you very much Brian! You explained very clear! I literally wrote down every single word you said in the videos as notes cause my native language is not English. Sometimes I need to read the notes again after the video to make myself really understand! You videos really helped me a lot! I will watch all your videos and hope you will make more videos!! Thanks again!

@jimmorrisshen 6 лет назад

Super nice video. I love your code of the BST. It will be good if the code is posted online. Also, for the private method, name is under the double underscore will also work, right? I found the lib of python is using double underscore for all the private functions.

@BrianFaure1 6 лет назад

Hi Jimmy, thanks for the nice comment! The code for this video can be found here: github.com/bfaure/Python_Data_Structures/blob/master/Binary_Search_Tree/main.py . Using a single underscore is more of a Python style convention than anything, it basically tells anyone using the code that they should refrain from calling the function directly (essentially making it a private function of the class, as you say) but doesn't enforce this in any way. A double underscore function or variable is actually treated slightly differently by the Python interpreter. I found a good answer on stack overflow talking about this exact thing ( stackoverflow.com/questions/1301346/what-is-the-meaning-of-a-single-and-a-double-underscore-before-an-object-name ).

@jimmorrisshen 6 лет назад

Thanks for the sharing of the code. Also thanks a lot for the link provided on the explanation of the difference of the double underscore and single underscore. It is very clear. Thanks.

@burakhanaksoy 3 года назад

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~

@fredesch3158 2 года назад

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).

@tibettenballs4962 2 года назад

No. It’s a snake to mouth paradigm. You’ll get it after much practise suqqing on knobs and snake heads.

@pedrocastro882 2 года назад

THANK YOU!!!!!!!!!!!!!!

@Wonnnebju 6 лет назад

I like your sthoyl

@BL-om2hn 6 лет назад

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.

@BrianFaure1 6 лет назад

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 ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-_pnqMz5nrRs.html

@BL-om2hn 6 лет назад

Thank you so much!

@rahadulislamrahat328 6 месяцев назад

Do you have video in Graph a nd algorithm

@Lorenzo13968 5 лет назад

I love you !!!

@utkarshpol123 3 года назад

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

@VibhaDhar 6 лет назад

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.

@BrianFaure1 6 лет назад

Thanks! Sure thing, I'll do a vid on the different traversal methods and build off the BST code from this video.

@lenaerbs8359 5 месяцев назад

@@BrianFaure1 I want to see these videos. Where are they?

@lilysu2529 4 года назад

the fast forward sounds now reminds me of animal crossing XD

@RaniLink 3 года назад

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))

@zzobaer09 Год назад

thanks bro

@satishchandra4386 5 лет назад

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

@BrianFaure1 5 лет назад

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

@satishchandra4386 5 лет назад

Thanks!!

@animeknowledge8381 4 года назад

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

@animeknowledge8381 4 года назад

had to set in class node that self.value = value and not None it was overwriting my values in the node constructor

@AnilYadav-ut5zj 3 года назад

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.

@TheSSB007 3 года назад

I observed this too, or you can start with -1 instead of zero

@indominus9184 2 года назад

please make a video on Hashtable with linear probing

@Abhi-qi6wm 2 года назад

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 :)

@MattUKepcc816 5 лет назад

Hello Brian I wanted to ask what does line 68 do? “ tree = binary_search_tree() “ I typed the code exactly how you typed it for practice and shows it’s an undefined name. I’m coding on Python 3.6 Thanks!

@BrianFaure1 5 лет назад

Hey Matt, "tree=binary_search_tree()" will set the 'tree' variable equal to a newly created instance of the binary_search_tree class, if this isn't working for you make sure that you named the class 'binary_search_tree'. If you did, feel free to share your code on repl.it and I can take a look for you.

@MattUKepcc816 5 лет назад

Yes its still not working for me, even after changing variables and class names. Heres my code: repl.it/@miglesias4/ProductiveRawQuadrant Thank you for taking the time to assist me much appreciated!

@BrianFaure1 5 лет назад

That link seems to be broken, getting a 404 when trying to go to it.

@MattUKepcc816 5 лет назад

This one should work: repl.it/@miglesias4/BinarySearchTree

@BrianFaure1 5 лет назад

Okay, I think I fixed the issue you were having repl.it/repls/ShockingClientsideTutorial , the problem was that in your 'init' functions you only had a single underscore '_' on each side of 'init' whereas, to declare a Python class constructor you need double underscores '__'. I also removed the first 'self' parameter from your recursive calls to _insert because you don't need to specify 'self' when calling a class member function, only when defining it. There were some other minor naming issues I fixed up so it should be working now.

@saideepspeaks 3 года назад

💥💥

@ashishjain3732 4 года назад

great

@data9051 Год назад

nice

@wonjaehwang7670 5 лет назад

What kind of keyboard do you use?

@BrianFaure1 5 лет назад

corsair k65 rgb with Cherry red keycaps :)

@wonjaehwang7670 5 лет назад

@@BrianFaure1 They sound great :)

@mahyarsedigh6203 4 года назад

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?

@BrianFaure1 4 года назад

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.

@mahyarsedigh6203 4 года назад

@@BrianFaure1 Thanks Brian