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

Definition of algorithm, Definition of Algorithm Algorithm must have th...

Definition of Algorithm Algorithm must have the following five characteristic features: 1.      Input 2.      Output 3.      Definiteness 4.      Effectiveness 5

State the term access restrictions - container, What is Access Restriction...

What is Access Restrictions Structured containers with access restrictions only allow clients to add, remove and examine elements at certain locations in their structure. For

Er diagram, Ask queConsider the following functional dependencies: Applican...

Ask queConsider the following functional dependencies: Applicant_ID -> Applicant_Name Applicant_ID -> Applicant_Address Position_ID -> Positoin_Title Position_ID -> Date_Position_O

C, padovan string

padovan string

How to write binary search algorithm?, Q. Write down the binary search algo...

Q. Write down the binary search algorithm and trace to search element 91 in following given list: 13          30          62           73         81         88             91

C++ function, Write c++ function to traverse the threaded binary tree in in...

Write c++ function to traverse the threaded binary tree in inorder traversal

Convert graph into tree, How can we convert a graph into a tree ? Do we hav...

How can we convert a graph into a tree ? Do we have any standardized algorithm for doing this?

Sparse metrics, Q. Define the sparse metrics and also explain the represent...

Q. Define the sparse metrics and also explain the representation of a 4X4 matrix using linked list.         Ans: A matrix in which number of zero entries is quite h

Algorithm to merge two sorted arrays with third array, Q. Write down an alg...

Q. Write down an algorithm to merge the two sorted arrays into the third array. Do  not perform the sort function in the third array.                           Ans: void m

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