Is the red-Black tree _actually_ a tree?

[Beakerboy]

I was looking at the OLE file directory object within an “empty” Excel spreadsheet’s vbaProject.bin file. The red-black tree looks like this

My understanding of red-black trees is it is to help searches. Each node should have a value between the values of the children. Say I wanted to find Sheet1. I would compare it’s value to “Module1” and see that it is larger, so I would move right to “ThisWorkbook”. Sheet1 is less than ThisWorkbook, so I should move to the right from there, but that takes me to nil. Is it indexed on something other then the name?

Also, a property of red-black trees (according to Wikipedia) is that a red parent cannot have a red child. However, in the real file this seems to exist.

Do you have any insight into the “proper” coloring and structure of this object? Maybe I’m interpreting something incorrectly. I am assuming the directory is zero indexed, and the value in an entry’s previous field refers to the object with that index (pointing down and to the left in my diagram) similarly, next is down and right. The “sub” field seems to mean the next object is the root of a child tree…indicated as a straight down arrow in my diagram.

I have an annotated hex dump of my file here

Any insight into this would be appreciated

[Beakerboy]

So I just found some MS documentation that says it indexes based on the length of the string, and compare the characters only if they are equal.

that still does not explain the coloring discrepancy. It did say that coloring everything black is valid.