11 Replies - 1336 Views - Last Post: 09 June 2015 - 04:35 PM

#1 Thalvor   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 08-June 15

Double blacks in a binary red black tree

Posted 08 June 2015 - 02:09 PM

I've been reading about how to do the delete function for a binary red black tree. After reviewing several different instances on how to do it, I'm still left slightly confused.

My main issue is with the Wiki page on red black deletion, I don't want to do top-down so please don't bring it up, but from the cases that are presented on the wiki page it never mentions a double black node. Why is that?

I take cases 1 - 6 and on paper everything seems to work, without ever having to add a double black node. And on paper I don't see the need for the methodology to recursively call each case back to root.

So to clarify my questions. Do I need to use a double black node for bottom up deletion? If not, once I have reached case 6 am I finished without having to worry about anything else?

Is This A Good Question/Topic? 0
  • +

Replies To: Double blacks in a binary red black tree

#2 Thalvor   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 08-June 15

Re: Double blacks in a binary red black tree

Posted 08 June 2015 - 04:12 PM

Maybe this will help. The example I show takes no double blacks. Is the example valid?



"In the algorithm above, all cases are chained in order, except in delete case 3 where it can recurse to case 1 back to the parent node: this is the only case where an in-place implementation will effectively loop (after only one rotation in case 3)."

This is why I haven't seen the need to recurse back. It only happens in this particular case.
 Test case:           6b
                    /    \
                   2r    8b
                  /  \
                 1b   4b
                      /
                     3r


Delete 6 successor is 8

case 2 swap parent and sibling color rotate through parent
                          2b
                        /     \
                       1b     6r
                             /   \
                            4b    8b
                            /
                            1r


case 5 4 has left child red; swap colors and rotate
    
                          2b
                         /  \
                        1b   6r
                            /  \
                           3b   8b
                            \
                             4r


case 6 3 has right child red; rotate 3 through parent
                            2b
                          /    \
                         1b      3b
                                /  \
                               4r   6r
                                      \
                                       8b


since 6 is now red and 8 has no further siblings or children 8 copies into 6 and the original 8 is snipped.
                            2b
                          /    \
                         1b      3b
                                /  \
                               4r   8r



That did show properly, can't seem to edit it. can anyone delete my second post for the example?

Thanks, don't delete now please

This post has been edited by macosxnerd101: 08 June 2015 - 04:09 PM
Reason for edit:: Added code tags around trees for better display

Was This Post Helpful? 0
  • +
  • -

#3 Thalvor   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 08-June 15

Re: Double blacks in a binary red black tree

Posted 08 June 2015 - 04:27 PM

below case 2 before case 5 i have a typo below 4b to left 1r, it should be 4b to left 3r
Was This Post Helpful? 0
  • +
  • -

#4 ishkabible   User is offline

  • spelling expret
  • member icon





Reputation: 1747
  • View blog
  • Posts: 5,898
  • Joined: 03-August 09

Re: Double blacks in a binary red black tree

Posted 08 June 2015 - 06:03 PM

What article are you referring to?
Was This Post Helpful? 0
  • +
  • -

#5 Thalvor   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 08-June 15

Re: Double blacks in a binary red black tree

Posted 08 June 2015 - 06:07 PM

Okay, I think I figured it out. I don't need to do a double black because I am not deleting the node before reconstruction. Now if I did, say in my example 3 and 4 were both black. Though that would be a violation with numbers I have, but imagine that the tree structure allows for it, maybe it has other child nodes. Now that both are black and I delete 6 and this time find the predecessor 4, I copy 4 to 6 and move 3 up into 4 making it a double black. Frankly I think adding that makes the cases harder, forcing a red at root to me is harder than that. When I say harder, I mean the amount of case logic that really needs to be implemented. 4 cases with top down but add a massive recoloring scheme, place holder and flags, not to mention iteration means more lines of code, and yes it's not that easy to implement. It was 2 or 3 days of struggling with it, and most information out there doesn't point out there are many different ways, and add the fact the concept in and of itself is not obvious, this truely is one of the hardest data structures to write for. Although satisfying when completed. More to the point, after hours of reading the various ways, I have to say the wiki page does the best job. You just have to be willing to slow down and do each case meticulously.

View Postishkabible, on 08 June 2015 - 06:03 PM, said:

What article are you referring to?

The wiki page on red black trees, under operations and deletions
Was This Post Helpful? 0
  • +
  • -

#6 ishkabible   User is offline

  • spelling expret
  • member icon





Reputation: 1747
  • View blog
  • Posts: 5,898
  • Joined: 03-August 09

Re: Double blacks in a binary red black tree

