Skip to main content

Red Black Tree Deletion in Java

Red Black tree deletion involves following cases:

  1. If node to delete is a RED leaf node then just delete it.
  2. If node to delete is a BLACK node and has one red child then, just replace it with child and retain color of node to be deleted.
  3. If node is having more than two children then just replace the node with in-order predecessor and call the delete routine at in-order predecessor recursively.
  4. But the problem arises when node to delete is a BLACK node and it has only one BLACK child or node to be deleted is a BLACK leaf node. Then DOUBLE BLACK problem arises.
Note: Points form 1 to 3 are easy to implement and can be understood using the code given below.
To resolve DOUBLE BLACK problem we have following four cases:

Why double black problem:
Suppose we have deleted a BLACK node and the number of nodes in the path going through it is reduced by 1. So the BLACK replacement will carry one extra BLACK color to retain property 5 of RB Tree that in any path from root to leaf the number of BLACK nodes must be same.


NOTE: "X" shown in below diagram is replacement of deleted node, it could be NULL also, so we have to be careful with our DOUBLE BLACK fix routine.
Rectangular boxes under x could be leaf nodes or trees, as in future when the DOUBLE BLACK problem propagates then these boxes will make sense in the diagram. 

Case 1: When sibling has color RED, we simply do inverse of zig-zig rotation:


Similarly when sibling is in left side we can do the same process.


 Case 2: When sibling and both of its children are BLACK (or children or leaf nodes):
Then apply the color change and if the parent is BLACK then call the DOUBLE BLACK fix routine again at new X. Otherwise just stop.
Yellow color shows that the node could have either RED or BLACK color.


When parent is RED then change color of parent to BLACK and stop, other wise move x to parent and call DOUBLE BLACK fix routine again,
Here the parent was RED so we stop the routine.
ELSE: call DOUBLE BLACK routine again,


 Case 3: When uncle is BLACK and its left child is RED and right child is BLACK.
Then we just do some pointer change and color change of new sibling and old sibling d and c of a, which was having double black problem, thus the case will be converted to case 4 and we will apply inverse of zig-zig rotation and our tree will be balanced.



Once again let me remind you sibling could be present on other side of the tree also so make the similar cases, just replace left with right and vice-versa.

 Note : After case 3 we must have to call case 4.

Case 4: When sibling is BLACK and its right child is BLACK (left child could be R/B).
We will apply inverse of zig-zig rotation and will change the color in following manner:

  • Color x's new grandfather with same color as x'father.
  • Color new uncle BLACK.

Now we have learned the cases to resolve DOUBLE BLACK problem, lets see some code in action:

Java Code:
There are two classes and one interface:
  • RBTreeFunctions: Interface
  • RBTree 
  • RBTreeTest
This code will be using my earlier BLOG RB Insertion so please check that once.

Code: RB Deletion

    References: 
    https://www.cs.usfca.edu/~galles/visualization/RedBlack.html http://www.stolerman.net/studies/cs521/red_black_trees.pdf

Comments

Post a Comment

Popular posts from this blog

Goodness of Fit Test for normal and poisson distribution

Meaning of Goodness of fit test: We find out which distribution fits the sample data the most. And this is achieved using chi-square distribution (Snedecor and Cochran, 1989). How to apply: There are 4 steps to follow: State the hypothesis:  Data follows a distribution or not Criteria to reject null hypothesis: if Χ 2  > Χ 2 (k,1-α) then reject null hypothesis. Analyze sample data: Compute the chi-square value using below formula: ∑(Oi- Ei) 2 /Ei        : Oi is observed frequency and Ei is expected frequency Interpret the results: Declare the results after comparing the values of Χ 2 and Χ 2 (k,1-α), where k is degree of freedom and  α is significance level. Degree of Freedom: It is  =  n - 1 - m m: number of parameter in the distribution. So in case of normal distribution m is 2 ( μ ,α) and in case of poisson dist. m is = 1 ( λ). Example 1: Goodness of fit test for Normal Distribution Year wise d...
2 comments
Read more

classification of database indexing

Dense Index: For every records we are having one entry in the index file. Sparse Index: Only one record for each block we will have it in the index file. Primary Index ( Primary Key + Ordered Data )  A primary index is an ordered file whose records are fixed length size with 2 fields. First field is same as primary key and the second field is pointer to the data block.  Here index entry is created for first record of each block, called ‘block anchor’. Number of index entries thus are equal to number of blocks Average number of block accesses are = logB (worst case) + 1 (best case),  So on average it will be O(logB) The type of index is called sparse index because index is not created for all the records, only the first records of every block the entry is made into the index file. Example on Primary Index Number of Records = 30000, Block Size = 1024 Bytes, Strategy = Unspanned, Record Size = 100 Bytes, Key Size = 6 Bytes, Pointer Size = 9 Byt...
2 comments
Read more

Reliable User Datagram Protocol

RUDP provides  a solution where UDP  is too primitive because guaranteed-order  p acket  delivery is desirable, but  T CP  adds too much overhead.  In order for RUDP to gain higher Quality of Service , RUDP implements features that are similar to TCP with less overhead. Implementations: In order to ensure quality, it extends UDP by means of adding the following features: Acknowledgment of received packets Flow control Re-transmission of lost packets Over buffering (Faster than real-time streaming) RUDP is not currently a formal standard, however it was described in an n 1999. It has not been proposed for standardization. Working Example: One way to think about how RUDP types of transport work is to use a basic model where all the data is sent in UDP format, and each missing packet is indexed.  Once the main body of the transfer is done, the recipient sends the sender the index list and the sender re-transmits ...
3 comments
Read more