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

Avl tree rotations, AVL trees and the nodes it contains must meet strict ba...

AVL trees and the nodes it contains must meet strict balance requirements to maintain O(log n) search time. These balance restrictions are kept maintained via various rotation func

Arrays and pointers, C compiler does not verify the bounds of arrays. It is...

C compiler does not verify the bounds of arrays. It is your job to do the essential work for checking boundaries wherever required. One of the most common arrays is a string tha

Tower of hanoi, how do we use 4-discs stack to solve tower of hanoi problem...

how do we use 4-discs stack to solve tower of hanoi problem and write an algorithm to solve it?

State the ways to construct container taxonomy, State the ways to construct...

State the ways to construct container taxonomy There are several ways that we could construct our container taxonomy from here; one way that works well is to make a fundamental

Sorting algorithms, Sorting is significant application activity. Several so...

Sorting is significant application activity. Several sorting algorithms are obtainable. But, each is efficient for a specific situation or a specific kind of data. The choice of a

Binary search, Write the algorithm for Binary search. Also apply this algo...

Write the algorithm for Binary search. Also apply this algorithm on the following data. 22, 44, 11, 88, 33, 55, 77, 66

State about the bit string, State about the Bit String Carrier set of...

State about the Bit String Carrier set of the Bit String ADT is the set of all finite sequences of bits, including empty strings of bits, which we denote λ. This set is {λ, 0

Characteristics of good algorithms, What do we mean by algorithm? What are ...

What do we mean by algorithm? What are the characteristics of a good and relevant algorithm? An algorithm is "a step-by-step procedure for finishing some task'' An algorithm c

Luminous Jewels - The Polishing Game, Byteland county is very famous for lu...

Byteland county is very famous for luminous jewels. Luminous jewels are used in making beautiful necklaces. A necklace consists of various luminous jewels of particular colour. Nec

Explain open addressing, Open addressing The easiest way to resolve a c...

Open addressing The easiest way to resolve a collision is to start with the hash address and do a sequential search by the table for an empty location.

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