Posted 08 June 2015 - 06:55 PM

There are lots of wiki pages. Are you referring to wikipedia?
Was This Post Helpful? 1
  • +
  • -

#7 Thalvor   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 08-June 15

Re: Double blacks in a binary red black tree

Posted 08 June 2015 - 07:05 PM

View Postishkabible, on 08 June 2015 - 06:55 PM, said:

There are lots of wiki pages. Are you referring to wikipedia?

http://en.m.wikipedi...80%93black_tree
Was This Post Helpful? 0
  • +
  • -

#8 Thalvor   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 08-June 15

Re: Double blacks in a binary red black tree

Posted 08 June 2015 - 07:23 PM

View Postishkabible, on 08 June 2015 - 06:55 PM, said:

There are lots of wiki pages. Are you referring to wikipedia?

I will say thanks for not using your question about my reference to declare some outrageous violation has taken place and declare that my question is void like some sites do. Well we all know which one.
Was This Post Helpful? 0
  • +
  • -

#9 ishkabible   User is offline

  • spelling expret
  • member icon





Reputation: 1747
  • View blog
  • Posts: 5,898
  • Joined: 03-August 09

Re: Double blacks in a binary red black tree

Posted 08 June 2015 - 07:56 PM

I normally like wikipedia but in this case I didn't find the article very easy to understand (and it felt misleading in some cases). This link felt simpler and easier to follow and indeed does mention the double black case.

Additionally the wikipedia page *does* consider all double black cases. Actually it considers an ungodly 6 cases which are mutually exclusive and exhaustive and thus all cases, period, are considered. Case 3 handles the triple black case. Case 4 considers double black with a red parent. So case 3 and case 4 consider both depth 1 nested double black cases. Case 5 considers a double black with a red sibling (note, all double blacks have siblings). Case 6 considers the double black case considers double black with a black sibling. These cases combined consider all double black cases. (Actually I think just case 5 and case 6 manage this but the assume that case 1-4 did not hold to ensure that the transformations they perform are valid).

This post has been edited by ishkabible: 08 June 2015 - 08:02 PM
Reason for edit:: grammar and spelling and corrections and stuff

Was This Post Helpful? 0
  • +
  • -

#10 Thalvor   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 08-June 15

Re: Double blacks in a binary red black tree

Posted 08 June 2015 - 09:10 PM

you are mistaken. I know it looks that way, but until you actually move the node up you are dealing with two different methodologies. Think about it like this, in the case I first presented. The way in which I follow each case and is valid and leads to an end result, which is valid for that particular case. okay, this is a little bit hard to get, but really all I am trying to do is get the tree into a state it would be in if the node to be deleted had never been. But given the sequence of the numbers could you imagine how many permutations that could be? So hence you need logic to lead you back through an existing permutation, unlike forcing a red node which generates an artificial new case. Thus, lets get back to my point. If I take may original case and add 8 to six, collapsing 8 into a doubly black state what I am really doing is creating a super position in which I must derive the original case. Check your reference that breaks out the null, at delete 20 to force separation of the new superposition aka double black. Now that does not need to be done. It is done indirectly grant you, but it does not need to be physically done. That is collapsing to doubly black state. Here is the proof I consider, though as always I could be wrong.

if b + b =b^2
The b + b = s 《》p = b^2 ( comparison leads to path from p to s and vis versa)
So doubly black or not. The only difference is in reconstruction before or after collapse.
Was This Post Helpful? 0
  • +
  • -

#11 Thalvor   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 8
  • Joined: 08-June 15

Re: Double blacks in a binary red black tree

Posted 08 June 2015 - 09:41 PM

To go back to case three. The idea of the violation at parent which the gets passed to case one. You are right that this is an indication of a double black on P's path, directly indicated or not. What I am arguing and it's a hard argument so I am more than happy to be wrong, but I consider we are talking about two sides of the same coin. I go back to the idea of the actual logic that would say collapse and reconstruct or reconstruct and then collapse. In that way the Wikipedia page never mentions double black directly and for reason, it implied in the logic rather than directly exercised in the logic which to makes it not that hard to code for. I can code for six cases that take one ideas, it's hard to code for 4 cases that take 3 each
Was This Post Helpful? 0
  • +
  • -

#12 ishkabible   User is offline

  • spelling expret
  • member icon





Reputation: 1747
  • View blog
  • Posts: 5,898
  • Joined: 03-August 09

Re: Double blacks in a binary red black tree

Posted 09 June 2015 - 04:35 PM

I'm sorry, I don't really understand what you are saying. I'm going to recommend this link again as it breaks it down nicely. As far as I can tell both pages are describing a very similar algorithm.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1