R2. 2-3 Trees and B-Trees
Вставка
- Опубліковано 27 лис 2024
- MIT 6.046J Design and Analysis of Algorithms, Spring 2015
View the complete course: ocw.mit.edu/6-0...
Instructor: Amartya Shankha Biswas
In this recitation, problems related to 2-3 Trees and B-Trees are discussed.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu
that's the cleanest blackboard i've ever seen
5 years later and I agree,
and I hope you are still alive and in a good health
INSERTION STARTS AT 18:20
your comment sounds dirty
Thanks
@@medievalogic hahahahhahahhahahahahahaha
@@medievalogic his name too lol
And goes on and on for all
DELETION STARTS AT 21:30
THANK WHICHEVER GOD MADE YOU. I MEAN IT. I AM NOT JOKING
INSERTION STARTS AT 18:20
DELETION STARTS AT 21:30
Thanks
Somebody should have told Amartya that he does really well here. He is knowledgeable about the subject, has good material, illustrations and it's clear with his explanations.
if we are here watching his lectures, there's no way we can get into mit:(
Inserting a new key in a 2-3 tree is done as follows. First of all, we always
insert a new key K in a leaf, except for the empty tree. The appropriate leaf is
found by performing a search for K. If the leaf in question is a 2-node, we insert
K there as either the first or the second key, depending on whether K is smaller or
larger than the node’s old key. If the leaf is a 3-node, we split the leaf in two: the
smallest of the three keys (two old ones and the new key) is put in the first leaf,
the largest key is put in the second leaf, and the middle key is promoted to the
old leaf’s parent. (If the leaf happens to be the tree’s root, a new root is created
to accept the middle key.)
author always rocks...
What a clear xplanation @ this age!!. It gave me goosebumps to have knowledge like this rather than for passing just exams.
Great lecture - the passion shines through and the motivation rubs off!
2-3 Tree: Atmost 2 keys, at most 3 children
That's some seriously young professor.
I don't believe he is a professor; a graduate student, teaching for some credit (Teaching Assistant), perhaps. That's because he is terrible at teaching.
He was in his 3rd while teaching.
+1
I don't see how "he is terrible at teaching" makes him a not professor ;)
its a recitation. they are always conducted by TA.
In the Cormen textbook, section 18.1, it is written that if a node has 2*B-1 keys then it is called "full node" and once the # keys become 2*B then split occurs. But in this lecture, split occurs at 2*B-1 itself as here max # keys should be strictly less than 2*B-1. So practically which one to prefer is the confusion here 🤔
He is a grad student of MIT (2017 passout) , currently working at Twitter
who cares he is a terrible teacher....
@@asadullahfarooqi254 you are a terrible student. Its perfectly understandable.
@@asadullahfarooqi254 Why so much hate? Are you pakistani?
Sorry guys @Int 0x80 @Pratham Yadav, I shouldn’t have said that 😔 I take back my words. my sincere apologies. One more thing @Pratham Yadav That was wrong but not political.
@@7xr1e20ln8 isnt his definition wrong though? in CLRS 3rd edition page 489 the definition for internal nodes of degree t is: t
The literature on B-trees is not uniform in its terminology
Bayer and McCreight (1972) define the order of B-tree
as the 'minimum number of keys' in a non-root node.
terminology is ambiguous because the maximum number of keys is not clear
: An order 3 B-tree might hold a maximum of 6 keys or a maximum of 7 keys
(4 minimum children holds a maximum of 7 or 8 children)
Knuth (1998) avoids the problem by defining the order to be the 'maximum number of children'
order 3 B-tree : 2-3 tree
order 4 B-tree : 2-3-4 tree (2-4 tree)
"Cache line size" is the phrase you're looking for
Ah yes. I think that's the phrase. Another question though, so do we tune the size of each node (which consists of M # of children) to fit (a) RAM line size or (b) Disk block size?
It depends on the location where the B-tree stay. If a B-tree lives in a memory, then cache line size is appropriate. If a B-tree lives in a storage, then disk block size is appropriate.
What a passionate teacher !
I really enjoyed this. Instructor is great at explaining everything. Thank you!
It was best solution on b tree i had ever seen on UA-cam. Thanks
The way this guy explains things is unreal
it is a good lecture for clearing the concept of B tree.
But I have a doubt that value of maximum keys in a node is less than 2*B-1 or less or equal to 2*B-1 @MIT OpenCourseWare.
There is something wrong while explaining Number of Keys. The correction will be :
B-1
Yes. There are two mistakes.
B
actually the teacher and you are right, there are two concepts, for Bayer e McCreight(the creators), b ai the minimal number of keys, and Knuth use the minimal number of childrens.
@@patrickdornellesdasilvavie937 i dont think so. From what i've read both bayer and CLRS use b as the minimal number of children and knuth uses b as the maximum number of children
@@h8pathak yes, in CLRS 3rd edition page 489 the definition for internal nodes of degree t is: t
he is really good at juggling chalks
When I know something that I have to teach to a junior but am not completely prepared for it, that's how I teach. Good recitation though
Yeah I mean the subject is probably,like you know, the most boring part that you just kinda have to get through. I dont blame him. I don't even think my professor knows how to code tbh 😂
10:18 a wild runner appears
Such a passionate guy. Respect!
Man, once I hit play, I couldn't stop till the end, except for just this comment! ❤✌🇮🇳🇮🇳🇮🇳
the professor is adept at dancing, it seems
Structure Preserve invariance (Rep Invariant)
Common Issue:
One of your nodes will (become) overFull, & Overflow
24:04
wow, good vid.....this guy has got a bronze medal in IOI twice.
wow
But bronze is not gold.
I like this handsome Indian TA. No Indian accent at all.
North Indian accent is just like this
....
You bastards have stereotyped Indian accent with South Indian accent
Amazing explanation. Thank you.
Thank you so much! This helped me a lot! Keep going with such wonderful videos!
I am in love with this teacher
Do You Code B-tree by yourself?Understanding this and implementing it makes a huge difference
youre cute lol pretty eyes
Just MIT stuffs 😊😊
weird that an MIT prof has never implemented B tree but my college need me to do it without plagurism
Incredible India 🔥
Buddy I Also strucked on Implementation.. It's implementation is really very tough on coding point of view 🥴
@@achyutambharatam2116 yes, took me hours. And is kinda stupid coz libraries exist for all this stuff already
@@rohandalvi6476 Really? Libraries are there! But this is complex type of Dta structure... Sometimes I strucked for week for making their code understand.. Do u also face this?
@@achyutambharatam2116 ofc i do, it was last to last semester
Thanks for this video, this helps a lot during the pandemic!
make an ASMR video just with chalk sounds
Insertion explained at 13:50
oh this guy is so energetic. I like that!
I think the reason to use these trees is balancing!
Near the beginning, he asks "Why use B-trees over Binary Search Trees". He then explains something about avoiding reading memory from disk. This is not the reason I was taught in my class. The reason I was taught, is that these trees will stay balanced. With a Binary Search Tree, the algorithm of insert could result in the tree being extremely deep on one branch and very shallow on others. This means you will not actually get log(n) performance, since most of the data is in longer branches.
I believe that b-trees are to be used when accessing a disk location takes a larger amount of time and thus it is more efficient to have more keys stored in each location.
Why can't it be both? Both better caching and a balanced tree. Most data structures have not one, but several pros and cons over other data structures.
You're wrong. AVL trees also stay balanced and are way easier to implement, but they only hold 1 key for a given node and each node has only up to 2 children. The reason for using B trees is the one presented in the video
@@pharoah327 because there are avl trees and red-black trees which are also balanced and way easier to implement but wouldnt work for disk access
I have to watch 2 time to understand it. Thanks sir
Deletion very beautifully explained
Amazing lesson, you have my gratitude.
He has Nobody's gratitude...
Every time I check subtitles for sth I don't understand subtitles help me a lot with this answer: "inaudible"
+1
2:35 to 5:32 will change your life :D
XD yeah man
I can bet, this faculty is from India.
KULDEEP SINGH great discovery, you want a cookie?
No thanks
Kharagpur to be precise.
Thank you, this was helpful to me when i was implementing a b-tree in C ;
the way this guys flips his chalk after every sentence pisses me off
Great Lecture thanks.
Great lecture, thanks!
Smart explanation
Thank you for good lecture about deletion op.
1:32 Is no one in the class paying attention? It isn't at all clear why the depth is logN.
8:04 Finally mentioned that all the leaves are at the same depth, and only then do you know that the depth is actually logN and the tree is balanced.
probably everybody knew? its MIT
They supposedly studied Binary Search Trees last time. It should be obvious then. And if it isn't clear to you then you are studying in wrong order. Study BST first.
Great explanation.
half an hour worth more than Whole semester in my collage
he is too impatient and he has to correct himself way too often. I am so glad I never had such lecturers.
why is he speaking at 1.25 speed lol. I had to check my settings for a second
He is from our school in india
Amazing lecture!
This guy's pretty good (thumbs up)
This is an excellent education video, thanks a lot. I would like to clarify is B-Tree B is really stands for Branching? Thanks
I believe it stands for balanced
thanks you sir
Thanks a lot mate!
I think ravindrababu ravula has taught it better than this MIT teacher
he is just dancing can anyone tell me what beat is that .?? because google just failed to find such a beat..
dud dud dud dud. du du dud dud dud.. dudu dud dud dudd dududd dud dud...
He reminds me Tedd Mozbi from How i met your mom? NO??
Lol
Have a question... The nodes are not supposed to have more than b-1 keys.. But in his example (26:16 m) he got 5 keys in one leaf... how is that right?
And b = 4
I believe that you've mistaken the maximum bound of keys in a node to not be more than b-1 when the correct one is suppose to be less than 2b-1
guys while your watching the vid write awesome!🤣
Sir what is the best programming language for design and analysis of data structures and algorithms??.. please reply me sir 🙏🙏
c++
c
c++/java
ADHD very chaotic - hard to follow - jumping all over the place and at the end the result is quite confusing.
That's a very nice coat.
I could not follow quite well when he said why use B Trees over BSTs. Can someone please help me understand it?.
Memory access time cost is much expensive than CPU compare(
If single node's memory size is bigger than cache line, then single node visiting makes caching at most twice. Therefore it seems good to make node's memory size to fit into cache line size.
too smart.. didn't understand shit.
NOOO YOU ARE TOO DUMB
Or simply the guy is bad at teaching.
tits
excuse me sir , your deletion of 41 is wrong , why should you bring 30 down ?
in order to have same height for every leaf
no , actually it is beacuse of 30 's both children has only one number so, merging and then 41 also has one children in both side so merging again.height does n't matter yr
so cute awww
Why he is in hurry
Perhaps to rush for his next fix?
Where can I access the notes he said he would provide?
ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/recitation-notes/MIT6_046JS15_Recitation2.pdf
ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/recitation-notes/MIT6_046JS15_Recitation2.pdf
What is the meaning of the R in the playlist? Is R1 available?
The R means Recitation. It is a session that allows students to ask questions from materials presented in the lectures and to get help if they are stuck on a specific problem or concept. R1 was not recorded.
He is Shahrukh Khan
can someone explain why in the last bit we chose to rotate 17 on the left over 30 on the right? thxxxxx in advance!
I believe that it's an arbitrary decision and both are viable operations. Like in deletion, we can choose to propagate the left-most element of the right child OR the right-most element of the left child. Take what I say with a grain of salt, I'm also trying to learn B-Trees lol
how is the order of B tree related to the branching factor? Also how do you find the branching factor?
B is defined as the branching factor. By definition, this establishes a bound on the number of children: [B,2B) and hence a bound on the number of keys: [B-1, 2B-1]. You can what B is by taking the floor of lg(# of children in any branch)....(correct me if im wrong here...)
2B-1 = order of the tree (which means the maximum number of branches a node can have )
and B= minimum number of Branches a node can have.
and you don't need to find the branching factor, whatever you wish you can take depending on your max height constraints
Cool guy
Although I am grateful for these OCW videos, I have to say that the TA was very disorientating with his botched accent and nervous energy. It distracted me from whatever he was trying to teach. Was there some cute girl in the audience he fancied or what?
Complexity of delete operation?
logn
this is insane
Any one please explain how its no of children B
so how can it adjust 19 children in it there
i think he's wrong, in CLRS 3rd edition page 489 the definition is: t
Awesome! Greetings from Mexico.
13:30 I know this fake laughs its widely used in my univirsty
in the end, what if you delete 3?
Good qus!
After deleting 3, we marge 2 and 7 make it a single node but this node has empty parent then 10 will come down and take it's parent node now 10 will only left node( containing two key 2 and 7) and it's right node is empty. There is one more problem the root node is also empty. Now we are combine 14 and 17 and make the left node/child of 30 and 16 goes up and take's the root place but still 10 doesn't have the right child now 10 will ask to it's sibling 30 help me but 30 say i am bierley full but sibling left child say hay i am eligible to help him, now sibling (30) of left child of right element goes up and combine with 30(now the parent node contain two key 17 and 30) now there will be rotation as well as shifting now 17 goes up now the root node has two key (16 and 17) and 16 come down to 17's left child 10 and there will be two key (i.e 10 and 16) and finally 16 will come down and became the right child of 10.now everything is kk..
He is pretty spazy and needs to slow it down a bit. So far the better videos on BTree's for sure, just needs to clean up his lecture and be a bit more prepared.
Hi MIT! this lecture doesn't seem to be well connected. Can we have another one?
No
Why log n? shouldn't it be log n base 3
Base doesn't matter. By change of base formula of log function. i.e., log_3(x) = Constant * log_10(x). You can pick any base for asymptotic analysis.
When watching this lecture, I can't help but think that this dude is scamming me right now :q
MARANATHA KYMRY
maybe he is impersonating SRK
tweakin
He wants to dance
cool
Very poor presentation missing tones of critical and essential points. Even the "node" and "keys in a node" distinction is not made that clear (and he gets a question because of this basic confusion). I suggest someone who wants to get basics of the subject should definitely NOT start with this lecture. It seems that someone who did not implement a B-tree should not give lectures on it.
4:30
Searching In BST is O(n) worst case not log(n)
He said B-trees needed to be balanced