I need prove that any red-black tree with at least two elements obtained through the insertion algorithm has at least one red node. For this, I need use Induction.

I don't understand how apply induction. (((


1 Answer 1


Here is the obvious thing to try:

  1. Prove that if you apply the insertion algorithm twice on an empty tree, then the resulting red-black tree has a red node (this also follows from the invariants of red-black trees).

  2. Prove that if a red-black tree has a red node and you insert an element using the insertion algorithm, then the result red-black tree has a red node.

I don't know if this scheme works, but it's the most immediate way to apply induction.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.