0:00 intro 4:00 what is a binary tree 9:10 subtree, depth of a node, height of a node, height of a tree 16:24 traversal order of a tree 20:32 traversal operations 33:13 insert and delete operations 47:20 implementing a set with a tree (BST)
true, but im sure this signals some huge change to how the industry will operate. This knowledge, being taught with this much clarity, used to cost tens of thousands of dollars. it can only mean it no longer does...
@@flymykim What I am trying to say is that the same knowledge could always be found in any university and even outside of university. The true value isn't really in the knowledge--a library is more than enough for that--but the people, the instruction, and the environment.
What strikes me is that these lectures are the exact same as the computer science lectures we get at my very low ranked public university. But the difference is that the students in the room have better GPA and accolades than most students in the country. We all learn the exact same things, but the difference is what we do with this knowledge. That’s what makes MIT different. Thank you for posting this for free. :))
There’s no parent pointer in tree given generally , as tree is generally defined with left and right pointers but this lecture provides the idea of how to think like a problem solver
Very engaging and informative class, I look through all the online sources, this is the only high-quality algorithm course that is free and python-based. I learned a lot from it! Loved it!
Very interesting and educational course; after searching all internet resources, this is the only excellent, free, Python-based course on algorithms. It taught me a lot of things
Thank you for sharing this lesson!! As a self thought professional this really gave me ahas moment! For better or worse I was hired before I could dive deep into algos and these lessons are gold!
At 29:17, I think it should be "return node.parent" instead of "return node" as node.parent would then be the first parent with a left-child while moving up the tree.
The depth and the breadth first search would be the representation criteria for the data stored inside the memory thus the Information science has got a great evolution. The most efficient search criteria may be having the best case in case of a particular structure namely BFS would be a faster in time complexity than DFS. BFS could be implemented by using the any directional criteria using Stack as the structural unit.
🌳Could you provide a justification for why we need to 🔁swap 🔁values while doing deletion instead of just overwriting the value of a current node `A` with a value of node `B` ? We are going to delete🚮 `B` anyway, so why bother writing something there?
Because, and that was mentioned in this lecture, the sub-roots can sometimes sort of copy the insert and create several records of the same value. In order to eliminate that possibiity, insert_bf and insert_af is used.
I believe the given notation is not quite clear. While walking upwards we need to check if we are going up a left branch and simultaneously update our current node. If it was a left branch then return the updated/current node.
@42:46 Hello Professor Demaine. With respect I want to ask that why don't we swap A and successor(A) (H in this case). It'd be much easier to remove that leaf.
You can link another dynamic array to the front of the other dynamic array, and maintain both at the same time. One starts from index 0 and the other goes before 0. The details were mentioned in one of the previous lectures tho. Based on this you get insert/delete first in O(1) amortised time just like ins/del last in a regular dynamic array.
@@mittunsudhahar634 Do you mean like a circular array where you can define where the array starts so you can expand the array in both directions when needed.
@@ianholloway9493 Kind of a similar concept but nah I literally mean two dynamic arrays linked together, the second array allows for insertion/deletion at the front of the array, and every so often you need to rebuild the arrays to reorganise them but that happens few enough times that you can call it amortised O(1). They explain way better than I do in one of their videos.
@@ianholloway9493 I think Mittun Sudhahar says that for example, for an array A, if A[0] is the first but you need to insert a value before A[0], then you can define another array B, that B[i] represents A[-i-1], that like use B[0] to represent A[-1], but you should maintain both A and B. This is a method but seems didn't explain what nika chachua asked
I find that the instructor writing on the blackboard while talking gives the perfect pacing. Digital stuff encourages the use of pre-made slides, and they kill pacing. The soft noise of the chalk also contributes to the pacing.
I feel like it also demonstrates a useful skill to the students. Explaining from near-scratch is a useful skill for collaborating in environments without so much established theory.
I might be dumb, because I don't understand almost nothing of these MIT lectures. They explain with very few practical or simulation examples, so it's hard to understand
Take the prerequisite courses until 90% of the course is understandable. It is very well explained so I would work on your foundations . We all started in a similar place
0:00 intro
4:00 what is a binary tree
9:10 subtree, depth of a node, height of a node, height of a tree
16:24 traversal order of a tree
20:32 traversal operations
33:13 insert and delete operations
47:20 implementing a set with a tree (BST)
Thank you. Where can we get the recitation (to see the python code)?
deletion ua-cam.com/video/76dhtgZt38A/v-deo.html
Thank you very much MIT. Please do not ever stop this life changing work. Those who dream of studying in MIT can fulfil it here.
nerd
@@stanfordy9104 says someone who literally has stanford in one's username
true, but im sure this signals some huge change to how the industry will operate. This knowledge, being taught with this much clarity, used to cost tens of thousands of dollars. it can only mean it no longer does...
@@flymykim the very same knowledge was always available for pennies on the ivy league dollars. It's not really about the knowledge itself.
@@flymykim What I am trying to say is that the same knowledge could always be found in any university and even outside of university. The true value isn't really in the knowledge--a library is more than enough for that--but the people, the instruction, and the environment.
What strikes me is that these lectures are the exact same as the computer science lectures we get at my very low ranked public university.
But the difference is that the students in the room have better GPA and accolades than most students in the country.
We all learn the exact same things, but the difference is what we do with this knowledge.
That’s what makes MIT different.
Thank you for posting this for free. :))
Not really. I think you really don't know what MIT is.
There’s no parent pointer in tree given generally , as tree is generally defined with left and right pointers but this lecture provides the idea of how to think like a problem solver
Very engaging and informative class, I look through all the online sources, this is the only high-quality algorithm course that is free and python-based. I learned a lot from it! Loved it!
are there any data structures course of same quality please suggest
He came wearing a root shirt. Legend
Yeah, it’s now that I am realizing that 😂
Great lecture. I always had confusion about the successor - thanks for the clarification.
Very interesting and educational course; after searching all internet resources, this is the only excellent, free, Python-based course on algorithms. It taught me a lot of things
Thank you for sharing this lesson!! As a self thought professional this really gave me ahas moment! For better or worse I was hired before I could dive deep into algos and these lessons are gold!
At 29:17, I think it should be "return node.parent" instead of "return node" as node.parent would then be the first parent with a left-child while moving up the tree.
Exactly, even I thought the same! He even says that it is that parent that will be the successor!
These classes pay so many dividends. It’s just amazing!
Thanks MIT for providing great content.
I know the comments here get melodramatic but seriously: thanks, it means a lot to have this available
The depth and the breadth first search would be the representation criteria for the data stored inside the memory thus the Information science has got a great evolution.
The most efficient search criteria may be having the best case in case of a particular structure namely BFS would be a faster in time complexity than DFS.
BFS could be implemented by using the any directional criteria using Stack as the structural unit.
Thanks MIT. Thank you Erik!
Thank you so much, what a great lecture, respect from Pakistan!
why would i every need to insert before or after in BTS 36:00 it supposed to be sorted automatically without me doing any thing
Thank you for uploading this lecture!
29:13, should it be return node.parent? i am confused
anybody explain please
the leaf analogy is so funny
Yo is it just me or does that chalk look super smooth to write with ???
🌳Could you provide a justification for why we need to 🔁swap 🔁values while doing deletion instead of just overwriting the value of a current node `A` with a value of node `B` ? We are going to delete🚮 `B` anyway, so why bother writing something there?
very goood lecture
I thought the edges in a binary tree are directional, one-way relationship (parent to child only). Right?
why did we not swapped a with d at (42.11-video) , that would be the leaf node and we could immediately remove the a
Can someone clarify "why insert_before and insert_after is required in BST ADT when insert operation takes care of inserting where it belongs to?"
Because, and that was mentioned in this lecture, the sub-roots can sometimes sort of copy the insert and create several records of the same value. In order to eliminate that possibiity, insert_bf and insert_af is used.
41:04 delete
43:42 isn't A's predessesor supposed to be b after being swapped with E?
nah, left child comes first for every node
at 30:17 of the video. Aren't we supposed to return node.parent since that is the successor?
I believe the given notation is not quite clear.
While walking upwards we need to check if we are going up a left branch and simultaneously update our current node. If it was a left branch then return the updated/current node.
Thanks a lot.💎🎓🔥💯
I think he forgot to explain how to delete in the case if node.right, could anyone please explain this point? thanks! 47:30
He did explain it. In case of node.right, we swap the node item with its successor because it would be lower in the tree
so this is newer version of lecture of ?
@42:46 Hello Professor Demaine.
With respect I want to ask that why don't we swap A and successor(A) (H in this case).
It'd be much easier to remove that leaf.
can someone explain pls in dynamic arrays insert/delete_first takes O(1) a , but it have to shift all elements so how is that O(1)?
You can link another dynamic array to the front of the other dynamic array, and maintain both at the same time. One starts from index 0 and the other goes before 0. The details were mentioned in one of the previous lectures tho. Based on this you get insert/delete first in O(1) amortised time just like ins/del last in a regular dynamic array.
@@mittunsudhahar634 Do you mean like a circular array where you can define where the array starts so you can expand the array in both directions when needed.
@@ianholloway9493 Kind of a similar concept but nah I literally mean two dynamic arrays linked together, the second array allows for insertion/deletion at the front of the array, and every so often you need to rebuild the arrays to reorganise them but that happens few enough times that you can call it amortised O(1). They explain way better than I do in one of their videos.
@@ianholloway9493 I think Mittun Sudhahar says that for example, for an array A, if A[0] is the first but you need to insert a value before A[0], then you can define another array B, that B[i] represents A[-i-1], that like use B[0] to represent A[-1], but you should maintain both A and B. This is a method but seems didn't explain what nika chachua asked
thanks a lot was extremely useful
Thanks
Is it explained in previous lectures hiw to achieve O(1) for insert first with dynamic array?
this is where peter parker wanted to go for his graduation.
isnt the traversal result for the tree FDEBAC? as per inorder traversal
No, it is FDBEAC. Note, B is before E, similar as A is before C.
1:04
I wonder why can't they use digital white board or with a projector for explanation than black board.
Easy to use and explain
I find that the instructor writing on the blackboard while talking gives the perfect pacing. Digital stuff encourages the use of pre-made slides, and they kill pacing. The soft noise of the chalk also contributes to the pacing.
I feel like it also demonstrates a useful skill to the students. Explaining from
near-scratch is a useful skill for collaborating in environments without so much established theory.
boht hard
xD great lec
normie
Emotional damage for node A
actually i get it now, G comes before B
use Internal Pointer Variable
Day 7 present
What about the non-binary trees? You have to be inclusive
Extending a binary tree to having more than two children is pretty straight forward.
@@ShredST It was a joke
wait until Twitter sees this
@@edwardnjogu159 lmao
Gotta learn about them genderfluid trees
😊😊😊😊😊😊😊😊🇺🇸🇺🇸🇺🇸🇺🇸
"I'm just a leaf you know"
I might be dumb, because I don't understand almost nothing of these MIT lectures. They explain with very few practical or simulation examples, so it's hard to understand
Take the prerequisite courses until 90% of the course is understandable. It is very well explained so I would work on your foundations . We all started in a similar place