Maximum number of red nodes in red black tree [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

This question appears to be off-topic because it lacks sufficient information to diagnose the problem. Describe your problem in more detail or include a minimal example in the question itself.

Closed 8 years ago.

Improve this question

In a red-black tree with n nodes, what is the maximum number of red nodes (assuming the root is black)?

Is it O(n)?

Answer 1

If the tree has n nodes and the root is black, there are n - 1 nodes left and n - 1 = O(n), so you're right.

If you want to count/bound number of red nodes in the tree more accurately, you have to know the topology of that tree.

For instance, if the tree is a complete binary tree, according to the definition of the red-black-tree, it can have no red nodes at all.