[Bug 1861] RBTree: redundant code removed

[bugzilla-daemon at rtems.org]

https://www.rtems.org/bugzilla/show_bug.cgi?id=1861

--- Comment #6 from Petr Benes <benesp16 at fel.cvut.cz> 2011-07-30 16:52:17 CDT ---
The second case is insufficient testing as we know now.

On 07/29/2011 08:04 PM, bugzilla-daemon at rtems.org wrote:
> The Wikipedia page says this about the third case:
> "The complex case is when both M and C are black. (This can only occur when
> deleting a black node which has two leaf children, because if the black node M
> had a black non-leaf child on one side but just a leaf child on the other side,
> then the count of black nodes on both sides would be different, thus the tree
> would had been an invalid red–black tree by violation of Property 5.)"
I wonder this case is redundant in rtems rbtree implementation indeed.
If you look at the Wikipedia sample tree on the top of that page they denote
'leaf node' the NULL ones. What is a leaf in our implementation is a node
holding a key which must be red in any case. If we imagine the tree without the
NULL nodes, then the color changes with every layer of the tree. What do you
think? Experiments still agree.

>
> I'm not quite sure how to cause this situation, but nothing I know about the
> tree properties prevents it from happening. We just need to figure out how to
> cause the case while testing the tree.
>
> I think we just haven't been smart enough with our test cases yet. Let's hold
> off removing these cases until we can think about it some more.

-- 
Configure bugmail: https://www.rtems.org/bugzilla/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are watching all bug changes.