5.19 Splay Tree Introduction | Data structure & Algorithm
HTML-код
- Опубликовано: 27 дек 2024
- Correction: at14:21 9 will be left child of 10
Jennys Lectures DSA with Java Course Enrollment link: www.jennyslect...
DSA Complete Course: https: • Data Structures and Al...
In this lecture I have discussed basics of Splay tree, rotations used in splay tree, advantages and drawbacks of splay tree, applications of splay tree.
See Complete Playlists:
C Programming Course: • Programming in C
C++ Programming: • C++ Complete Course
Python Full Course: • Python - Basic to Advance
Printing Pattern in C: • Printing Pattern Progr...
DAA Course: • Design and Analysis of...
Placement Series: • Placements Series
Dynamic Programming: • Dynamic Programming
Operating Systems: // • Operating Systems
DBMS: • DBMS (Database Managem...
Connect & Contact Me:
My Hindi Channel: / @jennyslectureshindi
Facebook: / jennys-lectures-csit-n...
Quora: www.quora.com/...
Instagram: / jayantikhatrilamba
Correction: at14:21 9 will be left child of 10
Do explain skip list madam
Splay tree is the topic which you will hardly find on youtube. Thank you mam for explaining this topic so perfectly on demand.
Correction - 14:20 that 9 shd be to the left of 10 and not to left of 7
yes right
yes, i think it must be like you said
trueee
yes you are right. I agree
yesbro
someone already mentioned it but im gonna right it anyway for anyone didnt see that comment , 14:20 9 is gonna be the left child of 10... and Jenny thanks.. getting use to the accent btw.
💯💯
right
Node(14) will take 3 rotation. At first,it will take left rotation (zag) and will be placed where node 13 is then it will take right rotation (zig) to take place of node 15 and then at last it will take left rotation (zag) to take place of node 10 and therefore by this way it will become root node.
so it become zag-zig-zag rotation ..it is true?????????
what if I suppose the left rotation as ' zig ' ?
I get to confused with your zig and zag pronunciation but concept wise its really good !
Yeah bro!totally confused😆
@@saicharan6514 haryanvi accent :)
puchi kisi ne - yashraj mukhaute
28:20 -Zag-zig rotation and then Zag rotation
3 rotations applied
Really appreciate these lectures here, helping me in the last moment rush to study things when the notes don't explain anything conviniently
First zag then zig zag mam to search the value of 14 . Mam do correct me if am wrong .
This is the answer for question asked @ 28:18
Really mam its helping a lot till now ....its like literally 4years since this playlists has been uploaded , we dont have any fikar about ds ka subject. Thats the power of a quality teacher ! Take a bow!! Thank you mam !
yup correct ;) ;) ;) ;)
awesome explanation ... thanx a lot, your all videos are helping me prepare for my upcoming exams... god bless you
In case of zig-zig or zag-zag rotation we are first rotating grandparent and then parent but in case of zig-zag or zag-zig you are rotating first parent and then grandparent. A little bit confusing
yes that's rule about rotation.. u need to take care of this thing while splaying
@@JennyslecturesCSIT okay mam got it✌️☺️
I am lazy, I just like videos to support who made them. But this video is THE VIDEO on RB trees. I saw it fully with adv and repeatedly. I pray you should feel satisfied and fulfilled in all your life.
I love your teaching mam🥰 i think am fall in love in your teaching❤
to search 14 we need 3 rotation zag - zig - zag in splaying.
No need
for last question ‐---》
*s1 : * zig rotation of 15 so 13 is new parent and 14 attaches to 15 on left side
*s2 : * zag rotation of 10 so 13 is new root and 11 attaches to 10 on right side
*s3 : * zig rotation of 15 so 14 is new parent
*s4 : * zag rotation of 13 so 14 is new root
right?
hello mam , your way of explanation is very cooll,,and one of my friend named avi goyal is also your great fan
2 ROTATIONS
1>ZAG-ZIG((zag part)14 will come to the 13 place and 13 will go left to the 14 after that (zig part)14 will go to the 15 place and 15 will go right of 14)
2>ZAG (14 will go to the root place and root 10 will shift left of 14)
for last question ‐---》
*s1 : * zig rotation of 15 so 13 is new parent and 14 attaches to 15 on left side
*s2 : * zag rotation of 10 so 13 is new root and 11 attaches to 10 on right side
*s3 : * zig rotation of 15 so 14 is new parent
*s4 : * zag rotation of 13 so 14 is new root
right?
can I consider the left rotation as " zig " and right rotation as " zag " ?
sure but your teacher may not consider that, so when they puts a 0 in your answer script, consider it to be a 10 @@atharvakunde8616
I have never seen such kind of teacher, teaching as perfect as you are!!! We Are really Very Glad😊 To Have youu Mam🤌❤️ Such an extraordinary concepts you have built yourself, really great mam hats off to you 🙌🫶✨
ma'm i really appriciate your study videos. they are very useful for my studies. thanks alot from sri lanka😘😘
i didn't find code implementation of trees in cpp, i love your videos way of teaching kindly pls make videos of implementation
Hi ma'am, I have a doubt, at 14:20, the tree on the left states that 7 becomes the root for 9 and 10, but then why is 9 on the left of 7, shouldn't it be on the right side of 7? Or we can have 9 instead of 7, 7 on the left and 10 on the right?
Very nice delevering technique to student . Watching from surkhet nepal.
mam 2 rotations will be needed for 14 that is zag-zig then just zag
at the very first instance ,your beauty n now your hard work is compelling me to fall for you..😊😊
Don't fall brother, She is teacher & teacher always rise students knowledge.
Maam DBMS series will be uploaded and completed before 24?!?!
Was about to start tuesday nA
15:01 result of zig zig rotation is not following BST property, 9 is greater than 7 so it should be in a right of 7.
for last question ‐---》
*s1 : * zig rotation of 15 so 13 is new parent and 14 attaches to 15 on left side
*s2 : * zag rotation of 10 so 13 is new root and 11 attaches to 10 on right side
*s3 : * zig rotation of 15 so 14 is new parent
*s4 : * zag rotation of 13 so 14 is new root
right?
god-tier explanation!
Sooooo helpful, you saved me today, ma'am🥰
in The zig-zig rotation on the final tree, as we know after splaying the tree must be BST(i.e left child of anode is less than the root node and right child is greater than the root), but when we look the result of the tree after splaying(1) it is not BST( i.e when we look node 7 its left child is greater than (9>7)) why?????
From a main tree if i want to search -1 what is the procedure to be followed? which type of rotation it would be!?
Hi Jenny, Cud u review this and clarify/confirm/correct?
Suppose a and b to the left and right extreme of splay tree are the most frequently accessed. search(a) zigs, makes a root, and pushes b down by almost double height. And search(b) next zags, make b root, and pushes a double the height down (when compared with the original tree height). So, every time these 2 searches happen consecutively, multiple rotations and too much skewing of the tree would occur, and search would be O(logN) and never O(1)
How about use Treap instead of Splay Tree to achieve the same?
The splay tree keys become Treap keys. Keys satisfy BST rule. Number of searches for a key becomes the node's priority. Priorities satisfy max-heap rule. Hence all those keys that are most frequently searched would always be very close to the Treap root, and skewing would also be relatively lesser.
And, above case of search(a) and search(b) happening consecutively, and many times, would ensure that a and b stay very close to Treap's root (if not become the root) due to tremendous increase in their priorities. The extreme zig or zag as with Splay Tree wouldn't happen here.
Is there any mistake in my understanding? Please comment on this. Thankyou! :)
Just Amazing as usual
Merci tu as sauvé mon examen d'algo !
This video will be most useful for me before exam .. thanks a lot
Your lecture on splay trees are very superb...👏👏👏
mam don't you think that you should also provide the code for better understanding?
16:48 -> right-side if you want to search 30; we will perform 4 zig rotations i.e. zig zig zig zig rotation....
@@prabhassla4237
No brother we will do 3 Zig Zig rotations
No...bro we will do 3 Zig Zig rotations
At 14:32 the Child of 10 should be 9 and 15 but you write child of 7 as 9 and 10 ,as we can see 7 is smaller than 9 so 9 cannot be in its left side i think so please let me know this ?
mam what about the case in which grandparent of the node (to be searched) is not the root? like searching 14 in the last example , if we perform any rotation in case3 like (zig-zig ,zag-zag, zig-zag, zag-zig) then 14 would not be at the root , it would 1 level below the root? is that correct?
mam...i saw the same tree you told told that parent of the searched node has to roatated untill the root is obtained....in java point website they tod to rotate the grand parent of the node untill the searched nodde is root...which is right mam??can u repost a new version of this vedio reclarifying it??
Time (15:09) After performing the second zig rotation the 9 will at the left of 10 not the left of 7.
Hushar ahes ki
@@harshvardhanmhetre9223 exam aahe ka udya 😂😂
@@shubhamchaudhari9475 ha😂😂
in zig zig how can 9 be the left child of 7
splay trees also follows the bst right?
Ma'am pplzz add videos for B-tree.
It's really an important topic for our university exam.
And I my only source of learning is u.
Already uploaded dear. Check out the playlist "b tree and b+ tree"
Mmm expected video from my side ...thanks 😍
Hello, in minute 16:00 the 13 in the ZAG seems wrongly placed in comparison to the 9 in the ZIG or viceversa.
Thank you very much. You are a genius.
Upload on AA tree,KD tree also if possible😄bcoz I know no one will explain it like u :)
Excellent Explanations Jenny...
God bless you !!!!!!!
What is the point of splaying when we have already found the node?
14:34 9 is left child of 7 ?🧐🤯
how, can't understand?
Is it mistakenly written or like that only?
I am asking with no intent to disrespect you at all. thank you
it was by mistake...9 will be left child of 10... btw thanks for highlighting this correction
@@JennyslecturesCSIT thanks for replying janita ma'am
@@JennyslecturesCSIT I also noted that.. Thanks for making my day on trees
wow! You gave a very clear explanation madam
lastly mam wrote one more feature , but unable to see, could anyone tell.
Watching at 11:15 am when the exam is at 1:45 pm
Thank you very much for helping me understand this topic!!
Answer is Zig-zag-zig rotation
Thank you memdm ji
Ur energy is fierce
for searching 14 can we do first zag zig rotation and then zag rotation ?
Mam aapke padane ka style wahhh I like you mam
There after zig zig rotation 9 is placed left to the 7 but it was greater than 7 ,9 shoud be placed right to the 7
Thanks for this wonderful lecture , keep it up Jenny 👍👍 you are doing a wonderful job for all the learner’s out their .
in order to insert 14 we will do three rotation
Mam.. shortening the video a bit will make your videos a good reach. Best teaching 💯💯💯🔥🔥
if a node have more than two parent than how many rotation need to do , mam ji ? do we need to make a node as a root node always if I am searching that particular node ?????
yes make it as root node always.
a big thanks for your work
why you don't write the code of AVL and RedBlack ?
keep it up jenny...your very intelligent and cute also😍💟❣
Thanks for taking my request
legendary teaching!
It's very clear to understand Tsm sister
thanks for very clear explanation!
Is it log base 2 n?
Awesome explanation thank you....
Mam Will you please check the BST after the zig-zag rotations I think it doesn't follow.....if I'm wrong then ignore me🙂🙂
ha bhai me bhi whi bolra
Mam can you tell about skip list and xor lists
15:45 at this time in the video .. after zig-zig ang zag-zag rotations....the tree in not following binary search tree I guess. .......coz the nodes are coz the parent node must be less than right child and more than left child ........after rotations
Very nice explanation! But I have doubt. After every operation it splays which usually leads to loss of its balancing property, but still we says that its a self-balancing tree. WHY??
I guess it's not about balance factor of AVL but a balance of BST. Balance of BST remains.
Thanks maam today I was looking for that topic in your playlist please complete it ASAP
thank You So much . Understood Prefectly .♥
awsome lecture...keep going
Ma'am I kindly request ,
Please teach us about trie data structure with code implementation.
Ma'am can you please upload video on Kd Tree .....
actually mam at 14:56 the final splay tree you made is wrong i think because it has 9 on left of 7 not 10
yes 9 should be in the left of 10
It was a minor mistake. Already said mate. Chill
Thanks mam, easy to understand :)
Please make a video on segment tree
the most frequent one or the recent ones??
i guess it should be recent ones
Searching 14 requires a combination of three operations mam: Zag - Zig - Zag! Guess am correct! If not please let me know. Thanks for being this super excellent and precise. May Allah bless you
Correct
Mam please make a video on hamilton cycle using backtracking
Binary threaded tree.. Mam??
super mam😘🥰😍
I better than understand maim and thanks so much
I deeply understand the process but i saw 7 is root and 9 is also greater than 7 but less than 10 ...i think 9 will child of 10 not 7...coz in BST left child should be less than and right child should be greater than root node.....
Madam sply tree Ana split tree Ana same ha
amazing explanation, thank you mam :)
Mam, all your lectures are very good. In this lecture you have stated multiple times zig and zag are sometimes said in opposite way, can you please provide some reference to which books or reference you are referring to?
Very systematic and clear explanation, many thanks!
The node 9 goes to left child of 7. I think it is not possible. Violating the rules of BST
you are too perfect teacher and also cute
Well explained Mam ☺️
One ZIG-ZAG rotation i.e. for nodes 15-13-14 (LR) and then one ZIG rotation i.e. for node 10 -14 (L) :*
I think the answer for search 14 is 3 rotations zag zig zag left right left
Ma'am Please pin me wheater I am correct or not.