title

5.19 Splay Tree Introduction | Data structure & Algorithm

description

Correction: at14:21 9 will be left child of 10
DSA Complete Course: https: https://www.youtube.com/playlist?list=PLdo5W4Nhv31bbKJzrsKfMpo_grxuLl8LU
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: https://www.youtube.com/playlist?list=PLdo5W4Nhv31a8UcMN9-35ghv8qyFWD9_S
C++ Programming: https://www.youtube.com/playlist?list=PLdo5W4Nhv31YU5Wx1dopka58teWP9aCee
Python Full Course: https://www.youtube.com/playlist?list=PLdo5W4Nhv31bZSiqiOL5ta39vSnBxpOPT
Printing Pattern in C: https://www.youtube.com/playlist?list=PLdo5W4Nhv31Yu1igxTE2x0aeShbKtVcCy
DAA Course: https://www.youtube.com/playlist?list=PLdo5W4Nhv31ZTn2P9vF02bkb3SC8uiUUn
Placement Series: https://www.youtube.com/playlist?list=PLdo5W4Nhv31YvlDpJhvOYbM9Ap8UypgEy
Dynamic Programming: https://www.youtube.com/playlist?list=PLdo5W4Nhv31aBrJE1WS4MR9LRfbmZrAQu
Operating Systems: //www.youtube.com/playlist?list=PLdo5W4Nhv31a5ucW_S1K3-x6ztBRD-PNa
DBMS: https://www.youtube.com/playlist?list=PLdo5W4Nhv31b33kF46f9aFjoJPOkdlsRc
Connect & Contact Me:
My Hindi Channel: https://www.youtube.com/@JennyslecturesHINDI
Facebook: https://www.facebook.com/Jennys-Lectures-CSIT-Netjrf-316814368950701/
Quora: https://www.quora.com/profile/Jayanti-Khatri-Lamba
Instagram: https://www.instagram.com/jayantikhatrilamba/

detail

