CODEWITHSUNDEEP
data-structurestreebinary-treebinary-search-treered-black-tree
Nilay İnel
Nilay İnel

Reputation: 101

Why are leaves blank on all rb trees?

I'm working on data structures. There is something I do not understand about Red and Black trees. He always writes about the following features about these trees. But in all examples the values of the leaves are null. Why is that not in the features either. Why "All leaf nodes are black and blank." not?

Red/Black Property: Every node is colored, either red or black. Root Property: The root is black. Leaf Property: Every leaf (NIL) is black. Red Property: If a red node has children then, the children are always black. Depth Property: For each node, any simple path from this node to any of its descendant leaf has the same black-depth (the number of black nodes).

Upvotes: 1

Views: 96

Answers (1)

jbapple
jbapple

Reputation: 3390

It doesn't really matter if all nodes are keyless and black or not.

If the nodes could be any color and/or empty, the asymptotics would not change at all, since red children cannot have red parents and all internal nodes have associated keys.

All paths would still have lengths that are at most a factor of two different in total number of keys, though now that would be 2L+2, rather than 2L for the longest path compared to the shortest path (of length L).

Upvotes: 1

Related Questions