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

Last in first out method, This method is the reverse of FIFO and assumes th...

This method is the reverse of FIFO and assumes that each issue of stock is made from latest items received in the enterprises .Thus if the last lot to be received is not sufficient

Explain the scan-line algorithm, Explain the Scan-Line Algorithm This i...

Explain the Scan-Line Algorithm This image-space method for removing hidden surfaces is an extension of the scan-line algorithm for filling polygon interiors. Instead of fillin

Enumerate about the carrier set members, Enumerate about the carrier set me...

Enumerate about the carrier set members Ruby is written in C, so carrier set members (which is, individual symbols) are implemented as fixed-size arrays of characters (which is

Splay trees, Addition of new records in a Binary tree structure always occu...

Addition of new records in a Binary tree structure always occurs as leaf nodes, which are further away from the root node making their access slower. If this new record is to be ac

Array, extra key inserted at end of array is called

extra key inserted at end of array is called

What are the example of area subdivision method, Example of Area Subdivisio...

Example of Area Subdivision Method The procedure will be explained with respect to an illustrative problem, with the image consisting of five objects, namely a triangle (T), qu

Linked list, create aset of ten numbers.then you must divide it into two s...

create aset of ten numbers.then you must divide it into two sets numbers which are set of odd numbers and set of even numbers.

Conversion of forest into tree, Conversion of Forest into Tree A binary...

Conversion of Forest into Tree A binary tree may be used to show an entire forest, since the next pointer in the root of a tree can be used to point to the next tree of the for

Graph connectivity, A connected graph is a graph wherein path exists among ...

A connected graph is a graph wherein path exists among every pair of vertices. A strongly connected graph is a directed graph wherein every pair of distinct vertices is connecte

Complexity of an algorithm, Q. Explain the complexity of an algorithm?  Wha...

Q. Explain the complexity of an algorithm?  What are the worst case analysis and best case analysis explain with an example.

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