Can we have a red-black tree without any red nodes? [closed]

Question

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 9 years ago.

Improve this question

I wonder whether a red black tree should have at least one red node. Also, given a BST, if we can convert it into an RBT, is there a unique way to turn this tree into a red-black tree?

Answer 1

A quick glance at the properties of a red-black tree shows that there is no requirement for any node to be red. The only way red nodes come about is through property 5:

Every simple path from a given node to any of its descendant leaves contains the same number of black nodes.

This property is also satisfied by any perfect binary tree, so every perfect binary search tree with only black nodes is also a red-black tree. (I'm not sure if the textbook red-black tree algorithms ever produce these, though.)

Also, given a BST, if we can convert it into an RBT, is there a unique way to turn this tree into a red-black tree?

There is no single unique RBT for an arbitrary BST; there are always multiple equivalent RBTs, except for very shallow trees.