6. Binary Trees, Part 1

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

% 2 400

MIT 6.006 Introduction to Algorithms, Spring 2020
Instructor: Erik Demaine
View the complete course: ocw.mit.edu/6-006S20
RU-vid Playlist: ru-vid.com/group/PLUl4u3cNGP63EdVPNLG3ToM6LaEUuStEY
This is the first of two lectures on binary trees. This lecture discusses binary tree terminology, tree navigation, and dynamic operations. These are explored in two applications: sets and sequences.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu
Support OCW at ow.ly/a1If50zVRlQ
We encourage constructive comments and discussion on OCW’s RU-vid and other social media channels. Personal attacks, hate speech, trolling, and inappropriate comments are not allowed and may be removed. More details at ocw.mit.edu/comments.

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

13 сен 2021

Ссылка:

Скачать:

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

Добавить в:

Мой плейлист

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

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

@ParthPatel-vj2zv 2 года назад

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)

@shyamtripathi2097 9 месяцев назад

Thank you. Where can we get the recitation (to see the python code)?

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

He came wearing a root shirt. Legend

@Ayushr0129 2 месяца назад

Yeah, it’s now that I am realizing that 😂

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

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.

@stanfordy9104 Год назад

nerd

@xugeorge7030 Год назад

@@stanfordy9104 says someone who literally has stanford in one's username

@flymykim 7 месяцев назад

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

@GaioSonase 11 дней назад

@@flymykim the very same knowledge was always available for pennies on the ivy league dollars. It's not really about the knowledge itself.

@GaioSonase 11 дней назад

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

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

Great lecture. I always had confusion about the successor - thanks for the clarification.

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

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!

@anjanikumarjha209 Год назад

are there any data structures course of same quality please suggest

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

Thanks MIT for providing great content.

@pif5023 Год назад

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!

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

Thank you for uploading this lecture!

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

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

@linonator 8 месяцев назад

These classes pay so many dividends. It’s just amazing!

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

I know the comments here get melodramatic but seriously: thanks, it means a lot to have this available

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

Thanks MIT. Thank you Erik!

@originalgamer4962 Год назад

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

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

so this is newer version of lecture of ?

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

Thank you so much, what a great lecture, respect from Pakistan!

@sushanthreddy5513 Год назад

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.

@gokulakrishnancandassamy4995 9 месяцев назад

Exactly, even I thought the same! He even says that it is that parent that will be the successor!

@mohammadsalehdehghanpour9856 Месяц назад

Is it explained in previous lectures hiw to achieve O(1) for insert first with dynamic array?

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

the leaf analogy is so funny

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

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?"

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

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.

@hoze540 7 месяцев назад

43:42 isn't A's predessesor supposed to be b after being swapped with E?

@suindude8149 3 месяца назад

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.

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

Thanks

@madoben3294 Год назад

at 30:17 of the video. Aren't we supposed to return node.parent since that is the successor?

@paulluckner411 3 месяца назад

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.

@kafychannel Год назад

thanks a lot was extremely useful

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

I think he forgot to explain how to delete in the case if node.right, could anyone please explain this point? thanks! 47:30

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

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

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

isnt the traversal result for the tree FDEBAC? as per inorder traversal

@paulluckner411 3 месяца назад

No, it is FDBEAC. Note, B is before E, similar as A is before C.

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

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

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

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.

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

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

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

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

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

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

@soonshin-sam-kwon Год назад

Thanks a lot.💎🎓🔥💯

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

🌳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?

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

Yo is it just me or does that chalk look super smooth to write with ???

@suhasdotcom Год назад

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

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

this is where peter parker wanted to go for his graduation.

@user-nu2sz2wg3i 2 года назад

Emotional damage for node A

@im-ls8tm Год назад

1:04

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

I wonder why can't they use digital white board or with a projector for explanation than black board. Easy to use and explain

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

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.

@pyrocrackermillenium675 2 месяца назад

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.

@hoze540 7 месяцев назад

actually i get it now, G comes before B