none
Red Black Tree in MS-CFB RRS feed

  • Question

  • In the MS-CFB documentation section 2.6.4 it lists constraints for a valid red-black tree.  the first constraint is:

    The root storage object MUST always be black. Because the root directory does not have siblings, its color is irrelevant and can therefore be either red or black.

    That statement seems to contradict itself. If it can be red or black, why does it have to be black?  I am assuming it has to be black BECAUSE otherwise you could assume it could be red OR black looking only at the other constraints.  

    In my CFB file I am trying to parse, which is a fresh, blank .MSG file generated by Outlook 2013, the root storage object's color is red(0x00). It is the first Directory entry in the first directory sector pointed to from the header, it's name is:

    "Root Entry\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0".

    In the first Directory sector the first 64 bytes are the name.  the next two are the length of the name, the following byte is the type of Directory Entry which is Root storage type(0x05) and the next byte is 0x00, or a red color flag.

    Was i misinterpreting the constraint?  or am I incorrectly parsing the directory entry? or is my file somehow corrupted?


    Michael Billingham

    Thursday, December 17, 2015 3:20 AM

Answers

  • Hi Michael,

    What they are stating here is that for the root node, effectively the color doesn't matter for balancing purposes. This is stated in definitions of red/black trees. If you look at the other nodes, they should be colored properly.

    In my parsing of the Root Entry using a .msg from Office 16, I see the same thing. 0x00 or red. But the rest of the tree looks balanced. Can you verify?

    Best regards,
    Tom Jebo
    Microsoft Open Specifications

    Saturday, December 19, 2015 12:35 AM
    Moderator

All replies

  • Hello Michael,

    Thank you for your question. One of the Open Specifications team members will investigate your issue.

    Thanks,
    Kamil Sykora

    Friday, December 18, 2015 7:40 PM
  • Hi Michael,

    What they are stating here is that for the root node, effectively the color doesn't matter for balancing purposes. This is stated in definitions of red/black trees. If you look at the other nodes, they should be colored properly.

    In my parsing of the Root Entry using a .msg from Office 16, I see the same thing. 0x00 or red. But the rest of the tree looks balanced. Can you verify?

    Best regards,
    Tom Jebo
    Microsoft Open Specifications

    Saturday, December 19, 2015 12:35 AM
    Moderator