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

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

Space-complexity of the algorithm, The space-complexity of the algorithm is...

The space-complexity of the algorithm is a constant. It just needs space of three integers m, n and t. Thus, the space complexity is O(1). The time complexity based on the loop

Define a b-tree, Define a B-Tree Justas AVL trees are balanced binary s...

Define a B-Tree Justas AVL trees are balanced binary search trees, B-trees are balanced M-way search trees. A B-Tree of order M is either the empty tree or it is an M-way searc

Sparse matrix, How sparse matrix stored in the memory of a computer?

How sparse matrix stored in the memory of a computer?

Implementation of dequeue, Dequeue (a double ended queue) is an abstract da...

Dequeue (a double ended queue) is an abstract data type alike to queue, where insertion and deletion of elements are allowed at both of the ends. Like a linear queue & a circular q

Explain b tree (binary tree), B Tree Unlike a binary-tree, every node o...

B Tree Unlike a binary-tree, every node of a B-tree may have a variable number of keys and children. The keys are stored in non-decreasing order. Every key has an associated ch

User-specified memory location, You need to implement a function which will...

You need to implement a function which will write out a given user-specified memory location to disk in base 10. That means that you have to convert the large number data structure

Reverse order of elements on a slack, Q. Reverse the order of the elements ...

Q. Reverse the order of the elements on a stack S    (i) by using two additional stacks (ii) by using one additional queue. Ans :      L e t S be the stac

Explain dijkstra''s algorithm, Explain Dijkstra's algorithm Dijkstra's ...

Explain Dijkstra's algorithm Dijkstra's algorithm: This problem is concerned with finding the least cost path from an originating node in a weighted graph to a destination node

State the complex reallocation procedure, State the complex reallocation pr...

State the complex reallocation procedure Some languages provide arrays whose sizes are established at run-time and can change during execution. These dynamic arrays have an in

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