title
5.17 Red Black Tree Insertion | Insertion Algorithm | Data Structure Tutorials
description
Explained how to do insertion in red black tree
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 #jennyslectures #dsa
detail
{'title': '5.17 Red Black Tree Insertion | Insertion Algorithm | Data Structure Tutorials', 'heatmap': [{'end': 666.514, 'start': 630.416, 'weight': 0.834}, {'end': 964.796, 'start': 941.746, 'weight': 0.712}], 'summary': 'Tutorial series covers red-black tree insertion and operations, emphasizing self-balancing, maintaining tree properties, and resolving red-red conflicts through recoloring and rotations, with specific examples of node insertions.', 'chapters': [{'end': 144.035, 'segs': [{'end': 66.799, 'src': 'embed', 'start': 35.797, 'weight': 0, 'content': [{'end': 40.098, 'text': 'now these are some rules, how we are going to insert the data in red black trees.', 'start': 35.797, 'duration': 4.301}, {'end': 43.039, 'text': 'we are going to discuss the rules one by one, right,', 'start': 40.098, 'duration': 2.941}, {'end': 52.701, 'text': 'and these three are the red black tree properties means red black tree is what it is a self-balancing binary search tree which must follow these properties.', 'start': 43.039, 'duration': 9.662}, {'end': 54.662, 'text': 'means root should be black.', 'start': 52.701, 'duration': 1.961}, {'end': 59.496, 'text': 'second thing is no two adjacent red nodes means.', 'start': 54.662, 'duration': 4.834}, {'end': 66.799, 'text': 'in other words, you can say if parent node is red then its children should be black right.', 'start': 59.496, 'duration': 7.303}], 'summary': 'Discussion of rules for inserting data into red-black trees, emphasizing properties like root being black and no adjacent red nodes.', 'duration': 31.002, 'max_score': 35.797, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qA02XWRTBdw/pics/qA02XWRTBdw35797.jpg'}], 'start': 0.289, 'title': 'Red black tree insertion', 'summary': 'Discusses the insertion in red black trees, covering the properties and rules for insertion, highlighting the importance of self-balancing and the key properties of red black trees, and demonstrating the insertion process with examples.', 'chapters': [{'end': 144.035, 'start': 0.289, 'title': 'Red black tree insertion', 'summary': 'Discusses the insertion in red black trees, covering the properties and rules for insertion, highlighting the importance of self-balancing and the key properties of red black trees, and demonstrating the insertion process with examples.', 'duration': 143.746, 'highlights': ['Red black tree is a self-balancing binary search tree with specific properties. The red black tree is a self-balancing binary search tree that must follow specific properties, such as the root being black, no two adjacent red nodes, and the count of black nodes in each path being the same.', 'Explanation of rules for inserting data in red black trees. The chapter explains the rules for inserting data in red black trees, including creating a new black root node when the tree is empty and following binary search tree insertion rules.', 'Demonstration of inserting data (10 and 18) in the red black tree. The chapter demonstrates the insertion of data (10 and 18) in the red black tree, following the rules of binary search tree insertion and ensuring the color of nodes based on the properties of red black trees.']}], 'duration': 143.746, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qA02XWRTBdw/pics/qA02XWRTBdw289.jpg', 'highlights': ['The red black tree is a self-balancing binary search tree with specific properties.', 'The chapter explains the rules for inserting data in red black trees, including creating a new black root node when the tree is empty and following binary search tree insertion rules.', 'The chapter demonstrates the insertion of data (10 and 18) in the red black tree, following the rules of binary search tree insertion and ensuring the color of nodes based on the properties of red black trees.']}, {'end': 519.506, 'segs': [{'end': 230.389, 'src': 'embed', 'start': 170.337, 'weight': 5, 'content': [{'end': 182.031, 'text': 'so you can say 18 would be to the right of this one and color is what red right now.', 'start': 170.337, 'duration': 11.694}, {'end': 183.794, 'text': 'now you need to check out.', 'start': 182.031, 'duration': 1.763}, {'end': 185.016, 'text': 'see now.', 'start': 183.794, 'duration': 1.222}, {'end': 190.624, 'text': 'after this you need to check out if parent of the new node, this is the new node we have created.', 'start': 185.016, 'duration': 5.608}, {'end': 192.868, 'text': 'right. check the parent of this node.', 'start': 190.624, 'duration': 2.244}, {'end': 199.551, 'text': 'if the parent is black, then done, you are done with the insertion exit.', 'start': 194.167, 'duration': 5.384}, {'end': 202.634, 'text': 'here the parent is black means done.', 'start': 199.551, 'duration': 3.083}, {'end': 204.695, 'text': 'this is now red black pre.', 'start': 202.634, 'duration': 2.061}, {'end': 206.617, 'text': 'as you can see, root is black.', 'start': 204.695, 'duration': 1.922}, {'end': 212.361, 'text': 'no, two adjacent red nodes are there and number of black nodes in each path from here to here, one black node.', 'start': 206.617, 'duration': 5.744}, {'end': 213.862, 'text': 'from here to here, also one black node.', 'start': 212.361, 'duration': 1.501}, {'end': 215.483, 'text': 'so this is red black pre.', 'start': 213.862, 'duration': 1.621}, {'end': 216.744, 'text': 'now we are done now.', 'start': 215.483, 'duration': 1.261}, {'end': 219.386, 'text': 'see, third is 7.', 'start': 216.744, 'duration': 2.642}, {'end': 222.306, 'text': 'where you are supposed to insert 7, tree is not empty.', 'start': 219.386, 'duration': 2.92}, {'end': 227.268, 'text': 'so always you are going to create a new node in red color.', 'start': 222.306, 'duration': 4.962}, {'end': 230.389, 'text': 'right now 7 is less than 10.', 'start': 227.268, 'duration': 3.121}], 'summary': 'Inserting 7 into a red-black tree with specific color and node conditions.', 'duration': 60.052, 'max_score': 170.337, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qA02XWRTBdw/pics/qA02XWRTBdw170337.jpg'}, {'end': 316.605, 'src': 'embed', 'start': 261.565, 'weight': 2, 'content': [{'end': 264.468, 'text': 'new node would be created with color red.', 'start': 261.565, 'duration': 2.903}, {'end': 271.199, 'text': 'because tree is not empty, right, always we are going to create a new node in color red.', 'start': 264.468, 'duration': 6.731}, {'end': 275.123, 'text': 'if tree is empty, then only color would be black right now.', 'start': 271.199, 'duration': 3.924}, {'end': 278.227, 'text': 'see, this is what also red color.', 'start': 275.123, 'duration': 3.104}, {'end': 282.031, 'text': 'but this is now violating the property, this one.', 'start': 278.227, 'duration': 3.804}, {'end': 285.235, 'text': 'here we have red red parent, child relationship.', 'start': 282.031, 'duration': 3.204}, {'end': 287.479, 'text': 'parent is also red.', 'start': 286.479, 'duration': 1}, {'end': 288.46, 'text': 'child is also red.', 'start': 287.479, 'duration': 0.981}, {'end': 290.62, 'text': 'that is not possible in red black tree.', 'start': 288.46, 'duration': 2.16}, {'end': 292.741, 'text': 'now it is violating the property.', 'start': 290.62, 'duration': 2.121}, {'end': 297.022, 'text': 'so you have to do something to make it a red black tree.', 'start': 292.741, 'duration': 4.281}, {'end': 298.122, 'text': 'now what you will do.', 'start': 297.022, 'duration': 1.1}, {'end': 300.783, 'text': 'the rule is what see now.', 'start': 298.122, 'duration': 2.661}, {'end': 301.443, 'text': 'fourth, check.', 'start': 300.783, 'duration': 0.66}, {'end': 307.124, 'text': 'the fourth rule if the parent of new node, new node, is 15, check the parent parent is red.', 'start': 301.443, 'duration': 5.681}, {'end': 316.605, 'text': 'if the parent is red, then check the color of parents sibling of new node.', 'start': 307.124, 'duration': 9.481}], 'summary': 'Red black tree nodes must adhere to color and relationship rules to maintain structure.', 'duration': 55.04, 'max_score': 261.565, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qA02XWRTBdw/pics/qA02XWRTBdw261565.jpg'}, {'end': 379.709, 'src': 'embed', 'start': 346.196, 'weight': 0, 'content': [{'end': 349.058, 'text': 'now check the color of parent sibling of new node.', 'start': 346.196, 'duration': 2.862}, {'end': 353.761, 'text': 'and if color is black but color is not black, color is red here.', 'start': 349.058, 'duration': 4.703}, {'end': 354.782, 'text': 'so now this rule.', 'start': 353.761, 'duration': 1.021}, {'end': 357.504, 'text': 'you need to take care in this situation.', 'start': 354.782, 'duration': 2.722}, {'end': 360.006, 'text': 'if color is red, obviously color is red.', 'start': 357.504, 'duration': 2.502}, {'end': 363.008, 'text': 'then recolor right now.', 'start': 360.006, 'duration': 3.002}, {'end': 370.786, 'text': 'recolor means you will do Recoloring of both the parent and parents sibling.', 'start': 363.008, 'duration': 7.778}, {'end': 374.327, 'text': 'So this would be now black.', 'start': 371.566, 'duration': 2.761}, {'end': 379.709, 'text': 'Right? This is 18 and this is now black.', 'start': 376.068, 'duration': 3.641}], 'summary': "When the parent sibling's color is black, and the new node's color is not black, it's changed to red. if the color is red, recoloring is done to change both the parent and parents' sibling to black.", 'duration': 33.513, 'max_score': 346.196, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qA02XWRTBdw/pics/qA02XWRTBdw346196.jpg'}, {'end': 486.766, 'src': 'embed', 'start': 459.489, 'weight': 1, 'content': [{'end': 470.897, 'text': 'now where you will insert 16 greater than 10, less than 18, but greater than this 15, and always new node would be created and colored as red right.', 'start': 459.489, 'duration': 11.408}, {'end': 472.278, 'text': 'so this is red now.', 'start': 470.897, 'duration': 1.381}, {'end': 474.26, 'text': 'here is what red red conflict.', 'start': 472.278, 'duration': 1.982}, {'end': 475.34, 'text': 'right parent is also red.', 'start': 474.26, 'duration': 1.08}, {'end': 476.982, 'text': 'child is also red now, here.', 'start': 475.34, 'duration': 1.642}, {'end': 482.945, 'text': 'if red red conflict is there, then then check the color of parents sibling.', 'start': 477.742, 'duration': 5.203}, {'end': 485.326, 'text': 'see, this is the newly created node.', 'start': 482.945, 'duration': 2.381}, {'end': 486.766, 'text': 'parents sibling.', 'start': 485.326, 'duration': 1.44}], 'summary': "Insert nodes with specific values and colors, handle red-red conflicts by checking parent's sibling's color.", 'duration': 27.277, 'max_score': 459.489, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qA02XWRTBdw/pics/qA02XWRTBdw459489.jpg'}], 'start': 144.035, 'title': 'Red black tree operations', 'summary': 'Covers red black tree insertion, violation, and recoloring, emphasizing the process of maintaining tree properties, such as black node count and handling red-red conflicts.', 'chapters': [{'end': 261.565, 'start': 144.035, 'title': 'Red black tree insertion', 'summary': 'Explains the process of inserting nodes into a red black tree, ensuring that the parent of a new node is black and maintaining the properties of a red black tree with two adjacent red nodes and the number of black nodes in each path.', 'duration': 117.53, 'highlights': ['Creating a new node in a red color for a non-empty tree, with the root always being black in a red black tree.', 'Ensuring the parent of the new node is black, indicating the completion of the insertion process.', 'Maintaining the properties of a red black tree with two adjacent red nodes and the number of black nodes in each path.']}, {'end': 316.605, 'start': 261.565, 'title': 'Red black tree violation', 'summary': 'Discusses the violation of the red black tree property due to the presence of red-red parent-child relationships and provides a rule for checking and correcting the violation.', 'duration': 55.04, 'highlights': ['The violation of having red-red parent-child relationships is discussed, which is not possible in a red black tree and requires corrective action.', "The rule for checking the violation involves examining the color of the parent's sibling of the new node when the parent of the new node is red."]}, {'end': 519.506, 'start': 316.605, 'title': 'Red black tree: insertion and recoloring', 'summary': 'Explains the process of inserting nodes into a red black tree, highlighting the steps of recoloring and rotation to maintain the properties of a red black tree, with emphasis on the number of black nodes in every path and handling red red conflicts.', 'duration': 202.901, 'highlights': ["The process involves recoloring of both the parent and parent's sibling when encountering a red red conflict, resulting in the adjustment of the colors of the nodes (18, 7, and 18's sibling) to black, ensuring the properties of a red black tree.", 'The chapter emphasizes the importance of maintaining the properties of a red black tree, including the color of nodes, the number of black nodes in every path, and the handling of red red conflicts to ensure the tree remains balanced and efficient.', "The explanation covers the specific steps and considerations for handling red red conflicts, including checking the color of the parent's sibling and performing suitable rotations and recoloring when necessary to maintain the structure of the red black tree.", 'The process of inserting nodes into a red black tree is detailed, highlighting the creation of new nodes and the necessary recoloring and rotation steps to ensure the properties of a red black tree are maintained, promoting efficient and balanced tree structures.']}], 'duration': 375.471, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qA02XWRTBdw/pics/qA02XWRTBdw144035.jpg', 'highlights': ["The process involves recoloring of both the parent and parent's sibling when encountering a red red conflict, resulting in the adjustment of the colors of the nodes (18, 7, and 18's sibling) to black, ensuring the properties of a red black tree.", "The explanation covers the specific steps and considerations for handling red red conflicts, including checking the color of the parent's sibling and performing suitable rotations and recoloring when necessary to maintain the structure of the red black tree.", 'The process of inserting nodes into a red black tree is detailed, highlighting the creation of new nodes and the necessary recoloring and rotation steps to ensure the properties of a red black tree are maintained, promoting efficient and balanced tree structures.', 'The chapter emphasizes the importance of maintaining the properties of a red black tree, including the color of nodes, the number of black nodes in every path, and the handling of red red conflicts to ensure the tree remains balanced and efficient.', 'The violation of having red-red parent-child relationships is discussed, which is not possible in a red black tree and requires corrective action.', 'Ensuring the parent of the new node is black, indicating the completion of the insertion process.', 'Creating a new node in a red color for a non-empty tree, with the root always being black in a red black tree.', "The rule for checking the violation involves examining the color of the parent's sibling of the new node when the parent of the new node is red.", 'Maintaining the properties of a red black tree with two adjacent red nodes and the number of black nodes in each path.']}, {'end': 696.752, 'segs': [{'end': 628.955, 'src': 'embed', 'start': 601.807, 'weight': 0, 'content': [{'end': 605.327, 'text': 'obviously we are getting some problem right red red conflict.', 'start': 601.807, 'duration': 3.52}, {'end': 609.461, 'text': 'now in this case you do what right rotations Right.', 'start': 605.327, 'duration': 4.134}, {'end': 614.004, 'text': 'Why you are doing right rotation? Why you are doing left rotation? That thing we have discussed in the avial tree.', 'start': 609.962, 'duration': 4.042}, {'end': 620.869, 'text': 'So now when you do right rotation, then always from here, from these three elements, the median element would be the root.', 'start': 614.565, 'duration': 6.304}, {'end': 623.992, 'text': 'The median element would be from 15, 16, 18.', 'start': 621.009, 'duration': 2.983}, {'end': 625.713, 'text': '16 would be the median element.', 'start': 623.992, 'duration': 1.721}, {'end': 627.474, 'text': 'Right That is shortcut.', 'start': 626.253, 'duration': 1.221}, {'end': 628.955, 'text': 'Right To do the rotation.', 'start': 628.015, 'duration': 0.94}], 'summary': 'Discussing right rotation in avl tree with median element from 15, 16, 18.', 'duration': 27.148, 'max_score': 601.807, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qA02XWRTBdw/pics/qA02XWRTBdw601807.jpg'}, {'end': 696.752, 'src': 'heatmap', 'start': 630.416, 'weight': 1, 'content': [{'end': 632.278, 'text': 'So now the tree would be something like this.', 'start': 630.416, 'duration': 1.862}, {'end': 638.18, 'text': 'so tree would be something like this see, here you can say rotation and recolor.', 'start': 632.958, 'duration': 5.222}, {'end': 643.282, 'text': 'so now, after rotation, 16 would be the root to the left of the 16.', 'start': 638.18, 'duration': 5.102}, {'end': 643.962, 'text': 'we have 15.', 'start': 643.282, 'duration': 0.68}, {'end': 647.143, 'text': 'to the right of the 16 we will have 18 and recolor.', 'start': 643.962, 'duration': 3.181}, {'end': 650.625, 'text': 'recolor means this 15 would would be as it is.', 'start': 647.143, 'duration': 3.482}, {'end': 653.506, 'text': 'this would be red and we are going to recolor this and this.', 'start': 650.625, 'duration': 2.881}, {'end': 654.766, 'text': 'so this is what here.', 'start': 653.506, 'duration': 1.26}, {'end': 655.407, 'text': 'this is red.', 'start': 654.766, 'duration': 0.641}, {'end': 657.227, 'text': 'so this would become black.', 'start': 655.407, 'duration': 1.82}, {'end': 658.148, 'text': 'this is what black.', 'start': 657.227, 'duration': 0.921}, {'end': 660.709, 'text': 'so this would become red.', 'start': 658.148, 'duration': 2.561}, {'end': 663.212, 'text': 'so now this is red black tree.', 'start': 660.709, 'duration': 2.503}, {'end': 664.393, 'text': 'after insertion of 16.', 'start': 663.212, 'duration': 1.181}, {'end': 666.514, 'text': 'you can check out all the three property.', 'start': 664.393, 'duration': 2.121}, {'end': 668.355, 'text': 'these are satisfied in this tree.', 'start': 666.514, 'duration': 1.841}, {'end': 672.297, 'text': 'right now we will insert 30 in this tree.', 'start': 668.355, 'duration': 3.942}, {'end': 674.038, 'text': 'now where to insert this 30.', 'start': 672.297, 'duration': 1.741}, {'end': 677.2, 'text': '30 is greater than 10, greater than 16, greater than 18.', 'start': 674.038, 'duration': 3.162}, {'end': 679.929, 'text': 'so here you will insert 30..', 'start': 677.2, 'duration': 2.729}, {'end': 682.753, 'text': 'And obviously tree is not empty so this would be always red.', 'start': 679.929, 'duration': 2.824}, {'end': 683.955, 'text': 'Now check up.', 'start': 683.254, 'duration': 0.701}, {'end': 687.099, 'text': 'Check the parent of this newly created node that is red.', 'start': 684.135, 'duration': 2.964}, {'end': 690.984, 'text': 'If this is red it means you have red red conflict.', 'start': 687.68, 'duration': 3.304}, {'end': 694.609, 'text': 'Right? Now what you will do? Check out the parent.', 'start': 691.325, 'duration': 3.284}, {'end': 696.752, 'text': 'this is the newly created node.', 'start': 695.51, 'duration': 1.242}], 'summary': 'Explanation of red-black tree insertion and recoloring with example nodes and properties.', 'duration': 49.609, 'max_score': 630.416, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qA02XWRTBdw/pics/qA02XWRTBdw630416.jpg'}], 'start': 519.506, 'title': 'Red-black tree insertion', 'summary': 'Explains the process of inserting nodes in a red-black tree, involving left and right rotations, and recoloring to maintain the red-black properties, ensuring a balanced tree with no red-red conflicts.', 'chapters': [{'end': 696.752, 'start': 519.506, 'title': 'Red-black tree insertion', 'summary': 'Explains the process of inserting nodes in a red-black tree, involving left and right rotations, and recoloring to maintain the red-black properties, ensuring a balanced tree with no red-red conflicts.', 'duration': 177.246, 'highlights': ['The process of left and right rotations is crucial in maintaining the balance of the red-black tree and avoiding red-red conflicts. The chapter emphasizes the importance of left and right rotations in resolving red-red conflicts and maintaining a balanced red-black tree.', 'The concept of recoloring is essential after rotations to ensure the red-black properties are satisfied. Recoloring is highlighted as a crucial step in maintaining the red-black properties after rotations, ensuring a balanced red-black tree without red-red conflicts.', 'The insertion of nodes in a red-black tree involves considering the properties of the existing tree and ensuring no red-red conflicts occur. The chapter stresses the significance of considering existing tree properties and avoiding red-red conflicts during the insertion of nodes in a red-black tree.']}], 'duration': 177.246, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qA02XWRTBdw/pics/qA02XWRTBdw519506.jpg', 'highlights': ['The process of left and right rotations is crucial in maintaining the balance of the red-black tree and avoiding red-red conflicts.', 'The concept of recoloring is essential after rotations to ensure the red-black properties are satisfied.', 'The insertion of nodes in a red-black tree involves considering the properties of the existing tree and ensuring no red-red conflicts occur.']}, {'end': 981.979, 'segs': [{'end': 839.521, 'src': 'embed', 'start': 696.752, 'weight': 0, 'content': [{'end': 699.655, 'text': 'so check out the parents sibling.', 'start': 696.752, 'duration': 2.903}, {'end': 700.656, 'text': 'parent is this one?', 'start': 699.655, 'duration': 1.001}, {'end': 706.924, 'text': 'parents sibling is this one, and the color of parents sibling is red, right.', 'start': 700.656, 'duration': 6.268}, {'end': 709.287, 'text': 'so simply do recolor.', 'start': 706.924, 'duration': 2.363}, {'end': 711.369, 'text': 'no rotations would be required in this case.', 'start': 709.287, 'duration': 2.082}, {'end': 717.911, 'text': 'if this is black or null, then rotation would be required and recoloring would be required in this case.', 'start': 712.35, 'duration': 5.561}, {'end': 722.873, 'text': 'if the parents sibling is red, then simply recolor it right.', 'start': 717.911, 'duration': 4.962}, {'end': 732.135, 'text': 'if parents sibling is red, then recolor means recolor means this and this parents and parents sibling would be recolored.', 'start': 722.873, 'duration': 9.262}, {'end': 735.096, 'text': 'if the color is red, do it black.', 'start': 732.135, 'duration': 2.961}, {'end': 742.484, 'text': 'so now this is something like this, As well as see recolor and also check.', 'start': 735.096, 'duration': 7.388}, {'end': 745.627, 'text': 'If parent of new node.', 'start': 743.205, 'duration': 2.422}, {'end': 746.827, 'text': 'See new node is this one.', 'start': 745.647, 'duration': 1.18}, {'end': 748.829, 'text': 'And parent is this one.', 'start': 747.488, 'duration': 1.341}, {'end': 751.03, 'text': "And parent's parent is 16.", 'start': 748.889, 'duration': 2.141}, {'end': 754.293, 'text': 'Right If this is not root node.', 'start': 751.03, 'duration': 3.263}, {'end': 756.694, 'text': 'Here 16 is not root node.', 'start': 754.733, 'duration': 1.961}, {'end': 758.435, 'text': 'Then recolor it.', 'start': 757.235, 'duration': 1.2}, {'end': 761.297, 'text': 'So you are going to recolor this as well.', 'start': 758.516, 'duration': 2.781}, {'end': 762.458, 'text': 'So this is black.', 'start': 761.358, 'duration': 1.1}, {'end': 764.82, 'text': 'So now this would become red.', 'start': 762.478, 'duration': 2.342}, {'end': 769.988, 'text': 'right and then recheck now.', 'start': 767.728, 'duration': 2.26}, {'end': 771.549, 'text': 'recheck means this is red.', 'start': 769.988, 'duration': 1.561}, {'end': 774.169, 'text': 'now again, recheck it with its parent.', 'start': 771.549, 'duration': 2.62}, {'end': 775.689, 'text': 'parent is black.', 'start': 774.169, 'duration': 1.52}, {'end': 779.19, 'text': 'so no red red conflict is there now.', 'start': 775.689, 'duration': 3.501}, {'end': 782.251, 'text': 'this is what a red black tree right.', 'start': 779.19, 'duration': 3.061}, {'end': 785.351, 'text': 'you can check out these properties on this tree.', 'start': 782.251, 'duration': 3.1}, {'end': 796.829, 'text': 'now, after 30, we are going to insert 25 now, where to insert 25 greater than 10, greater than 16 greater than 18, but less than 30..', 'start': 785.351, 'duration': 11.478}, {'end': 807.612, 'text': 'so to the left of 30 you will insert 25 and that would be obviously in red color because you are inserting new node that would be always in the red color if that is not a root node,', 'start': 796.829, 'duration': 10.783}, {'end': 809.112, 'text': 'if tree is not empty.', 'start': 807.612, 'duration': 1.5}, {'end': 811.713, 'text': 'now here again, check red red conflict.', 'start': 809.112, 'duration': 2.601}, {'end': 813.893, 'text': 'we have parent of newly created node.', 'start': 811.713, 'duration': 2.18}, {'end': 815.514, 'text': 'is red right?', 'start': 813.893, 'duration': 1.621}, {'end': 818.414, 'text': 'then check the color of parents.', 'start': 815.514, 'duration': 2.9}, {'end': 820.635, 'text': 'sibling parents, sibling parent.', 'start': 818.414, 'duration': 2.221}, {'end': 829.356, 'text': 'is this one parent sibling is it must be here the second child of this one parent of this parent.', 'start': 820.635, 'duration': 8.721}, {'end': 830.797, 'text': 'but there is no child.', 'start': 829.356, 'duration': 1.441}, {'end': 832.938, 'text': 'so it means it is what black or null.', 'start': 830.797, 'duration': 2.141}, {'end': 834.839, 'text': 'so here it is null.', 'start': 832.938, 'duration': 1.901}, {'end': 837.12, 'text': 'then you need to do some rotations and recolor.', 'start': 834.839, 'duration': 2.281}, {'end': 839.521, 'text': 'now which rotations you require.', 'start': 837.12, 'duration': 2.401}], 'summary': 'Explaining red-black tree insertion and conflict resolution', 'duration': 142.769, 'max_score': 696.752, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qA02XWRTBdw/pics/qA02XWRTBdw696752.jpg'}, {'end': 981.979, 'src': 'heatmap', 'start': 941.746, 'weight': 2, 'content': [{'end': 948.369, 'text': 'right now, recoloring of these two you will do.', 'start': 941.746, 'duration': 6.623}, {'end': 952.39, 'text': 'the 30 would become, would be as it is, that is red and now 25 is red.', 'start': 948.369, 'duration': 4.021}, {'end': 958.31, 'text': 'so it would become now black and 18 is black.', 'start': 952.39, 'duration': 5.92}, {'end': 960.2, 'text': 'so it would become now red.', 'start': 958.31, 'duration': 1.89}, {'end': 964.796, 'text': "and that's it.", 'start': 963.956, 'duration': 0.84}, {'end': 966.256, 'text': 'now you can check out.', 'start': 964.796, 'duration': 1.46}, {'end': 969.457, 'text': 'this is the red black tree and this is satisfying all the three conditions.', 'start': 966.256, 'duration': 3.201}, {'end': 973.218, 'text': 'right now, after this 25, we will insert 40.', 'start': 969.457, 'duration': 3.761}, {'end': 974.958, 'text': 'where to insert 40?', 'start': 973.218, 'duration': 1.74}, {'end': 981.979, 'text': 'it would be, i guess, here to the right of this 30, because it is greater than 10, greater than 16, 25, greater than 30.', 'start': 974.958, 'duration': 7.021}], 'summary': 'Recoloring of nodes in red-black tree to satisfy conditions, then insert 40 to the right of 30.', 'duration': 29.589, 'max_score': 941.746, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qA02XWRTBdw/pics/qA02XWRTBdw941746.jpg'}], 'start': 696.752, 'title': 'Red-black tree operations', 'summary': 'Explains red-black tree algorithms including recoloring, rotating nodes, and insertion of nodes, with a specific example of inserting nodes 25 and 40.', 'chapters': [{'end': 785.351, 'start': 696.752, 'title': 'Red black tree algorithm', 'summary': "Explains the process of recoloring and rotating nodes in a red-black tree to maintain the properties of the tree, addressing cases where recoloring or rotation is required based on the color of the parent's sibling and the new node's parent.", 'duration': 88.599, 'highlights': ['The process involves recoloring the parent and its sibling if the sibling is red, changing them from red to black to maintain the red-black tree properties.', "If the parent's sibling is black or null, rotation is required, in addition to recoloring, to maintain the red-black tree properties.", 'The chapter emphasizes the importance of rechecking the colors of nodes after recoloring or rotation to ensure there are no red-red conflicts, thus maintaining the structure of a red-black tree.']}, {'end': 981.979, 'start': 785.351, 'title': 'Red-black tree insertion', 'summary': "Explains the process of inserting nodes in a red-black tree, involving rotations and recoloring to maintain the tree's properties, with a specific example of inserting nodes 25 and 40.", 'duration': 196.628, 'highlights': ["The process involves checking for red-red conflicts and performing rotations and recoloring to maintain the red-black tree's properties.", "The specific example demonstrates the insertion of nodes 25 and 40, with detailed steps for rotations and recoloring to maintain the red-black tree's properties.", "The example involves inserting node 25 to the left of its parent, triggering right and left rotations followed by recoloring to maintain the red-black tree's properties.", "The insertion of node 40 is also illustrated, showing the process of determining its position and ensuring the red-black tree's properties are maintained."]}], 'duration': 285.227, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qA02XWRTBdw/pics/qA02XWRTBdw696752.jpg', 'highlights': ["The specific example demonstrates the insertion of nodes 25 and 40, with detailed steps for rotations and recoloring to maintain the red-black tree's properties.", "The example involves inserting node 25 to the left of its parent, triggering right and left rotations followed by recoloring to maintain the red-black tree's properties.", "The insertion of node 40 is also illustrated, showing the process of determining its position and ensuring the red-black tree's properties are maintained.", "The process involves checking for red-red conflicts and performing rotations and recoloring to maintain the red-black tree's properties.", 'The process involves recoloring the parent and its sibling if the sibling is red, changing them from red to black to maintain the red-black tree properties.', "If the parent's sibling is black or null, rotation is required, in addition to recoloring, to maintain the red-black tree properties.", 'The chapter emphasizes the importance of rechecking the colors of nodes after recoloring or rotation to ensure there are no red-red conflicts, thus maintaining the structure of a red-black tree.']}, {'end': 1308.535, 'segs': [{'end': 1038.188, 'src': 'embed', 'start': 981.979, 'weight': 0, 'content': [{'end': 989.661, 'text': 'so here, and it would be always in the red color when we will insert a new node, that would always be first of all in red color.', 'start': 981.979, 'duration': 7.682}, {'end': 991.501, 'text': 'now check the if there is any conflict.', 'start': 989.661, 'duration': 1.84}, {'end': 994.158, 'text': 'yes, here we have red red conflict.', 'start': 991.501, 'duration': 2.657}, {'end': 996.479, 'text': 'parents of the new node is in red.', 'start': 994.158, 'duration': 2.321}, {'end': 1000.041, 'text': 'so now we are going to check the parents sibling parents.', 'start': 996.479, 'duration': 3.562}, {'end': 1002.663, 'text': 'sibling is also in red.', 'start': 1000.041, 'duration': 2.622}, {'end': 1005.044, 'text': 'so now no rotation would be required.', 'start': 1002.663, 'duration': 2.381}, {'end': 1007.665, 'text': 'just do recoloring right.', 'start': 1005.044, 'duration': 2.621}, {'end': 1012.166, 'text': 'recoloring means parent of new node is red.', 'start': 1007.665, 'duration': 4.501}, {'end': 1013.067, 'text': 'this is also red.', 'start': 1012.166, 'duration': 0.901}, {'end': 1016.911, 'text': 'so you will recolor both these parents and sibling of the parent.', 'start': 1013.067, 'duration': 3.844}, {'end': 1027.063, 'text': 'so now this would become in black color and this is also in black color right now.', 'start': 1016.911, 'duration': 10.152}, {'end': 1029.884, 'text': 'next is see, this is not yet done.', 'start': 1027.063, 'duration': 2.821}, {'end': 1034.046, 'text': 'now check the parents parent that is 25 parent.', 'start': 1029.884, 'duration': 4.162}, {'end': 1036.207, 'text': 'is this one parents parent is 25?', 'start': 1034.046, 'duration': 2.161}, {'end': 1038.188, 'text': 'is this root node?', 'start': 1036.207, 'duration': 1.981}], 'summary': 'Inserting new node, resolving red-red conflict, performing recoloring.', 'duration': 56.209, 'max_score': 981.979, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qA02XWRTBdw/pics/qA02XWRTBdw981979.jpg'}, {'end': 1309.995, 'src': 'embed', 'start': 1281.454, 'weight': 2, 'content': [{'end': 1284.096, 'text': '40 is in red, so it would become in black.', 'start': 1281.454, 'duration': 2.642}, {'end': 1289.247, 'text': '30 would be to the left of 40 and recoloring of 30 means 30 is in black.', 'start': 1285.445, 'duration': 3.802}, {'end': 1295.369, 'text': 'so 30 would become in red and 60 would be as it is in the red color.', 'start': 1289.247, 'duration': 6.122}, {'end': 1298.15, 'text': 'so this is now a red black tree after inserting 60.', 'start': 1295.369, 'duration': 2.781}, {'end': 1298.751, 'text': 'you can check out.', 'start': 1298.15, 'duration': 0.601}, {'end': 1302.672, 'text': 'this is following these three property right now insert 2.', 'start': 1298.751, 'duration': 3.921}, {'end': 1306.074, 'text': '2 is less than 16, less than 10, less than 7.', 'start': 1302.672, 'duration': 3.402}, {'end': 1308.535, 'text': 'so insert 2 here.', 'start': 1306.074, 'duration': 2.461}, {'end': 1309.995, 'text': 'now check the parent of new node.', 'start': 1308.535, 'duration': 1.46}], 'summary': 'Inserting 60 creates a red-black tree. inserting 2 follows property rules.', 'duration': 28.541, 'max_score': 1281.454, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qA02XWRTBdw/pics/qA02XWRTBdw1281454.jpg'}], 'start': 981.979, 'title': 'Red-black tree operations', 'summary': 'Discusses recoloring in a red-black tree, resolving red-red conflicts, and inserting nodes while maintaining red-black properties, with examples of inserting nodes 60 and 2.', 'chapters': [{'end': 1090.106, 'start': 981.979, 'title': 'Red-black tree recoloring', 'summary': 'Discusses the process of recoloring in a red-black tree data structure, highlighting the identification and resolution of red-red conflicts through recoloring and rotation.', 'duration': 108.127, 'highlights': ['The process of recoloring involves changing the color of the parent and its sibling to resolve red-red conflicts, ensuring the new node and its parents are recolored to black if they are not root nodes.', "Identification of red-red conflicts is crucial in the recoloring process, requiring checking the colors of the new node's parent, sibling, and the parent's parent to determine the need for recoloring and rotations."]}, {'end': 1308.535, 'start': 1090.106, 'title': 'Red black tree insertion', 'summary': 'Explains the process of inserting nodes into a red black tree, including left rotation and recoloring to maintain the red black properties, and provides an example of inserting nodes 60 and 2 into the tree.', 'duration': 218.429, 'highlights': ['The process of left rotation is explained, where the median element becomes the root, and the left and right elements are adjusted accordingly. Left rotation is performed, with 16 becoming the root, 10 on the left, and 25 on the right, demonstrating the adjustment of elements during rotation.', 'The concept of recoloring in a red black tree is described, with specific instructions on how to recolor nodes to maintain the properties of the tree. The explanation includes the recoloring of nodes 16 and 10 after the left rotation, ensuring that the properties of the red black tree are maintained.', "An example of inserting node 60 into the red black tree is provided, demonstrating the process of comparing values and inserting the node while maintaining the tree's properties. The step-by-step insertion of node 60 is described, highlighting the comparison of values and the maintenance of red black tree properties during the insertion process.", "The process of handling a red red conflict and the subsequent left rotation and recoloring are explained, emphasizing the resolution of conflicts and maintenance of the tree's properties. The explanation details the identification of a red red conflict, the required left rotation, and the subsequent recoloring to resolve the conflict and maintain the properties of the red black tree."]}], 'duration': 326.556, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qA02XWRTBdw/pics/qA02XWRTBdw981979.jpg', 'highlights': ['The process of recoloring involves changing the color of the parent and its sibling to resolve red-red conflicts, ensuring the new node and its parents are recolored to black if they are not root nodes.', "Identification of red-red conflicts is crucial in the recoloring process, requiring checking the colors of the new node's parent, sibling, and the parent's parent to determine the need for recoloring and rotations.", "An example of inserting node 60 into the red black tree is provided, demonstrating the process of comparing values and inserting the node while maintaining the tree's properties.", "The process of handling a red red conflict and the subsequent left rotation and recoloring are explained, emphasizing the resolution of conflicts and maintenance of the tree's properties.", 'The concept of recoloring in a red black tree is described, with specific instructions on how to recolor nodes to maintain the properties of the tree.']}, {'end': 1655.523, 'segs': [{'end': 1461.407, 'src': 'embed', 'start': 1431.184, 'weight': 0, 'content': [{'end': 1433.925, 'text': 'so to the right of 60 you will insert 70.', 'start': 1431.184, 'duration': 2.741}, {'end': 1436.717, 'text': 'right now.', 'start': 1433.925, 'duration': 2.792}, {'end': 1439.959, 'text': 'check out the parent of newly created node that is red.', 'start': 1436.717, 'duration': 3.242}, {'end': 1441.901, 'text': 'so here we have red red conflict.', 'start': 1439.959, 'duration': 1.942}, {'end': 1443.062, 'text': 'now how to resolve this?', 'start': 1441.901, 'duration': 1.161}, {'end': 1445.584, 'text': 'check out the parent sibling that is red.', 'start': 1443.062, 'duration': 2.522}, {'end': 1447.605, 'text': 'so simply do recoloring.', 'start': 1445.584, 'duration': 2.021}, {'end': 1453.971, 'text': 'so recoloring means you will do recolor its parent, parent of newly created node, as well as the sibling.', 'start': 1447.605, 'duration': 6.366}, {'end': 1455.572, 'text': 'so these are red in red.', 'start': 1453.971, 'duration': 1.601}, {'end': 1461.407, 'text': 'so do it in black color plus.', 'start': 1455.572, 'duration': 5.835}], 'summary': "To resolve red-red conflict, recolor parent, new node's parent, and sibling to black.", 'duration': 30.223, 'max_score': 1431.184, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qA02XWRTBdw/pics/qA02XWRTBdw1431184.jpg'}, {'end': 1557.32, 'src': 'embed', 'start': 1508.952, 'weight': 2, 'content': [{'end': 1513.737, 'text': 'So now simply recolor these two means this is red so it would become black.', 'start': 1508.952, 'duration': 4.785}, {'end': 1517.521, 'text': 'This is also red so it would become black.', 'start': 1514.858, 'duration': 2.663}, {'end': 1523.108, 'text': "And also check now the parent's parent is 16 right.", 'start': 1518.402, 'duration': 4.706}, {'end': 1527.828, 'text': 'parent of this one is this one and parents parent is 16.', 'start': 1525.287, 'duration': 2.541}, {'end': 1532.969, 'text': 'this is now root node, so you are not going to recolor it, just leave it as it is.', 'start': 1527.828, 'duration': 5.141}, {'end': 1537.591, 'text': 'so this is the final red black tree after inserting all the data right.', 'start': 1532.969, 'duration': 4.622}, {'end': 1540.411, 'text': 'so i guess i have discussed all the rules here.', 'start': 1537.591, 'duration': 2.82}, {'end': 1541.772, 'text': 'simple rules are there.', 'start': 1540.411, 'duration': 1.361}, {'end': 1546.213, 'text': 'if tree is empty, just create a node and color it in black.', 'start': 1541.772, 'duration': 4.441}, {'end': 1549.634, 'text': 'if tree is not empty, then create a node in red color.', 'start': 1546.213, 'duration': 3.421}, {'end': 1551.815, 'text': 'check the parent of the newly created node.', 'start': 1549.634, 'duration': 2.181}, {'end': 1557.32, 'text': 'if the parent is black, then exit means you are done with the insertion.', 'start': 1551.815, 'duration': 5.505}], 'summary': 'Demonstration of recoloring in red-black tree, following simple insertion rules.', 'duration': 48.368, 'max_score': 1508.952, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qA02XWRTBdw/pics/qA02XWRTBdw1508952.jpg'}, {'end': 1644.894, 'src': 'embed', 'start': 1615.634, 'weight': 4, 'content': [{'end': 1617.035, 'text': 'Simple rules are there.', 'start': 1615.634, 'duration': 1.401}, {'end': 1618.937, 'text': 'So I hope you got all the rules.', 'start': 1617.356, 'duration': 1.581}, {'end': 1630.244, 'text': 'A question for you guys is, is it possible to have all the black nodes in a red black tree? You can tell me the answer in the comment box.', 'start': 1619.597, 'duration': 10.647}, {'end': 1638.61, 'text': 'Right And see one more important point about this is what every red black tree is a binary search tree.', 'start': 1630.524, 'duration': 8.086}, {'end': 1644.894, 'text': 'But every binary search tree need not to be a red black tree.', 'start': 1639.11, 'duration': 5.784}], 'summary': 'Red black tree is a binary search tree, not vice versa.', 'duration': 29.26, 'max_score': 1615.634, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qA02XWRTBdw/pics/qA02XWRTBdw1615634.jpg'}], 'start': 1308.535, 'title': 'Red black tree insertion', 'summary': 'Explains the process and rules for inserting nodes into a red black tree, resolving red-red conflicts through rotations and recoloring, and discusses the possibility of having all black nodes in a red black tree.', 'chapters': [{'end': 1508.551, 'start': 1308.535, 'title': 'Red black tree insertion', 'summary': 'Explains the process of inserting nodes into a red black tree, resolving red-red conflicts through rotations and recoloring, and ensures adherence to all red-black tree properties.', 'duration': 200.016, 'highlights': ['After inserting 70, resolve red-red conflict by recoloring the parent, its sibling, and the grandparent, ensuring adherence to red-black tree properties. After inserting 70, resolve red-red conflict by recoloring the parent, its sibling, and the grandparent. This ensures adherence to red-black tree properties.', 'Resolve red-red conflict by recoloring and rechecking the tree to ensure adherence to red-black tree properties. Resolve red-red conflict by recoloring and rechecking the tree to ensure adherence to red-black tree properties.', 'Insert 1 to the left of 2, resulting in a red-red conflict resolved through rotation and recoloring. Insert 1 to the left of 2, resulting in a red-red conflict resolved through rotation and recoloring.']}, {'end': 1655.523, 'start': 1508.952, 'title': 'Red black tree insertion', 'summary': "Explains the rules for inserting data into a red black tree, including the process of recoloring and rotations, and raises the question of whether it's possible to have all black nodes in a red black tree.", 'duration': 146.571, 'highlights': ['The final red black tree after inserting all the data contains nodes in black and red colors.', "The rules for inserting data in a red black tree include creating a node in red color, checking the parent of the newly created node, and performing rotations and recoloring based on the color of the parent's sibling.", 'An important point is raised about the relationship between red black trees and binary search trees, highlighting that while every red black tree is a binary search tree, not every binary search tree is a red black tree.']}], 'duration': 346.988, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/qA02XWRTBdw/pics/qA02XWRTBdw1308535.jpg', 'highlights': ['After inserting 70, resolve red-red conflict by recoloring the parent, its sibling, and the grandparent, ensuring adherence to red-black tree properties.', 'Insert 1 to the left of 2, resulting in a red-red conflict resolved through rotation and recoloring.', 'The final red black tree after inserting all the data contains nodes in black and red colors.', "The rules for inserting data in a red black tree include creating a node in red color, checking the parent of the newly created node, and performing rotations and recoloring based on the color of the parent's sibling.", 'An important point is raised about the relationship between red black trees and binary search trees, highlighting that while every red black tree is a binary search tree, not every binary search tree is a red black tree.']}], 'highlights': ["The process involves recoloring of both the parent and parent's sibling when encountering a red red conflict, resulting in the adjustment of the colors of the nodes (18, 7, and 18's sibling) to black, ensuring the properties of a red black tree.", "The specific example demonstrates the insertion of nodes 25 and 40, with detailed steps for rotations and recoloring to maintain the red-black tree's properties.", 'The process of left and right rotations is crucial in maintaining the balance of the red-black tree and avoiding red-red conflicts.', 'After inserting 70, resolve red-red conflict by recoloring the parent, its sibling, and the grandparent, ensuring adherence to red-black tree properties.', 'The concept of recoloring is essential after rotations to ensure the red-black properties are satisfied.']}