CODEWITHSUNDEEP
algorithmred-black-tree
C.Hu
C.Hu

Reputation: 57

What should a 4-node red-black tree look like

Hi I know little about red-black tree before and maybe it's a stupid question.
Here's a 4-node tree:

my tree

Is it a legal red-balck tree? In my opinion, it actually violates rules of red-black tree:

  1. Every red node has both of its children colored black.
  2. Every path from the root to a tree leaf contains the same number (the "black-height") of black nodes.

If not what should a 4-node red-black look like?
Thanks

Upvotes: 1

Views: 228

Answers (1)

Eric T-M
Eric T-M

Reputation: 93

You are correct that this tree violates the rules of red-black trees because the path 3-2-1-Null goes through 3 black nodes, while 3-4-Null only goes through 2.

Recall that there is no constraint that black nodes have to have their children painted red, only the reverse. Even a tree with all black nodes is technically a red-black tree, as long as it is balanced and therefore satisfies that "Every path from the root to a tree leaf contains the same number (the 'black-height') of black nodes."

As a result, you could make this tree a valid red-black tree by painting nodes 2 and 4 black and painting node 1 red. Notice node 1 (the only red node) would still have 2 black children and all paths from the root to leaves would hit 3 black nodes. Therefore satisfying the rules of a red-black tree.

Upvotes: 2

Related Questions