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. (((
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
Here is the obvious thing to try:
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).
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.