title
5.16 Red Black tree | Introduction to Red Black trees | DSA Tutorials

description
In this lecture I have discussed basics of Red Black trees, need of Red Black trees, AVL trees vs Red Black Trees, properties of Red Black Trees with examples. DSA Full Course: https: https://www.youtube.com/playlist?list=PLdo5W4Nhv31bbKJzrsKfMpo_grxuLl8LU ****************************************** 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: 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/ #redblacktree #datastructures #ugcnetcomputerscience #jennyslecture

detail
{'title': '5.16 Red Black tree | Introduction to Red Black trees | DSA Tutorials', 'heatmap': [{'end': 261.365, 'start': 237.16, 'weight': 0.756}, {'end': 1367.269, 'start': 1325.155, 'weight': 0.709}, {'end': 1815.787, 'start': 1757.065, 'weight': 0.7}, {'end': 1881.875, 'start': 1860.265, 'weight': 0.755}], 'summary': 'This tutorial introduces red-black trees, emphasizing their advantages in large data sets for faster search, insertion, update, and deletion operations, comparing them with avl trees and binary search trees, and discussing their self-balancing properties, color coding, hierarchical structure, and limitations on path length.', 'chapters': [{'end': 120.023, 'segs': [{'end': 46.982, 'src': 'embed', 'start': 23.054, 'weight': 0, 'content': [{'end': 30.337, 'text': 'See, we have already discussed many types of trees, BS tree, binary tree, AVL tree, B tree, B plus tree, heap tree as well.', 'start': 23.054, 'duration': 7.283}, {'end': 36.459, 'text': 'Right So what is the need of red black tree? We have already many types of trees.', 'start': 30.697, 'duration': 5.762}, {'end': 40.42, 'text': 'Fine See, first of all, tree is what it is a data structure.', 'start': 37.179, 'duration': 3.241}, {'end': 46.982, 'text': "You can say data structure means it's a way of organizing the data, or you can say a way of organizing the data efficiently.", 'start': 40.44, 'duration': 6.542}], 'summary': 'Red black tree is a new type of tree structure.', 'duration': 23.928, 'max_score': 23.054, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/3RQtq7PDHog/pics/3RQtq7PDHog23054.jpg'}], 'start': 0.51, 'title': 'Understanding red black trees', 'summary': 'Discusses the advantages of using red black trees in large data sets for faster search, insertion, update, and deletion operations compared to other tree structures.', 'chapters': [{'end': 120.023, 'start': 0.51, 'title': 'Understanding red black trees', 'summary': 'Discusses the need for red black trees in efficiently organizing and accessing data, comparing it to other tree structures, and highlighting the advantages of using red black trees in large data sets for faster search, insertion, update, and deletion operations.', 'duration': 119.513, 'highlights': ['Red black tree is a way of organizing data efficiently for faster access and manipulation, particularly suitable for large data sets. (Relevance: 5)', 'Comparison of red black trees with other tree structures such as AVL trees, emphasizing the specific advantage of red black trees in certain scenarios. (Relevance: 4)', 'Explanation of the need for efficient data structures like red black trees for storing and processing large amounts of data, considering factors like frequent operations. (Relevance: 3)']}], 'duration': 119.513, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/3RQtq7PDHog/pics/3RQtq7PDHog510.jpg', 'highlights': ['Red black tree is a way of organizing data efficiently for faster access and manipulation, particularly suitable for large data sets. (Relevance: 5)', 'Comparison of red black trees with other tree structures such as AVL trees, emphasizing the specific advantage of red black trees in certain scenarios. (Relevance: 4)', 'Explanation of the need for efficient data structures like red black trees for storing and processing large amounts of data, considering factors like frequent operations. (Relevance: 3)']}, {'end': 443.44, 'segs': [{'end': 223.392, 'src': 'embed', 'start': 172.302, 'weight': 3, 'content': [{'end': 175.504, 'text': 'now this property is applied in all the nodes, on all the nodes.', 'start': 172.302, 'duration': 3.202}, {'end': 178.645, 'text': 'now for 7, left side child should be less than 7.', 'start': 175.504, 'duration': 3.141}, {'end': 181.427, 'text': 'suppose i am taking 3.', 'start': 178.645, 'duration': 2.782}, {'end': 185.829, 'text': 'right child of 7 should be greater than 7.', 'start': 181.427, 'duration': 4.402}, {'end': 189.27, 'text': 'now i am taking here 11.', 'start': 185.829, 'duration': 3.441}, {'end': 190.791, 'text': 'but is this a bst?', 'start': 189.27, 'duration': 1.521}, {'end': 191.932, 'text': 'no, it is not a bst.', 'start': 190.791, 'duration': 1.141}, {'end': 201.888, 'text': 'You should say that the left subtree because see 11 is greater than 7, but 11 is greater than 10 also.', 'start': 193.226, 'duration': 8.662}, {'end': 207.948, 'text': 'but to the left of 10, the value should be less than 10.', 'start': 203.106, 'duration': 4.842}, {'end': 210.968, 'text': 'it means this is the left subtree for this 10.', 'start': 207.948, 'duration': 3.02}, {'end': 214.249, 'text': 'this would be the right subtree for this 10 right.', 'start': 210.968, 'duration': 3.281}, {'end': 216.27, 'text': 'so in this, left subtrees,', 'start': 214.249, 'duration': 2.021}, {'end': 223.392, 'text': 'left subtree of any node should contain values less than that node and right subtree should contain values greater than that node.', 'start': 216.27, 'duration': 7.122}], 'summary': 'Property is applied in all nodes for a binary search tree', 'duration': 51.09, 'max_score': 172.302, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/3RQtq7PDHog/pics/3RQtq7PDHog172302.jpg'}, {'end': 275.828, 'src': 'heatmap', 'start': 237.16, 'weight': 0, 'content': [{'end': 247.291, 'text': 'Now, as we know that in binary search tree, the searching or you can say insertion and deletion is going to take order of log n time in average case.', 'start': 237.16, 'duration': 10.131}, {'end': 251.323, 'text': 'log 2, base 2 and n in average case.', 'start': 248.843, 'duration': 2.48}, {'end': 253.544, 'text': 'in best case it is order of 1.', 'start': 251.323, 'duration': 2.221}, {'end': 257.043, 'text': 'in worst case it is order of n right.', 'start': 253.544, 'duration': 3.499}, {'end': 261.365, 'text': 'in average case it is order of log n right.', 'start': 257.043, 'duration': 4.322}, {'end': 267.146, 'text': 'so you can say the searching of any data in binary search tree is going to take less time.', 'start': 261.365, 'duration': 5.781}, {'end': 270.927, 'text': 'that is why, obviously, we are using tree data structures right.', 'start': 267.146, 'duration': 3.781}, {'end': 273.867, 'text': 'how see, suppose i am taking this is one bst.', 'start': 270.927, 'duration': 2.94}, {'end': 274.907, 'text': 'this is another bst.', 'start': 273.867, 'duration': 1.04}, {'end': 275.828, 'text': 'two types of bst.', 'start': 274.907, 'duration': 0.921}], 'summary': 'Binary search tree allows log n time for searching, insertion and deletion in average case, making it efficient for data retrieval.', 'duration': 24.505, 'max_score': 237.16, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/3RQtq7PDHog/pics/3RQtq7PDHog237160.jpg'}], 'start': 120.023, 'title': 'Binary search trees and time complexity', 'summary': 'Discusses the concept of binary search trees and their time complexity, emphasizing the property of left and right subtrees and highlighting that searching in a balanced binary search tree takes average case log n time and worst case n time.', 'chapters': [{'end': 223.392, 'start': 120.023, 'title': 'Understanding binary search trees', 'summary': 'Discusses the concept of binary search trees, emphasizing the property that the left subtree of a node should contain values less than that node and the right subtree should contain values greater than that node, illustrated with examples.', 'duration': 103.369, 'highlights': ['The left subtree of a node should contain values less than that node, and the right subtree should contain values greater than that node, as illustrated through examples. Property of binary search trees', 'Explanation of how the binary search tree property applies to all nodes and their respective children, with a visual example. Demonstration of applying the property to all nodes', 'Illustration of a non-binary search tree example, highlighting the violation of the property and explaining why it does not adhere to the binary search tree rules. Identification of non-binary search tree']}, {'end': 443.44, 'start': 223.392, 'title': 'Binary search trees and time complexity', 'summary': 'Explains the advantages of using balanced binary search trees, highlighting that in average case, searching in a binary search tree takes order of log n time, while in the worst case, it takes order of n time.', 'duration': 220.048, 'highlights': ['In average case, searching in a binary search tree takes order of log n time. The average case time complexity for searching in a binary search tree is order of log n, making it efficient for searching operations.', 'In worst case, searching in a binary search tree takes order of n time. In the worst case, the time complexity for searching in a binary search tree is order of n, which emphasizes the importance of maintaining a balanced tree to minimize search time.', 'Balanced binary search trees ensure that all operations have time complexity of order of log n only, which is significantly less than order of n. Maintaining a balanced binary search tree ensures that operations such as insertion, deletion, and searching have a time complexity of order of log n, which is much more efficient than order of n.']}], 'duration': 323.417, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/3RQtq7PDHog/pics/3RQtq7PDHog120023.jpg', 'highlights': ['Balanced binary search trees ensure operations have time complexity of order of log n, significantly less than order of n.', 'Average case time complexity for searching in a binary search tree is order of log n, making it efficient for searching operations.', 'In worst case, searching in a binary search tree takes order of n time, emphasizing the importance of maintaining a balanced tree to minimize search time.', 'The left subtree of a node should contain values less than that node, and the right subtree should contain values greater than that node, as illustrated through examples.', 'Explanation of how the binary search tree property applies to all nodes and their respective children, with a visual example.']}, {'end': 611.85, 'segs': [{'end': 521.797, 'src': 'embed', 'start': 491.686, 'weight': 0, 'content': [{'end': 499.311, 'text': 'but avial tree guarantees that the time complexity would be log n only because this is what height, height balanced tree.', 'start': 491.686, 'duration': 7.625}, {'end': 504.532, 'text': 'so why we are using red black trees, how red black trees are different from avial trees.', 'start': 499.311, 'duration': 5.221}, {'end': 506.033, 'text': 'see now.', 'start': 504.532, 'duration': 1.501}, {'end': 513.755, 'text': 'main difference is what, in avial tree, you need to do many rotations, sometimes if tree is very large.', 'start': 506.033, 'duration': 7.722}, {'end': 521.797, 'text': 'so maybe you require more than two, three, four, five, six or many rotations to balance that tree.', 'start': 513.755, 'duration': 8.042}], 'summary': 'Avl tree guarantees log n time complexity due to its height balance. red black trees require fewer rotations for balancing.', 'duration': 30.111, 'max_score': 491.686, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/3RQtq7PDHog/pics/3RQtq7PDHog491686.jpg'}, {'end': 595.24, 'src': 'embed', 'start': 565.591, 'weight': 1, 'content': [{'end': 570.812, 'text': 'maximum two rotations would be required and the tree would be balanced right.', 'start': 565.591, 'duration': 5.221}, {'end': 576.034, 'text': 'and sometimes even the rotations would not be required and recoloring would be required.', 'start': 570.812, 'duration': 5.222}, {'end': 582.473, 'text': 'recoloring means, as the name suggests, the nodes would be either red or black.', 'start': 576.034, 'duration': 6.439}, {'end': 589.056, 'text': 'so you need to change the color only if the node is red, just change it to black, something like this.', 'start': 582.473, 'duration': 6.583}, {'end': 595.24, 'text': 'we will discuss these rules in the next video when we are going to discuss the insertion part right.', 'start': 589.056, 'duration': 6.184}], 'summary': 'Balancing a tree may require up to two rotations, or recoloring if node is red.', 'duration': 29.649, 'max_score': 565.591, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/3RQtq7PDHog/pics/3RQtq7PDHog565591.jpg'}], 'start': 443.44, 'title': 'Red black trees vs avl trees', 'summary': 'Explains differences between red-black trees and avl trees. avl trees may require many rotations to balance large trees, while red-black trees need at most two rotations and sometimes only require recoloring.', 'chapters': [{'end': 611.85, 'start': 443.44, 'title': 'Red black trees vs avl trees', 'summary': 'Explains the differences between red-black trees and avl trees, emphasizing that avl trees may require many rotations to balance large trees, while red-black trees need at most two rotations and sometimes only require recoloring.', 'duration': 168.41, 'highlights': ['Red-black trees need at most two rotations to balance, while AVL trees may require many rotations for large trees.', 'Recoloring may be sufficient for balancing red-black trees, while AVL trees may require rotations up to the root node.', 'In AVL trees, time complexity can be order of n in worst case due to left or right skewed trees, while red-black trees guarantee time complexity of log n due to being height balanced.']}], 'duration': 168.41, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/3RQtq7PDHog/pics/3RQtq7PDHog443440.jpg', 'highlights': ['Red-black trees need at most two rotations to balance, while AVL trees may require many rotations for large trees.', 'Recoloring may be sufficient for balancing red-black trees, while AVL trees may require rotations up to the root node.', 'In AVL trees, time complexity can be order of n in worst case due to left or right skewed trees, while red-black trees guarantee time complexity of log n due to being height balanced.']}, {'end': 1300.152, 'segs': [{'end': 689.368, 'src': 'embed', 'start': 639.89, 'weight': 0, 'content': [{'end': 645.313, 'text': "you can say searching, insertion, deletion, these kind of operations and that that's exactly we want.", 'start': 639.89, 'duration': 5.423}, {'end': 647.815, 'text': 'the time complexity would be this one right.', 'start': 645.313, 'duration': 2.502}, {'end': 650.136, 'text': 'so we can go for red black trees.', 'start': 647.815, 'duration': 2.321}, {'end': 655.96, 'text': 'in the case, when you are, you are going to perform insertion and deletion operation very frequently.', 'start': 650.136, 'duration': 5.824}, {'end': 663.575, 'text': 'see, searching is faster in avial tree because it is strictly height balanced tree.', 'start': 657.25, 'duration': 6.325}, {'end': 674.583, 'text': 'but insertion and deletion is faster in red black trees because here we require few rotations and in avial trees we require many rotations.', 'start': 663.575, 'duration': 11.008}, {'end': 680.626, 'text': 'right. so depends on the situation, depends on the operations you want to perform on the tree.', 'start': 674.583, 'duration': 6.043}, {'end': 682.706, 'text': 'we are going to choose the trees.', 'start': 680.626, 'duration': 2.08}, {'end': 683.787, 'text': "it's not like that.", 'start': 682.706, 'duration': 1.081}, {'end': 687.448, 'text': 'red black trees are best and these are not good right.', 'start': 683.787, 'duration': 3.661}, {'end': 689.368, 'text': 'it depends on the situation.', 'start': 687.448, 'duration': 1.92}], 'summary': 'Red-black trees are faster for frequent insertion and deletion, while avl trees are faster for searching due to their height balance.', 'duration': 49.478, 'max_score': 639.89, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/3RQtq7PDHog/pics/3RQtq7PDHog639890.jpg'}, {'end': 768.052, 'src': 'embed', 'start': 736.698, 'weight': 4, 'content': [{'end': 739.639, 'text': 'next is obviously it is a red black tree.', 'start': 736.698, 'duration': 2.941}, {'end': 743.02, 'text': 'so every node is either red or black.', 'start': 739.639, 'duration': 3.381}, {'end': 752.76, 'text': 'right it means every node is having a special bit which shows the color of the node, A one bit.', 'start': 743.02, 'duration': 9.74}, {'end': 758.344, 'text': 'you can say 0 means black and 1 means red.', 'start': 752.76, 'duration': 5.584}, {'end': 762.347, 'text': 'Only one extra bit would be required with each node.', 'start': 759.185, 'duration': 3.162}, {'end': 768.052, 'text': 'and rather than this bit, each node is containing what obviously the node is same as binary tree.', 'start': 763.45, 'duration': 4.602}], 'summary': 'Red-black tree nodes have a color bit, 0 for black and 1 for red, requiring only one extra bit per node.', 'duration': 31.354, 'max_score': 736.698, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/3RQtq7PDHog/pics/3RQtq7PDHog736698.jpg'}, {'end': 1035.339, 'src': 'embed', 'start': 1004.18, 'weight': 3, 'content': [{'end': 1009.844, 'text': 'in another term you can say There should not be no red-red parent-child relationship.', 'start': 1004.18, 'duration': 5.664}, {'end': 1014.708, 'text': 'Or you can say that no adjacent node can be red.', 'start': 1010.324, 'duration': 4.384}, {'end': 1016.229, 'text': 'Something like this.', 'start': 1015.569, 'duration': 0.66}, {'end': 1024.116, 'text': 'See this root is black, right? So this and this can be black, can be red.', 'start': 1017.19, 'duration': 6.926}, {'end': 1030.613, 'text': 'right, because constraint is only on the red nodes, not on the black color.', 'start': 1025.307, 'duration': 5.306}, {'end': 1035.339, 'text': 'on the black nodes, constraint is this one, that thing we will discuss right.', 'start': 1030.613, 'duration': 4.726}], 'summary': 'No adjacent node can be red in the parent-child relationship.', 'duration': 31.159, 'max_score': 1004.18, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/3RQtq7PDHog/pics/3RQtq7PDHog1004180.jpg'}], 'start': 611.85, 'title': 'Red black trees vs avl trees', 'summary': 'Compares red black trees and avl trees, highlighting that red black trees ensure o(log n) time complexity for all operations, making them suitable for frequent insertion and deletion despite being less balanced than avl trees. it also provides an overview of red black trees, discussing the self-balancing property, color coding, hierarchical structure, rotations and recoloring rules, significance of black nodes, prohibition of red-red parent-child relationship, and uniformity of black nodes in paths.', 'chapters': [{'end': 713.634, 'start': 611.85, 'title': 'Red black trees vs avl trees', 'summary': 'Discusses the differences between red black trees and avl trees, emphasizing that red black trees guarantee a time complexity of o(log n) for all operations, making them suitable for frequent insertion and deletion despite being less balanced than avl trees.', 'duration': 101.784, 'highlights': ['Red black trees guarantee a time complexity of O(log n) for all operations, making them suitable for frequent insertion and deletion despite being less balanced than avl trees.', 'Searching is faster in avl trees due to their strict height balance, while insertion and deletion are faster in red black trees due to fewer rotations required.', 'The choice between red black trees and avl trees depends on the specific operations and frequency of insertion and deletion in the tree.']}, {'end': 1300.152, 'start': 713.634, 'title': 'Red black trees overview', 'summary': 'Introduces the concept of red black trees, emphasizing the self-balancing property, color coding, and hierarchical structure. it discusses the rule for rotations and recoloring, the significance of black nodes, the prohibition of red-red parent-child relationship, and the uniformity of black nodes in paths.', 'duration': 586.518, 'highlights': ['The tree is a self-balancing binary search tree that ensures every leaf node, represented by nil, is black, and prohibits red-red parent-child relationship, with the constraint that every path from a node to any of its descendant nil nodes must have the same number of black nodes (8 instances mentioned).', 'The introduction of red black trees, emphasizing the self-balancing property and color coding, with each node containing a special bit to indicate its color, either red or black, ensuring the root node is always black, and the prohibition of red-red parent-child relationship.', 'The significance of black nodes in red black trees, with every leaf node being nil and black, and the hierarchical structure ensuring that the head node remains black, symbolizing calmness and stability within the tree.', 'The discussion of the rule for rotations and recoloring, the implementation of the node structure, and the prohibition of red-red parent-child relationship, ensuring that if a node is red, its children must be black.']}], 'duration': 688.302, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/3RQtq7PDHog/pics/3RQtq7PDHog611850.jpg', 'highlights': ['Red black trees guarantee O(log n) time complexity for all operations, suitable for frequent insertion and deletion.', 'Searching is faster in avl trees due to strict height balance, while insertion and deletion are faster in red black trees.', 'The choice between red black trees and avl trees depends on specific operations and frequency of insertion and deletion.', 'Red black trees ensure every leaf node is black, prohibit red-red parent-child relationship, and maintain uniform black nodes in paths.', 'Red black trees use color coding to indicate node color, with the root node always being black, ensuring stability within the tree.', 'Discussion of rotations, recoloring rules, and prohibition of red-red parent-child relationship in red black trees.']}, {'end': 1491.444, 'segs': [{'end': 1331.448, 'src': 'embed', 'start': 1300.152, 'weight': 0, 'content': [{'end': 1304.715, 'text': 'now i guess in every path we have same number of black nodes.', 'start': 1300.152, 'duration': 4.563}, {'end': 1307.357, 'text': 'so now this is a red black tree.', 'start': 1304.715, 'duration': 2.642}, {'end': 1312.661, 'text': 'now the question may be is every avial tree can be a red black tree.', 'start': 1307.357, 'duration': 5.304}, {'end': 1320.327, 'text': 'see, if a tree is avial tree and you color it red and black according to the rules, then it would be a red black tree.', 'start': 1312.661, 'duration': 7.666}, {'end': 1325.155, 'text': 'so you can say avial trees are subset of red black trees.', 'start': 1320.327, 'duration': 4.828}, {'end': 1331.448, 'text': 'right, but if a tree is red black tree then it is not true that that would be avial tree.', 'start': 1325.155, 'duration': 6.293}], 'summary': 'Red-black trees have same number of black nodes in every path. avial trees are a subset of red-black trees.', 'duration': 31.296, 'max_score': 1300.152, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/3RQtq7PDHog/pics/3RQtq7PDHog1300152.jpg'}, {'end': 1367.269, 'src': 'heatmap', 'start': 1325.155, 'weight': 0.709, 'content': [{'end': 1331.448, 'text': 'right, but if a tree is red black tree then it is not true that that would be avial tree.', 'start': 1325.155, 'duration': 6.293}, {'end': 1334.543, 'text': 'maybe if you remove the coloring.', 'start': 1332.403, 'duration': 2.14}, {'end': 1338.264, 'text': 'so it is not compulsory that that that tree would be avial tree,', 'start': 1334.543, 'duration': 3.721}, {'end': 1345.345, 'text': 'because these trees are roughly height balanced and avial tree is strictly height balanced tree.', 'start': 1338.264, 'duration': 7.081}, {'end': 1349.146, 'text': "right now i'm going to give you some examples and we will see.", 'start': 1345.345, 'duration': 3.801}, {'end': 1351.466, 'text': 'are those trees red, black trees or not?', 'start': 1349.146, 'duration': 2.32}, {'end': 1354.087, 'text': 'if not, which property they are violating?', 'start': 1351.466, 'duration': 2.621}, {'end': 1357.107, 'text': 'fine, so let us take these three examples.', 'start': 1354.087, 'duration': 3.02}, {'end': 1358.547, 'text': 'are these red, black trees or not?', 'start': 1357.107, 'duration': 1.44}, {'end': 1359.488, 'text': 'first of all this thing.', 'start': 1358.547, 'duration': 0.941}, {'end': 1360.628, 'text': 'check out this thing.', 'start': 1359.488, 'duration': 1.14}, {'end': 1365.049, 'text': 'see, here you can say first of all it is a bst or not right.', 'start': 1360.628, 'duration': 4.421}, {'end': 1367.269, 'text': 'so you have to check out that condition.', 'start': 1365.049, 'duration': 2.22}], 'summary': 'Discussion on red-black trees and their properties, including examples of violating properties.', 'duration': 42.114, 'max_score': 1325.155, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/3RQtq7PDHog/pics/3RQtq7PDHog1325155.jpg'}, {'end': 1404.353, 'src': 'embed', 'start': 1374.11, 'weight': 3, 'content': [{'end': 1376.431, 'text': 'no need to check out other conditions.', 'start': 1374.11, 'duration': 2.321}, {'end': 1378.311, 'text': 'right. first is violated.', 'start': 1376.431, 'duration': 1.88}, {'end': 1380.712, 'text': 'it means it is not a red black tree.', 'start': 1378.311, 'duration': 2.401}, {'end': 1394.766, 'text': 'next is this one here see, i have, all the nodes are black right and obviously this is a bst because it is following a bst property right now.', 'start': 1380.712, 'duration': 14.054}, {'end': 1398.07, 'text': 'but this is not a red black tree.', 'start': 1394.766, 'duration': 3.304}, {'end': 1400.851, 'text': 'why? so which property this is violating?', 'start': 1398.07, 'duration': 2.781}, {'end': 1402.692, 'text': 'see, see, first, property is what.', 'start': 1400.851, 'duration': 1.841}, {'end': 1404.353, 'text': 'every node is either black or red.', 'start': 1402.692, 'duration': 1.661}], 'summary': 'Nodes violate red-black tree properties, not a valid red-black tree.', 'duration': 30.243, 'max_score': 1374.11, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/3RQtq7PDHog/pics/3RQtq7PDHog1374110.jpg'}, {'end': 1459.792, 'src': 'embed', 'start': 1428.062, 'weight': 2, 'content': [{'end': 1432.084, 'text': "so obviously i'm not drawing those nil that are black.", 'start': 1428.062, 'duration': 4.022}, {'end': 1434.706, 'text': 'consider that thing right.', 'start': 1432.084, 'duration': 2.622}, {'end': 1437.288, 'text': 'if node is red, then its children are black black.', 'start': 1434.706, 'duration': 2.582}, {'end': 1439.429, 'text': 'but here no red node is there.', 'start': 1437.288, 'duration': 2.141}, {'end': 1451.557, 'text': 'now this property see every path from any node to its descendant null nodes or nil nodes must contain same number of black nodes.', 'start': 1439.429, 'duration': 12.128}, {'end': 1456.009, 'text': 'Now check out this path to its nil nodes.', 'start': 1452.546, 'duration': 3.463}, {'end': 1458.03, 'text': '1, 2, 3 black nodes.', 'start': 1456.769, 'duration': 1.261}, {'end': 1459.792, 'text': 'Here also 1, 2, 3 fine.', 'start': 1458.29, 'duration': 1.502}], 'summary': 'In a red-black tree, paths have equal black nodes from any node to nil nodes.', 'duration': 31.73, 'max_score': 1428.062, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/3RQtq7PDHog/pics/3RQtq7PDHog1428062.jpg'}], 'start': 1300.152, 'title': 'Red-black trees', 'summary': 'Discusses the relationship between red-black trees and avl trees, stating that every avl tree can be a red-black tree, but not vice versa due to height balancing requirements. it also covers the process of checking if a binary search tree is a red-black tree, emphasizing the color and arrangement of nodes, and the structure of a red-black tree with a focus on the number of black nodes along paths.', 'chapters': [{'end': 1351.466, 'start': 1300.152, 'title': 'Red black trees vs. avl trees', 'summary': 'Discusses the relationship between red-black trees and avl trees, stating that while every avl tree can be a red-black tree, the reverse is not true due to the difference in height balancing requirements.', 'duration': 51.314, 'highlights': ['A red-black tree is a type of binary search tree where every path has the same number of black nodes, making it roughly height balanced.', 'AVL trees are a subset of red-black trees, as every AVL tree can be colored red and black according to the rules, resulting in a red-black tree.', 'While an AVL tree can always be transformed into a red-black tree, the reverse is not necessarily true due to the stricter height balancing requirement of AVL trees.']}, {'end': 1404.353, 'start': 1351.466, 'title': 'Red black trees property check', 'summary': 'Discusses the process of checking if a given binary search tree is a red black tree, using specific examples and identifying the violated properties, with a focus on the color and arrangement of nodes.', 'duration': 52.887, 'highlights': ['The root node being red instead of black violates the property of a red black tree, making it not a valid red black tree.', 'All nodes being black satisfies the binary search tree property but violates the red black tree property, where every node should be either black or red.']}, {'end': 1491.444, 'start': 1404.353, 'title': 'Red-black tree structure', 'summary': 'Discusses the structure of a red-black tree, emphasizing the rule that every path from any node to its descendant null nodes must contain the same number of black nodes and highlighting an example where this condition is violated.', 'duration': 87.091, 'highlights': ['The rule that every path from any node to its descendant null nodes must contain the same number of black nodes is emphasized, with an example where this condition is violated.', 'The importance of the root being black and every leaf node being black is mentioned, but not explicitly highlighted as a key point in the summary.', 'The concept that if a node is red, its children should be black is explained, but not explicitly highlighted as a key point in the summary.']}], 'duration': 191.292, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/3RQtq7PDHog/pics/3RQtq7PDHog1300152.jpg', 'highlights': ['AVL trees are a subset of red-black trees, as every AVL tree can be colored red and black according to the rules, resulting in a red-black tree.', 'A red-black tree is a type of binary search tree where every path has the same number of black nodes, making it roughly height balanced.', 'The rule that every path from any node to its descendant null nodes must contain the same number of black nodes is emphasized, with an example where this condition is violated.', 'The root node being red instead of black violates the property of a red black tree, making it not a valid red black tree.']}, {'end': 1979.513, 'segs': [{'end': 1538.531, 'src': 'embed', 'start': 1512.114, 'weight': 0, 'content': [{'end': 1520.317, 'text': 'each node is having exactly two children and these leaf node should be at the same level.', 'start': 1512.114, 'duration': 8.203}, {'end': 1530.224, 'text': 'so here you can say every perfect binary tree that contains only black nodes is also a red black tree.', 'start': 1520.317, 'duration': 9.907}, {'end': 1532.506, 'text': 'so now this is a red black tree.', 'start': 1530.224, 'duration': 2.282}, {'end': 1534.207, 'text': 'right, this is a red black tree.', 'start': 1532.506, 'duration': 1.701}, {'end': 1535.789, 'text': 'now check out this thing.', 'start': 1534.207, 'duration': 1.582}, {'end': 1538.531, 'text': 'is this a binary tree, binary search tree?', 'start': 1535.789, 'duration': 2.742}], 'summary': 'A red black tree has exactly two children for each node and all leaf nodes are at the same level, making it a perfect binary tree.', 'duration': 26.417, 'max_score': 1512.114, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/3RQtq7PDHog/pics/3RQtq7PDHog1512114.jpg'}, {'end': 1679.116, 'src': 'embed', 'start': 1651.08, 'weight': 2, 'content': [{'end': 1653.402, 'text': 'yes, but see, this is red.', 'start': 1651.08, 'duration': 2.322}, {'end': 1654.743, 'text': 'this is also red.', 'start': 1653.402, 'duration': 1.341}, {'end': 1659.328, 'text': 'but if a node is red, then its children should be black.', 'start': 1654.743, 'duration': 4.585}, {'end': 1663.933, 'text': 'so this is violating this property, the this one right.', 'start': 1659.328, 'duration': 4.605}, {'end': 1673.051, 'text': 'if i write here black, then then is it is a red black tree, right, this property is also followed.', 'start': 1663.933, 'duration': 9.118}, {'end': 1674.112, 'text': 'now check out this one.', 'start': 1673.051, 'duration': 1.061}, {'end': 1675.833, 'text': 'check out the path from here to here.', 'start': 1674.112, 'duration': 1.721}, {'end': 1678.135, 'text': 'we have one to two black nodes from here to here.', 'start': 1675.833, 'duration': 2.302}, {'end': 1679.116, 'text': 'also two black nodes.', 'start': 1678.135, 'duration': 0.981}], 'summary': 'Violation of red-black tree property: node is red but its children are black.', 'duration': 28.036, 'max_score': 1651.08, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/3RQtq7PDHog/pics/3RQtq7PDHog1651080.jpg'}, {'end': 1815.787, 'src': 'heatmap', 'start': 1757.065, 'weight': 0.7, 'content': [{'end': 1765.75, 'text': "if you do the coloring black right, suppose zero, i'm taking so in this node b, one, two and three, three black nodes.", 'start': 1757.065, 'duration': 8.685}, {'end': 1767.45, 'text': 'but here we have only two black nodes.', 'start': 1765.75, 'duration': 1.7}, {'end': 1770.394, 'text': 'so this is not possible right.', 'start': 1767.45, 'duration': 2.944}, {'end': 1772.555, 'text': 'so now here one more point about red black tree.', 'start': 1770.394, 'duration': 2.161}, {'end': 1779.456, 'text': 'is what we are drawing that point from this property only because this, because of this property, we cannot add here one more node,', 'start': 1772.555, 'duration': 6.901}, {'end': 1781.997, 'text': 'neither red nor black right.', 'start': 1779.456, 'duration': 2.541}, {'end': 1793.825, 'text': 'so here you can say the longest path from the root is no more then twice the length of the shortest path.', 'start': 1781.997, 'duration': 11.828}, {'end': 1800.454, 'text': 'Or you can say, see the path from root to its farthest leaf node.', 'start': 1794.366, 'duration': 6.088}, {'end': 1815.787, 'text': 'Farthest means to its extreme leaf node right? is no more than twice as long as the path from root to its nearest leaf node.', 'start': 1800.835, 'duration': 14.952}], 'summary': 'Red-black tree ensures longest path is at most twice as long as shortest path', 'duration': 58.722, 'max_score': 1757.065, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/3RQtq7PDHog/pics/3RQtq7PDHog1757065.jpg'}, {'end': 1889.179, 'src': 'heatmap', 'start': 1860.265, 'weight': 0.755, 'content': [{'end': 1863.206, 'text': 'having four this to this.', 'start': 1860.265, 'duration': 2.941}, {'end': 1864.027, 'text': 'then this to this.', 'start': 1863.206, 'duration': 0.821}, {'end': 1865.067, 'text': 'that is four.', 'start': 1864.027, 'duration': 1.04}, {'end': 1867.589, 'text': 'it means two into two, that is four.', 'start': 1865.067, 'duration': 2.522}, {'end': 1871.005, 'text': 'it cannot be more than four.', 'start': 1868.863, 'duration': 2.142}, {'end': 1874.669, 'text': 'so you can say it cannot be more than twice.', 'start': 1871.005, 'duration': 3.664}, {'end': 1877.631, 'text': 'then this path right.', 'start': 1874.669, 'duration': 2.962}, {'end': 1878.993, 'text': 'that is one more.', 'start': 1877.631, 'duration': 1.362}, {'end': 1881.875, 'text': 'you can say that point about red black trees.', 'start': 1878.993, 'duration': 2.882}, {'end': 1883.737, 'text': 'i hope you are getting this property.', 'start': 1881.875, 'duration': 1.862}, {'end': 1884.237, 'text': 'see here.', 'start': 1883.737, 'duration': 0.5}, {'end': 1889.179, 'text': 'we can add some node here, right.', 'start': 1884.237, 'duration': 4.942}], 'summary': 'Four is the maximum, twice at most. red-black trees properties explained.', 'duration': 28.914, 'max_score': 1860.265, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/3RQtq7PDHog/pics/3RQtq7PDHog1860265.jpg'}, {'end': 1963.825, 'src': 'embed', 'start': 1937.222, 'weight': 1, 'content': [{'end': 1947.106, 'text': 'so that is one more point, and that point has been, you know, driven from this point, only the longest path from root to its leaf node, uh, cannot be,', 'start': 1937.222, 'duration': 9.884}, {'end': 1953.388, 'text': 'you know, more than twice the length of the shortest path.', 'start': 1947.106, 'duration': 6.282}, {'end': 1954.909, 'text': 'so now this is question for you.', 'start': 1953.388, 'duration': 1.521}, {'end': 1957.91, 'text': 'you need to tell me, is this a red black tree or not?', 'start': 1954.909, 'duration': 3.001}, {'end': 1963.825, 'text': 'if not, then which property this tree is violating?', 'start': 1958.883, 'duration': 4.942}], 'summary': 'Red-black tree: longest path <= 2*shortest path', 'duration': 26.603, 'max_score': 1937.222, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/3RQtq7PDHog/pics/3RQtq7PDHog1937222.jpg'}], 'start': 1491.444, 'title': 'Red-black trees', 'summary': 'Introduces red-black trees, explaining their properties and relationship with perfect binary trees and binary search trees. it also emphasizes the key property of red-black trees, highlighting the limitations on the longest path from root to leaf nodes not being more than twice the length of the shortest path.', 'chapters': [{'end': 1979.513, 'start': 1491.444, 'title': 'Introduction to red black trees', 'summary': 'Introduces red-black trees, explaining their properties and relationship with perfect binary trees and binary search trees. it also emphasizes the key property of red-black trees, highlighting the limitations on the longest path from root to leaf nodes not being more than twice the length of the shortest path.', 'duration': 488.069, 'highlights': ['Every perfect binary tree containing only black nodes is also a red-black tree. Perfect binary trees with only black nodes are also classified as red-black trees, expanding the scope of red-black tree classification. This provides a clear relationship between perfect binary trees and red-black trees.', 'The key property of red-black trees is the limitation on the longest path from root to leaf nodes not being more than twice the length of the shortest path. Red-black trees are characterized by the key property that the longest path from the root to its leaf nodes cannot be more than twice the length of the shortest path. This property is crucial in understanding and analyzing the structure of red-black trees.', 'The chapter emphasizes the limitations on adding nodes to red-black trees, highlighting the constraints on node coloring to maintain the red-black tree properties. The chapter emphasizes the limitations on adding nodes to red-black trees, highlighting the constraints on node coloring to maintain the red-black tree properties. It clarifies that the addition of nodes, whether red or black, is restricted by the need to maintain the balance of black nodes in paths.']}], 'duration': 488.069, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/3RQtq7PDHog/pics/3RQtq7PDHog1491444.jpg', 'highlights': ['Perfect binary trees with only black nodes are also classified as red-black trees, expanding the scope of red-black tree classification.', 'Red-black trees are characterized by the key property that the longest path from the root to its leaf nodes cannot be more than twice the length of the shortest path.', 'The chapter emphasizes the limitations on adding nodes to red-black trees, highlighting the constraints on node coloring to maintain the red-black tree properties.']}], 'highlights': ['Red black tree is a way of organizing data efficiently for faster access and manipulation, particularly suitable for large data sets. (Relevance: 5)', 'Comparison of red black trees with other tree structures such as AVL trees, emphasizing the specific advantage of red black trees in certain scenarios. (Relevance: 4)', 'Explanation of the need for efficient data structures like red black trees for storing and processing large amounts of data, considering factors like frequent operations. (Relevance: 3)', 'Red black trees guarantee O(log n) time complexity for all operations, suitable for frequent insertion and deletion.', 'Red black trees ensure every leaf node is black, prohibit red-red parent-child relationship, and maintain uniform black nodes in paths.', 'Red-black trees need at most two rotations to balance, while AVL trees may require many rotations for large trees.', 'Red-black trees use color coding to indicate node color, with the root node always being black, ensuring stability within the tree.', 'Red-black trees are characterized by the key property that the longest path from the root to its leaf nodes cannot be more than twice the length of the shortest path.']}