{'title': '5.19 Splay Tree Introduction | Data structure & Algorithm', 'heatmap': [{'end': 350.289, 'start': 308.564, 'weight': 1}, {'end': 704.962, 'start': 678.271, 'weight': 0.916}, {'end': 1634.921, 'start': 1603.719, 'weight': 0.723}], 'summary': 'Delves into splay trees, their operations, binary tree rotations, zigzag rotations, and the advantages and drawbacks of splay trees, providing insights into their applications and potential to optimize time complexity, with examples and quantifiable data.', 'chapters': [{'end': 43.006, 'segs': [{'end': 43.006, 'src': 'embed', 'start': 0.071, 'weight': 0, 'content': [{'end': 2.439, 'text': 'you So the topic is splay trees.', 'start': 0.071, 'duration': 2.368}, {'end': 4.961, 'text': 'See, splay trees are basically.', 'start': 3.02, 'duration': 1.941}, {'end': 13.987, 'text': 'these are self-balancing, or you can say self-adjusted binary search trees, right, or you can say these are variants of binary search tree.', 'start': 4.961, 'duration': 9.026}, {'end': 19.27, 'text': 'So the prerequisite of this video is you should know what is binary search tree right.', 'start': 14.667, 'duration': 4.603}, {'end': 23.093, 'text': 'Now, in this video we will discuss what are splay trees,', 'start': 19.731, 'duration': 3.362}, {'end': 30.178, 'text': 'how splay trees are different from other balancing binary search trees like avial tree and red block trees.', 'start': 23.093, 'duration': 7.085}, {'end': 40.284, 'text': 'right and as well as we will see advantages and drawbacks of split trees and at last we will see some applications of split trees right.', 'start': 30.718, 'duration': 9.566}, {'end': 43.006, 'text': 'so now we will discuss what is split tree.', 'start': 40.284, 'duration': 2.722}], 'summary': 'Splay trees are self-balancing binary search trees with advantages and drawbacks compared to other balancing trees, and have various applications.', 'duration': 42.935, 'max_score': 0.071, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qMmqOHr75b8/pics/qMmqOHr75b871.jpg'}], 'start': 0.071, 'title': 'Splay trees', 'summary': 'Discusses splay trees, self-balancing binary search trees, their differences from other balancing binary search trees, advantages, drawbacks, and applications.', 'chapters': [{'end': 43.006, 'start': 0.071, 'title': 'Splay trees: self-balancing binary search trees', 'summary': 'Discusses splay trees, which are self-balancing binary search trees, their differences from other balancing binary search trees, advantages, drawbacks, and applications.', 'duration': 42.935, 'highlights': ['Splay trees are self-balancing binary search trees, a variant of binary search trees.', 'The video covers the differences between splay trees and other balancing binary search trees like avl and red-black trees.', 'The chapter highlights the advantages, drawbacks, and applications of splay trees.']}], 'duration': 42.935, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qMmqOHr75b8/pics/qMmqOHr75b871.jpg', 'highlights': ['The chapter highlights the advantages, drawbacks, and applications of splay trees.', 'The video covers the differences between splay trees and other balancing binary search trees like avl and red-black trees.', 'Splay trees are self-balancing binary search trees, a variant of binary search trees.']}, {'end': 497.79, 'segs': [{'end': 119.779, 'src': 'embed', 'start': 93.402, 'weight': 1, 'content': [{'end': 103.773, 'text': 'in avial tree and in red black trees it is order of log n means avial tree and red black tree guarantees that the time complexity would be order of log n.', 'start': 93.402, 'duration': 10.371}, {'end': 109.035, 'text': 'because these are balanced trees, self balancing trees.', 'start': 103.773, 'duration': 5.262}, {'end': 113.636, 'text': 'these trees cannot be right, skewed or left skewed, right.', 'start': 109.035, 'duration': 4.601}, {'end': 119.779, 'text': 'so i hope you have seen my videos on bst, on avial tree and red black trees, right.', 'start': 113.636, 'duration': 6.143}], 'summary': 'Avl and red-black trees ensure o(log n) time complexity due to their balanced, self-balancing nature.', 'duration': 26.377, 'max_score': 93.402, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qMmqOHr75b8/pics/qMmqOHr75b893402.jpg'}, {'end': 199.314, 'src': 'embed', 'start': 166.047, 'weight': 0, 'content': [{'end': 169.408, 'text': 'See, see, on these trees, splay trees also.', 'start': 166.047, 'duration': 3.361}, {'end': 174.09, 'text': 'the operations would be same as BSTT, like a search insertion and deletion.', 'start': 169.408, 'duration': 4.682}, {'end': 180.212, 'text': 'And the procedure would be same as we have conducted these operation in binary search tree right?', 'start': 174.27, 'duration': 5.942}, {'end': 182.052, 'text': 'Plus extra thing is what?', 'start': 180.812, 'duration': 1.24}, {'end': 190.955, 'text': 'Here all the basic operations would be same as binary search tree, with some extra operation, that is splaying.', 'start': 182.532, 'duration': 8.423}, {'end': 199.314, 'text': 'these, all the operations are followed by one operation.', 'start': 195.273, 'duration': 4.041}], 'summary': 'Splay trees have same operations as bst with extra splaying operation.', 'duration': 33.267, 'max_score': 166.047, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qMmqOHr75b8/pics/qMmqOHr75b8166047.jpg'}, {'end': 350.289, 'src': 'heatmap', 'start': 302.559, 'weight': 2, 'content': [{'end': 307.563, 'text': 'We are going to make this element, or that particular element as the root of the tree.', 'start': 302.559, 'duration': 5.004}, {'end': 312.287, 'text': 'right. so how you can define splay trees.', 'start': 308.564, 'duration': 3.723}, {'end': 326.979, 'text': 'these are self adjusted binary search tree in which each operation on element rearrange the tree so that that element would be placed at the root of the tree.', 'start': 312.287, 'duration': 14.692}, {'end': 331.212, 'text': 'right now, suppose we are going to perform search operation on 9.', 'start': 326.979, 'duration': 4.233}, {'end': 334.175, 'text': 'right, so 9 is less than 10.', 'start': 331.212, 'duration': 2.963}, {'end': 334.955, 'text': 'we are going to the left.', 'start': 334.175, 'duration': 0.78}, {'end': 336.036, 'text': '9 is greater than 7.', 'start': 334.955, 'duration': 1.081}, {'end': 337.057, 'text': 'we are going to the right.', 'start': 336.036, 'duration': 1.021}, {'end': 338.779, 'text': 'now. here we got 9.', 'start': 337.057, 'duration': 1.722}, {'end': 339.239, 'text': 'now we are.', 'start': 338.779, 'duration': 0.46}, {'end': 340.16, 'text': 'we are going to do splang.', 'start': 339.239, 'duration': 0.921}, {'end': 345.445, 'text': 'splang means we are going to make this element as the root of the tree.', 'start': 340.16, 'duration': 5.285}, {'end': 350.289, 'text': 'now, for making these elements, for suppose i am going to make 9 as the root of the tree.', 'start': 345.445, 'duration': 4.844}], 'summary': 'Splay trees rearrange for search operation, making 9 the root.', 'duration': 31.616, 'max_score': 302.559, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qMmqOHr75b8/pics/qMmqOHr75b8302559.jpg'}, {'end': 397.354, 'src': 'embed', 'start': 370.164, 'weight': 3, 'content': [{'end': 375.746, 'text': 'if you got what is splaying, how to do splaying of this tree, then it means you are done with splay trees.', 'start': 370.164, 'duration': 5.582}, {'end': 377.326, 'text': 'you got it right.', 'start': 375.746, 'duration': 1.58}, {'end': 386.729, 'text': 'so splaying means basically what rearranging the tree so that the element on which you are going to perform the operation now become the root of the tree.', 'start': 377.326, 'duration': 9.403}, {'end': 389.17, 'text': 'right, how to do the rearrangement of the tree, that thing.', 'start': 386.729, 'duration': 2.441}, {'end': 397.354, 'text': 'we will discuss the rotations, how many rotations and which type of rotations you need to perform here right now.', 'start': 389.17, 'duration': 8.184}], 'summary': 'Splaying rearranges tree to make element the root. discussing rotations.', 'duration': 27.19, 'max_score': 370.164, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qMmqOHr75b8/pics/qMmqOHr75b8370164.jpg'}], 'start': 43.006, 'title': 'Splay trees and their operations', 'summary': 'Discusses the time complexity of binary search trees, avl trees, and red-black trees. it also introduces the concept of splay trees and their potential for improving time complexity in practical situations. furthermore, it delves into the splaying operation in splay trees to rearrange the tree for efficient search operations, providing examples and associated splaying steps.', 'chapters': [{'end': 221.319, 'start': 43.006, 'title': 'Splay trees: self-balancing binary search trees', 'summary': 'Discusses the time complexity of binary search trees, avl trees, and red-black trees. it also introduces the concept of splay trees and their potential for improving time complexity in practical situations.', 'duration': 178.313, 'highlights': ['Splay trees guarantee improved time complexity Splay trees ensure a time complexity of O(log n) for search, insertion, and deletion operations, potentially offering better performance in practical scenarios.', 'Comparison of time complexity with other tree types AVL trees and red-black trees also maintain a time complexity of O(log n), ensuring balanced trees and efficient operation performance.', 'Explanation of splaying in splay trees Splaying in splay trees involves a self-adjusting process that follows basic binary search tree operations, enhancing performance with additional splaying operations.']}, {'end': 497.79, 'start': 221.319, 'title': 'Splay trees and splaying operation', 'summary': 'Discusses splay trees, focusing on the splaying operation to rearrange the tree so that the element being searched becomes the root, with examples of search operations and associated splaying steps.', 'duration': 276.471, 'highlights': ['The splaying operation in splay trees involves rearranging the tree so that the element being searched becomes the root, achieved through zig rotations and right rotations.', 'Splay trees are self-adjusted binary search trees where each operation rearranges the tree so that the operated element is placed at the root, with splaying being a crucial aspect of splay trees.', 'The search operation in splay trees is followed by splaying, which involves making the searched element the root of the tree through rotation and rearrangement steps.']}], 'duration': 454.784, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qMmqOHr75b8/pics/qMmqOHr75b843006.jpg', 'highlights': ['Splay trees guarantee improved time complexity with O(log n) for search, insertion, and deletion operations.', 'AVL trees and red-black trees maintain a time complexity of O(log n), ensuring balanced trees and efficient operation performance.', 'Splaying in splay trees involves a self-adjusting process that follows basic binary search tree operations, enhancing performance with additional splaying operations.', 'The splaying operation in splay trees involves rearranging the tree so that the element being searched becomes the root, achieved through zig rotations and right rotations.', 'Splay trees are self-adjusted binary search trees where each operation rearranges the tree so that the operated element is placed at the root, with splaying being a crucial aspect of splay trees.', 'The search operation in splay trees is followed by splaying, which involves making the searched element the root of the tree through rotation and rearrangement steps.']}, {'end': 1015.464, 'segs': [{'end': 638.25, 'src': 'embed', 'start': 611.775, 'weight': 0, 'content': [{'end': 618.818, 'text': 'somewhere it is written that the right rotation is known as zig rotation and the left is known as zeg rotation.', 'start': 611.775, 'duration': 7.043}, {'end': 629.243, 'text': 'fine, but somewhere it is written that this case, if the child, if the node you want to search, is child of the root node, it can be left.', 'start': 618.818, 'duration': 10.425}, {'end': 631.324, 'text': 'it can be right in both cases.', 'start': 629.243, 'duration': 2.081}, {'end': 634.967, 'text': 'it is what zig rotation in this case.', 'start': 631.324, 'duration': 3.643}, {'end': 638.25, 'text': 'in this case, if it is the left child, then zig right rotation.', 'start': 634.967, 'duration': 3.283}], 'summary': 'Zig rotation is used for left and right child nodes in tree traversal.', 'duration': 26.475, 'max_score': 611.775, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qMmqOHr75b8/pics/qMmqOHr75b8611775.jpg'}, {'end': 738.3, 'src': 'heatmap', 'start': 678.271, 'weight': 1, 'content': [{'end': 688.177, 'text': "now the situation is if the node you want to search is having parent as well as grandparent, Suppose I'm going to search one.", 'start': 678.271, 'duration': 9.906}, {'end': 691.438, 'text': 'One is having parent as well as grandparent.', 'start': 688.777, 'duration': 2.661}, {'end': 695.36, 'text': 'Now in that case, we have four cases, four rotations.', 'start': 692.239, 'duration': 3.121}, {'end': 696.921, 'text': 'Let us see those rotations.', 'start': 695.66, 'duration': 1.261}, {'end': 701.483, 'text': 'Now let us take this example and here I want to search one.', 'start': 697.561, 'duration': 3.922}, {'end': 704.962, 'text': 'now the same step.', 'start': 704.062, 'duration': 0.9}, {'end': 707.683, 'text': 'first of all, perform the standard BST searching.', 'start': 704.962, 'duration': 2.721}, {'end': 709.303, 'text': 'compare with this 10.', 'start': 707.683, 'duration': 1.62}, {'end': 710.244, 'text': 'one is less than 10.', 'start': 709.303, 'duration': 0.941}, {'end': 714.445, 'text': 'so we are going to go to the left of this less than 7.', 'start': 710.244, 'duration': 4.201}, {'end': 717.766, 'text': 'now to the left of 7, and here we got 1.', 'start': 714.445, 'duration': 3.321}, {'end': 719.846, 'text': 'now we do what splaying now.', 'start': 717.766, 'duration': 2.08}, {'end': 722.367, 'text': 'splaying means this one should be the root of the tree.', 'start': 719.846, 'duration': 2.521}, {'end': 724.267, 'text': 'you have to make this one as the root of the tree now.', 'start': 722.367, 'duration': 1.9}, {'end': 726.368, 'text': 'you have to rearrange the tree now.', 'start': 724.267, 'duration': 2.101}, {'end': 732.87, 'text': 'here the situation is now this one, this element on which you are going to perform the operation, that is searching operation,', 'start': 726.368, 'duration': 6.502}, {'end': 738.3, 'text': 'is parent as well as grandparent.', 'start': 732.87, 'duration': 5.43}], 'summary': 'Explains splaying with searching and tree rearrangement, involving four rotations.', 'duration': 49.523, 'max_score': 678.271, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qMmqOHr75b8/pics/qMmqOHr75b8678271.jpg'}, {'end': 970.452, 'src': 'embed', 'start': 944.809, 'weight': 3, 'content': [{'end': 949.952, 'text': 'so now the tree would be something like this so now this zigzag rotation is having two cases.', 'start': 944.809, 'duration': 5.143}, {'end': 957.275, 'text': 'one is this one, this one, and second, is this one right this you can say that it is zigzag right rotation.', 'start': 949.952, 'duration': 7.323}, {'end': 970.452, 'text': 'it is what zigzag left left rotations and somewhere it is written that it is what zeg rotation, first zeg rotation and again zeg rotation.', 'start': 957.275, 'duration': 13.177}], 'summary': 'The zigzag rotation has two cases, involving left and right rotations.', 'duration': 25.643, 'max_score': 944.809, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qMmqOHr75b8/pics/qMmqOHr75b8944809.jpg'}], 'start': 497.79, 'title': 'Binary tree rotations', 'summary': 'Covers the processes of searching and performing rotations in binary trees, addressing cases like the search item being a child of the root node and the splaying process, and also explains the concept of zig-zag rotations in binary search trees with illustrative examples and quantifiable data.', 'chapters': [{'end': 738.3, 'start': 497.79, 'title': 'Search and rotation in binary trees', 'summary': 'Discusses the process of searching and performing rotations in binary trees, explaining the cases where the search item is a child of the root node and the subsequent zig rotations, as well as the splaying process when the search item is both a parent and a grandparent.', 'duration': 240.51, 'highlights': ['The chapter explains the scenarios where the search item is a child of the root node, detailing the cases of left and right child and the corresponding zig rotations to reorganize the tree, such as left rotation for left child and right rotation for right child.', 'It discusses the splaying process when the search item is both a parent and a grandparent, emphasizing the need for rearranging the tree and making the search item the root of the tree to perform the searching operation effectively.', 'It provides examples and steps for performing standard BST searching and splaying when the search item has a parent as well as a grandparent, highlighting the importance of rearranging the tree to make the search item the root of the tree for efficient operations.']}, {'end': 1015.464, 'start': 738.3, 'title': 'Zig-zag rotations in binary search trees', 'summary': 'Explains the concept of zig-zag rotations in binary search trees, illustrating how to identify the need for zig-zag rotations and perform them, using examples with quantifiable data.', 'duration': 277.164, 'highlights': ['The chapter discusses the scenario of zig-zag rotations in binary search trees, emphasizing the need for two rotations to perform zig-zag rotations.', 'It explains the process of identifying the need for zig-zag rotations based on the relative positions of the nodes, providing examples with quantifiable data.', 'The concept of zig-zag rotations is further illustrated with specific examples of performing zig-zag rotations in binary search trees, highlighting the steps and outcomes with quantifiable data.']}], 'duration': 517.674, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qMmqOHr75b8/pics/qMmqOHr75b8497790.jpg', 'highlights': ['The chapter explains the scenarios of left and right child of the root node, detailing corresponding zig rotations.', 'It discusses the splaying process when the search item is both a parent and a grandparent.', 'It provides examples and steps for performing standard BST searching and splaying.', 'The chapter discusses the scenario of zig-zag rotations in binary search trees.', 'It explains the process of identifying the need for zig-zag rotations based on the relative positions of the nodes.', 'The concept of zig-zag rotations is further illustrated with specific examples.']}, {'end': 1374.011, 'segs': [{'end': 1095.606, 'src': 'embed', 'start': 1067.147, 'weight': 0, 'content': [{'end': 1070.13, 'text': 'first of all, this 13 is to the left of this 15.', 'start': 1067.147, 'duration': 2.983}, {'end': 1072.913, 'text': 'so we will do right rotation.', 'start': 1070.13, 'duration': 2.783}, {'end': 1083.075, 'text': 'right when you do right rotation on 15 on this edge which is connecting 13, and this 15 means the node you want to search and its parent.', 'start': 1072.913, 'duration': 10.162}, {'end': 1086.658, 'text': 'first of all, you will do rotation on that edge.', 'start': 1083.075, 'duration': 3.583}, {'end': 1091.883, 'text': 'you are not going to do rotation on this 10 now, right in zigzag situation.', 'start': 1086.658, 'duration': 5.225}, {'end': 1095.606, 'text': 'first of all, we will rotate this on this edge.', 'start': 1091.883, 'duration': 3.723}], 'summary': 'Perform right rotation on node 15 connected to 13.', 'duration': 28.459, 'max_score': 1067.147, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qMmqOHr75b8/pics/qMmqOHr75b81067147.jpg'}, {'end': 1208.424, 'src': 'embed', 'start': 1154.965, 'weight': 1, 'content': [{'end': 1157.407, 'text': 'now this is the tree after one zig operation.', 'start': 1154.965, 'duration': 2.442}, {'end': 1159.369, 'text': 'now still we are left now.', 'start': 1157.407, 'duration': 1.962}, {'end': 1163.492, 'text': 'still the 13 is not the root right now.', 'start': 1159.369, 'duration': 4.123}, {'end': 1166.674, 'text': 'now we will do what the 13 is to the right of its parent.', 'start': 1163.492, 'duration': 3.182}, {'end': 1169.356, 'text': 'now we will do left rotation means zig rotation.', 'start': 1166.674, 'duration': 2.682}, {'end': 1179.765, 'text': 'so now, after left rotation on this 10, the tree would be something like this see this 11 is to the left of 13, so to the left of 13.', 'start': 1171.721, 'duration': 8.044}, {'end': 1180.926, 'text': 'now we have 10.', 'start': 1179.765, 'duration': 1.161}, {'end': 1183.507, 'text': 'so the 11 would go to the right of this 10.', 'start': 1180.926, 'duration': 2.581}, {'end': 1184.788, 'text': 'now this is the final tree.', 'start': 1183.507, 'duration': 1.281}, {'end': 1186.789, 'text': 'as you can see, 13 is now the root.', 'start': 1184.788, 'duration': 2.001}, {'end': 1190.031, 'text': 'so this is the situation of zigzag situation.', 'start': 1186.789, 'duration': 3.242}, {'end': 1199.137, 'text': 'now, since the second case in zigzag situation may be what, suppose i want to search 9 now?', 'start': 1190.031, 'duration': 9.106}, {'end': 1202.52, 'text': 'same, compare with this 10 less than 10.', 'start': 1199.137, 'duration': 3.383}, {'end': 1203.981, 'text': 'so here greater than 7.', 'start': 1202.52, 'duration': 1.461}, {'end': 1205.201, 'text': 'so here we got this 9.', 'start': 1203.981, 'duration': 1.22}, {'end': 1207.403, 'text': 'now we are going to do splaying.', 'start': 1205.201, 'duration': 2.202}, {'end': 1208.424, 'text': 'splaying on this.', 'start': 1207.403, 'duration': 1.021}], 'summary': 'After one zig operation, 13 becomes the root in the final tree.', 'duration': 53.459, 'max_score': 1154.965, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qMmqOHr75b8/pics/qMmqOHr75b81154965.jpg'}, {'end': 1365.247, 'src': 'embed', 'start': 1328.464, 'weight': 3, 'content': [{'end': 1330.646, 'text': 'this is zigzag situation.', 'start': 1328.464, 'duration': 2.182}, {'end': 1333.228, 'text': 'now you can take, you can write down.', 'start': 1330.646, 'duration': 2.582}, {'end': 1340.974, 'text': 'the. both the cases means two rotation you can write down or you can take it within one rotation, that is zigzag rotation.', 'start': 1333.228, 'duration': 7.746}, {'end': 1343.495, 'text': 'so now we have discussed all the rotations.', 'start': 1341.855, 'duration': 1.64}, {'end': 1351.938, 'text': 'so somewhere you find out that they have written these three rotations only in splaying of the tree zig rotation, zig, zig and zigzag.', 'start': 1343.495, 'duration': 8.443}, {'end': 1355.379, 'text': 'or somewhere you find out that they have written six rotations.', 'start': 1351.938, 'duration': 3.441}, {'end': 1365.247, 'text': 'fine, so here in zig rotation they have covered both the cases zig and zeg right, either you can write down separately,', 'start': 1355.379, 'duration': 9.868}], 'summary': 'Discussion on zigzag rotations in trees, covering both two and six rotations.', 'duration': 36.783, 'max_score': 1328.464, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qMmqOHr75b8/pics/qMmqOHr75b81328464.jpg'}], 'start': 1015.464, 'title': 'Zigzag rotations in trees', 'summary': 'Discusses zigzag rotations in bst and binary trees, demonstrating left and right rotations to optimize tree structure, resulting in a new tree with 13 as the root node and emphasizing the coverage of rotations in splaying.', 'chapters': [{'end': 1208.424, 'start': 1015.464, 'title': 'Zigzag rotation in bst', 'summary': 'Discusses the concept of zigzag rotation in bst, where the process involves right and left rotations to restructure the tree, resulting in a new tree with the 13 as the root node and other nodes rearranged accordingly.', 'duration': 192.96, 'highlights': ['The process involves right rotation on the edge connecting 13 and 15, followed by left rotation to rearrange the tree, resulting in 13 as the root node.', 'The zigzag rotation process is demonstrated through the steps of performing zig rotation on the parent of the node, resulting in a new tree with 13 as the root node.', 'Splaying is performed to rearrange the tree when searching for 9, involving comparisons and restructuring of the tree based on the search process.']}, {'end': 1282.51, 'start': 1208.424, 'title': 'Zigzag situation in binary tree', 'summary': 'Explains a zigzag situation in a binary tree, demonstrating the process of left rotation and its impact on the tree structure, to optimize the tree for efficient search operations.', 'duration': 74.086, 'highlights': ['The chapter demonstrates the process of left rotation in a binary tree, specifically focusing on the repositioning of nodes to optimize search operations, such as moving 9 to the root and reorganizing its adjacent nodes (7 and 8) (Relevance: 5)', 'An explanation of the concept of a zigzag situation in a binary tree is provided, highlighting the significance of identifying and addressing such situations to improve the tree structure for efficient search operations (Relevance: 3)']}, {'end': 1374.011, 'start': 1282.51, 'title': 'Zig and zigzag rotations', 'summary': 'Discusses right rotations, specifically zig and zigzag rotations, and explains the final tree structure after the rotations, highlighting the concept of zigzag situations and the coverage of rotations in splaying of the tree.', 'duration': 91.501, 'highlights': ['The concept of zigzag situations is explained, where a node is rotated to the right of the root and then to the left of a child node, illustrating the tree restructuring process. This provides a clear understanding of the zigzag rotation process.', 'The coverage of rotations in splaying of the tree is discussed, emphasizing that both the cases of zig and zeg are covered within zig rotation, and both zigzag and zigzag cases are covered within zigzag rotation.']}], 'duration': 358.547, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qMmqOHr75b8/pics/qMmqOHr75b81015464.jpg', 'highlights': ['The process involves right rotation on the edge connecting 13 and 15, followed by left rotation to rearrange the tree, resulting in 13 as the root node.', 'The zigzag rotation process is demonstrated through the steps of performing zig rotation on the parent of the node, resulting in a new tree with 13 as the root node.', 'Splaying is performed to rearrange the tree when searching for 9, involving comparisons and restructuring of the tree based on the search process.', 'The concept of zigzag situations is explained, where a node is rotated to the right of the root and then to the left of a child node, illustrating the tree restructuring process.', 'The coverage of rotations in splaying of the tree is discussed, emphasizing that both the cases of zig and zeg are covered within zig rotation, and both zigzag and zigzag cases are covered within zigzag rotation.', 'An explanation of the concept of a zigzag situation in a binary tree is provided, highlighting the significance of identifying and addressing such situations to improve the tree structure for efficient search operations.']}, {'end': 1711.129, 'segs': [{'end': 1522.915, 'src': 'embed', 'start': 1467.121, 'weight': 0, 'content': [{'end': 1474.084, 'text': 'so that is the main advantage of split tree that the most frequently accessed element would be near to the root,', 'start': 1467.121, 'duration': 6.963}, {'end': 1477.145, 'text': 'so that you need to take less time to search those items.', 'start': 1474.084, 'duration': 3.061}, {'end': 1486.311, 'text': 'fine, and that is why, because of this advantage, one application of splay trees, what it is used, you know it is better.', 'start': 1477.645, 'duration': 8.666}, {'end': 1490.354, 'text': 'it is giving better performance in practical scenarios.', 'start': 1486.311, 'duration': 4.043}, {'end': 1496.158, 'text': 'right, better performance than avial and red black trees in practical situations.', 'start': 1490.354, 'duration': 5.804}, {'end': 1507.737, 'text': 'so in practical scenarios we are using splay trees mostly right, and these are invented, invented in 1985, fine.', 'start': 1496.158, 'duration': 11.579}, {'end': 1509.323, 'text': 'so one one application.', 'start': 1507.737, 'duration': 1.586}, {'end': 1516.75, 'text': 'maybe these are used to implement caches, right.', 'start': 1509.323, 'duration': 7.427}, {'end': 1522.915, 'text': "so i'm going to write down now the advantages, drawbacks and applications of splay trees.", 'start': 1516.75, 'duration': 6.165}], 'summary': 'Splay trees offer faster search with better performance than avl and red black trees, commonly used in practical scenarios, such as implementing caches, invented in 1985.', 'duration': 55.794, 'max_score': 1467.121, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qMmqOHr75b8/pics/qMmqOHr75b81467121.jpg'}, {'end': 1644.45, 'src': 'heatmap', 'start': 1603.719, 'weight': 4, 'content': [{'end': 1611.286, 'text': 'so that is why these are used in implementation of cache memories to save the time for accessing the data right now.', 'start': 1603.719, 'duration': 7.567}, {'end': 1615.239, 'text': 'drawback of this tree maybe see One.', 'start': 1611.286, 'duration': 3.953}, {'end': 1618.142, 'text': 'main topic is what these are not strictly balanced.', 'start': 1615.239, 'duration': 2.903}, {'end': 1623.848, 'text': 'So sometimes the height may be linear, or you can say order of n.', 'start': 1618.362, 'duration': 5.486}, {'end': 1629.716, 'text': 'that is the main drawback of this tree, because these are not strictly balanced trees.', 'start': 1624.912, 'duration': 4.804}, {'end': 1634.921, 'text': 'this may be skewed, fine, but this is very rare case.', 'start': 1629.716, 'duration': 5.205}, {'end': 1644.45, 'text': 'so that is why sometimes any single operation may take what order of, or you can say, theta n time complexity.', 'start': 1634.921, 'duration': 9.529}], 'summary': 'Cache memories use these trees, but drawbacks include non-strict balance, leading to linear height and theta n time complexity for some operations.', 'duration': 29.211, 'max_score': 1603.719, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qMmqOHr75b8/pics/qMmqOHr75b81603719.jpg'}], 'start': 1374.011, 'title': 'Advantages and drawbacks of splay trees', 'summary': 'Discusses the advantages of splay trees, including the reduction of time complexity to o(1) for frequently accessed elements and their practical applications. it also covers drawbacks such as potential linear height leading to rare o(n) time complexity and their applications in windows nt and gcc compilers.', 'chapters': [{'end': 1711.129, 'start': 1374.011, 'title': 'Advantages, drawbacks, and applications of splay trees', 'summary': 'Discusses the advantages of splay trees, including the reduction of time complexity to o(1) for frequently accessed elements, their use in practical scenarios for better performance, and applications in implementing caches. it also covers the drawbacks, such as potential linear height leading to rare o(n) time complexity, and applications in windows nt and gcc compilers.', 'duration': 337.118, 'highlights': ['Splaying the tree reduces the time complexity to O(1) for frequently accessed elements, resulting in better performance in practical scenarios.', 'The main advantage of splay trees is that the most frequently accessed element would be near to the root, reducing the time needed to search those items.', 'Splay trees are used in practical scenarios for better performance than avial and red black trees.', 'The drawbacks of splay trees include potential linear height leading to rare O(n) time complexity for some operations.', 'Splay trees are used to implement caches, as frequently accessed data is stored in caches to reduce access time to the data.']}], 'duration': 337.118, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qMmqOHr75b8/pics/qMmqOHr75b81374011.jpg', 'highlights': ['Splaying the tree reduces the time complexity to O(1) for frequently accessed elements, resulting in better performance in practical scenarios.', 'The main advantage of splay trees is that the most frequently accessed element would be near to the root, reducing the time needed to search those items.', 'Splay trees are used in practical scenarios for better performance than avial and red black trees.', 'Splay trees are used to implement caches, as frequently accessed data is stored in caches to reduce access time to the data.', 'The drawbacks of splay trees include potential linear height leading to rare O(n) time complexity for some operations.']}], 'highlights': ['Splay trees guarantee improved time complexity with O(log n) for search, insertion, and deletion operations.', 'The main advantage of splay trees is that the most frequently accessed element would be near to the root, reducing the time needed to search those items.', 'Splaying the tree reduces the time complexity to O(1) for frequently accessed elements, resulting in better performance in practical scenarios.', 'Splay trees are used in practical scenarios for better performance than avial and red black trees.', 'The drawbacks of splay trees include potential linear height leading to rare O(n) time complexity for some operations.', 'The chapter highlights the advantages, drawbacks, and applications of splay trees.', 'The video covers the differences between splay trees and other balancing binary search trees like avl and red-black trees.', 'Splay trees are self-balancing binary search trees, a variant of binary search trees.']}