Recitation 5: Recursion Trees, Binary Search Trees
Вставка
- Опубліковано 5 чер 2024
- MIT 6.006 Introduction to Algorithms, Fall 2011
View the complete course: ocw.mit.edu/6-006F11
Instructor: Victor Costan
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu
Victor is a genius, he make everything so clear and simple
Man , you save me again and again. Thanks MIT
This class was just so good, well explained and I was able to understand most of it from begining to end, now it is time for the longest part, take a book and implement it!!
most valuable 360p youtube video. danke mit!
14:10 Binary Search Trees discussion starts
man far better than the lecture i got today.
inorder successor begins at 35:40
Lucid explanation :)
Hold up, the O in Big O notation stands for order of?
as a self-taught developer, I feel dumb
duh? what did you think it stood for? just curious
@@blasttrash I thought it stood for Ogre, honoring your mom...
@@blasttrash I would like to know tooo xd
@@anonimous4798 nah dude, he was honoring your mom.
blasttrash Good one
42:17 Binary Tree Deletions
i love you
Why is necessary to change n to cn? Why recursion is infinite? It seems to me that there are finite recursions or nodes until it contains only one element.
This instructor has such illegible handwriting (not bad but how to differentiate the letters) yet his accent is weirdly comforting...I came here to freshen up my recursion stuff and can't believe i am actually getting through them
27:15 Who got the reference? 😏
N/(2^x) = 1, so that 2^x = N, i.e. x = logN
I can't really find the video of Recitation 4, not even on the OCW site. Does it exist somewhere?
ranalynamic Sorry, Recitation 4 video is not available.
@@mitocw :'(
very good thanks :)
Why is not there a recitation lecture 4? :(
We are not sure why. We checked the authoring database for notes, but nothing was listed. There are a number of possible reasons: wasn't recorded (date/time was changed and the video crew wasn't notified), audio was bad/missing, recitation was not held... just to name a few.
@@mitocw there is a recitation 4 video in Victor's channel, I think you can help to put it in this playlist
@@nickleefly No, it's not. ua-cam.com/video/i9zdH3GtEf0/v-deo.html This was the uncut version of this video.
What confused me is that right at the end there is talk of computing the minimum from more minima but isn't there a global minimum? (if you go left down the tree only)
i think, in 22.37 min lecturer draw complete binary tree, not full binary tree
Good catch that's definitely what he meant to say.
can anyone please send me the link to insertion of BST
42:21 Deletions
Could u pls provide the link for insertion and search 2
10:03 ... still waiting.
if we can hold data in array and linkedlist why would we need Trees for store /delete /update operations?
U can't do binary searh tree in linked list but can insert/remove quickly;
And u can do binary search in sorted array but can't remove/insert quickly (u have to move the entire array),
So binary search tree is a way to solve that problem.
It is explained in a video about binary search tree that is also from this channel but from a later course iirc
@Nasy Rest That question is dealt with in great detail in 5th lecture of this course. And reply by Koyanis is a good summary of that
@ZackTactical34 thank you
How can I reach the problem sets that he talks about? thanks
You can see the course materials on MIT OpenCourseWare at: ocw.mit.edu/6-006F11. Best wishes on your studies!
Does anyone have the code he talks about?
The notes and code files are available in the full OCW course site: ocw.mit.edu/6-006F11. Open up Recitation 5 in the tabbed video player, and click on the "Recitation Notes" tab for materials related to the session. Good luck with your studies!
@@mitocw OCW off-center wicked. Thanks!
What is order H??
The height of the tree
H is the height of the tree, which in a BST is not guaranteed to be log(n) because a BST can be unbalanced, thus O(H)
why
For the degenerate unbalanced tree that keeps going to the right, why is O(N) for searching? i mean its ordered right since it keeps increasing, so we can still using binary search right?
The degenerate tree is like a sorted list indeed.
But binary search only applies to arrays, which give you random access.
Random access means you can access any element at constant time.
With trees or lists, you can't do that; you have to follow the pointers.
That's why you can't use the binary search algorithm.
@@luizfelipels7 100% true. a good word for this is being indexable
Way to flood my sub box, guys -_-
BST implementation in py ♥
github.com/RaviPabari/DataStructures-Algorithm/blob/master/Tree/Binary%20Search%20Tree/BST.py
59:00 Nobody will find out that you told people how to do it for everything. We'll keep it a secret :)
hellow anyone to sugegst me book with solved exercises in recutions??i be grateful for that help!!thanks
This course does feature assignments with solutions. See ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/assignments/ for details. We hope this helps.
good explanation not perfect but just good enough
good explanation not perfect but just good enough