Deletion from a red-black tree, Data Structure & Algorithms

Assignment Help:

Deletion in a RBT uses two main processes, namely,

Procedure 1: This is utilized to delete an element in a given Red-Black Tree. It involves the method of deletion utilized in binary search tree.

Procedure 2: when the node is removed from a tree, and after deletion, there might be chances of losing Red-Black Properties in a tree and so, some of the cases are to be considered to retain those properties.

This process is called only while the successor of the node to be deleted is Black, however if y is red, the red- black properties yet hold and for the following reasons:

  • No red nodes have been made adjacent
  • No black heights in the tree have altered
  • y could not have been the root

Now, the node (say x) that takes the position of the deleted node (say z) will be called in process 2. Now, this process starts with a loop to make the extra black up to the tree until

o   X points to a black node

o   Rotations to be performed and recoloring to be done

o   X is a pointer to the root wherein the extra black can be easily removed

 This while loop will be executed till x becomes root and its color is red. Here, a new node (say w) is taken which is the sibling of x.

There are four cases that we will be letting separately as follows:

Case 1: If color of w's sibling of x is red

Since W must have black children, we can change the colors of w & p (x) and then left rotate p (x) and the new value of w to be the right node of parent of x.  Now, the conditions are satisfied and we switch over to case 2, 3 and 4.

Case 2: If color of w is black & both of its children are also black.

As w is black, we make w to be red leaving x with only one black and assign parent (x) to be the new value of x.  Now, the condition will be again verified, i.e. x = left (p(x)).

Case 3: If the color of w is black, however its left child is red and w's right child is black. After entering case-3, we change the color of left child of w to black and w to be red and then carry out right rotation on w without violating any of the black properties. Now the new sibling w of x is black node with a red right child and therefore case 4 is obtained.

Case 4: While w is black and w's right child is red.

It can be done by making some color changes and performing a left rotation on p(x). We can delete the extra black on x, making it single black. Setting x as the root causes the while loop to terminate.


Related Discussions:- Deletion from a red-black tree

Data structures, I am looking for assignment help on the topic Data Structu...

I am looking for assignment help on the topic Data Structures. It would be great if anyone help me.

Stack, using a program flowchart design a program to illustrate pop and pus...

using a program flowchart design a program to illustrate pop and push operation

Comparisons between linear and binary search, Comparative Study of Linear a...

Comparative Study of Linear and Binary Search Binary search is lots quicker than linear search. Some comparisons are following: NUMBER OF ARRAY ELEMENTS EXAMINED array

Kruskals algorithm, Krushkal's algorithm uses the concept of forest of tree...

Krushkal's algorithm uses the concept of forest of trees. At first the forest contains n single node trees (and no edges). At each of the step, we add on one (the cheapest one) edg

All pairs shortest paths, N = number of rows of the graph D[i[j] = C[i][...

N = number of rows of the graph D[i[j] = C[i][j] For k from 1 to n Do for i = 1 to n Do for j = 1 to n D[i[j]= minimum( d ij (k-1) ,d ik (k-1) +d kj (k-1)

Explain about the structured types - built-in types, Explain about the Stru...

Explain about the Structured types - Built-In Types Values of the carrier set are not atomic, consisting rather than several atomic values arranged in some way. Common illu

What is a height balanced tree, What is a height balanced tree? Height Ba...

What is a height balanced tree? Height Balanced Tree (AVL Tree) An AVL tree is a binary search tree in which the height of the left and right subtree of the root vary by at most

Breadth first traversal, The data structure needed for Breadth First Traver...

The data structure needed for Breadth First Traversal on a graph is Queue

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd