logging in or signing up RED – BLACK TREES abhi121090 Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 349 Category: Entertainment License: All Rights Reserved Like it (0) Dislike it (0) Added: March 02, 2011 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... Premium member Presentation Transcript RED – BLACK TREES: RED – BLACK TREESIntro : Intro A red-black tree is a BST, in which all the nodes are colored either red or black. This should follow two types of properties Node properties Edge propertirsSlide 3: Node properties: 1. The root and all external nodes are colored as black. 2. No root-to-external node path has 2 consecutive red nodes. 3. All root-to-external node paths have the same number of black nodes .Slide 4: Edge properties: 1. Pointer from internal to external nodes are black. 2. No root-to-external-node path has two consecutive red pointers. 3.All root-to-external node path have the same number of black pointers.Rank of the Node: Rank of the Node The rank of the node in a red-black tree be the number of black pointers on any path from the node to the any external node. A Red-Black tree is represented by end with null pointers and nodes. Searching is similar as the searching in BST.Simple red-black tree: Simple red-black tree 65 50 80 10 60 70 5 57Inserting:: Inserting: Insertions follows both the node and edge rules. If the tree is not balanced, it has to be rotated like the rotations in the AVL Tree. LLr, LRr, LLb,LRb rotaions are applied. These are color balancing rotaions.Deleting:: Deleting: Is similar to BST. But the rotation we apply on these trees are Rb0(two black nodes), Rb1(root is red), Rb2(LR in AVL). Rr0(black points red), Rr1(LR in AVL), Rr2(height) Similar for the left sub-tree.Complexity: Complexity Time complexity of Red-Black Tree operations (insert & delete) is O (log n). But the space complexity is increased by Theta (log n). Color changing rotations will take the time of theta (n)Splay Trees: Splay Trees AVL and RB trees are used to implement the dictionaries. But these tress perform operations very slowly. Now splay trees are used for faster operations. But the time complexity of each operation id O (n). Total time complexity is O (f+i+d).Inserting:: Inserting: It follows sequence of steps called as SPLAY steps. the root is the splay node of the BST. Insertion is similar to BST but it is followed by a set of rotations. They are Zig. Zag. Deletion and search are similar to that of BST.Time complexity:: Time complexity: The amortized complexity of the splay tree operations is O (log n). Amortized complexity is the time needed, that often bears no relationship to the actual operation.M – Way search trees: M – Way search trees Definition: It may be empty. If not then It is an extended BST with external null nodes. Every node p has exactly p+1 number of children. For a node p if k1, k2, …… kn are the keys then k1<k2<……..<kn.Insertion and deletion: Insertion and deletion If k is the element to be inserted then Select the sub-tree in such a way where k1 < k < k2 If k is the element to be deleted then Select the sub-tree in such a way where k1<k<k2 if the element is found there delete it.Simple m-way search tree: Simple m-way search tree Example 10 80 5 82 85 86 89 20 30 40 50 32 38Search and height: Search and height Search is also similar to BST. But here we need to find the intermediate sub-tree. Let The height of the m-way search tree is ‘h’ then the number of nodes are pow(m,h)-1. If number of elements are m then the height is log m (n+1).B-trees: B-trees Definition: A B-tree is an m-way search tree and it may not be empty and it has to satisfies the following properties.. The root has at least two of children. All internal nodes except root has at least [m/2] children. All external nodes are at same level.Example: Example Simple B-tree 10 80 5 62 85 86 89 20 30 40 50 32 48 90 2 3 6 8 12 28Height of B-tree: Height of B-tree Let h is the height , d=[m/2], n is the number of elements then 2d h-1 <= n <= m h-1 Log m (n+1) <= h <= log m (n+1/2)+1 Searching is similar to the m-way search trees. You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.
RED – BLACK TREES abhi121090 Download Post to : URL : Related Presentations : Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Uploaded from authorPOINT lite Insert YouTube videos in PowerPont slides with aS Desktop Copy embed code: (To copy code, click on the text box) Embed: URL: Thumbnail: WordPress Embed Customize Embed The presentation is successfully added In Your Favorites. Views: 349 Category: Entertainment License: All Rights Reserved Like it (0) Dislike it (0) Added: March 02, 2011 This Presentation is Public Favorites: 0 Presentation Description No description available. Comments Posting comment... Premium member Presentation Transcript RED – BLACK TREES: RED – BLACK TREESIntro : Intro A red-black tree is a BST, in which all the nodes are colored either red or black. This should follow two types of properties Node properties Edge propertirsSlide 3: Node properties: 1. The root and all external nodes are colored as black. 2. No root-to-external node path has 2 consecutive red nodes. 3. All root-to-external node paths have the same number of black nodes .Slide 4: Edge properties: 1. Pointer from internal to external nodes are black. 2. No root-to-external-node path has two consecutive red pointers. 3.All root-to-external node path have the same number of black pointers.Rank of the Node: Rank of the Node The rank of the node in a red-black tree be the number of black pointers on any path from the node to the any external node. A Red-Black tree is represented by end with null pointers and nodes. Searching is similar as the searching in BST.Simple red-black tree: Simple red-black tree 65 50 80 10 60 70 5 57Inserting:: Inserting: Insertions follows both the node and edge rules. If the tree is not balanced, it has to be rotated like the rotations in the AVL Tree. LLr, LRr, LLb,LRb rotaions are applied. These are color balancing rotaions.Deleting:: Deleting: Is similar to BST. But the rotation we apply on these trees are Rb0(two black nodes), Rb1(root is red), Rb2(LR in AVL). Rr0(black points red), Rr1(LR in AVL), Rr2(height) Similar for the left sub-tree.Complexity: Complexity Time complexity of Red-Black Tree operations (insert & delete) is O (log n). But the space complexity is increased by Theta (log n). Color changing rotations will take the time of theta (n)Splay Trees: Splay Trees AVL and RB trees are used to implement the dictionaries. But these tress perform operations very slowly. Now splay trees are used for faster operations. But the time complexity of each operation id O (n). Total time complexity is O (f+i+d).Inserting:: Inserting: It follows sequence of steps called as SPLAY steps. the root is the splay node of the BST. Insertion is similar to BST but it is followed by a set of rotations. They are Zig. Zag. Deletion and search are similar to that of BST.Time complexity:: Time complexity: The amortized complexity of the splay tree operations is O (log n). Amortized complexity is the time needed, that often bears no relationship to the actual operation.M – Way search trees: M – Way search trees Definition: It may be empty. If not then It is an extended BST with external null nodes. Every node p has exactly p+1 number of children. For a node p if k1, k2, …… kn are the keys then k1<k2<……..<kn.Insertion and deletion: Insertion and deletion If k is the element to be inserted then Select the sub-tree in such a way where k1 < k < k2 If k is the element to be deleted then Select the sub-tree in such a way where k1<k<k2 if the element is found there delete it.Simple m-way search tree: Simple m-way search tree Example 10 80 5 82 85 86 89 20 30 40 50 32 38Search and height: Search and height Search is also similar to BST. But here we need to find the intermediate sub-tree. Let The height of the m-way search tree is ‘h’ then the number of nodes are pow(m,h)-1. If number of elements are m then the height is log m (n+1).B-trees: B-trees Definition: A B-tree is an m-way search tree and it may not be empty and it has to satisfies the following properties.. The root has at least two of children. All internal nodes except root has at least [m/2] children. All external nodes are at same level.Example: Example Simple B-tree 10 80 5 62 85 86 89 20 30 40 50 32 48 90 2 3 6 8 12 28Height of B-tree: Height of B-tree Let h is the height , d=[m/2], n is the number of elements then 2d h-1 <= n <= m h-1 Log m (n+1) <= h <= log m (n+1/2)+1 Searching is similar to the m-way search trees.