I was reading about compressed tries and read the following:
a compressed trie is a tree which has L leaves and every internal node in the trie has at least 2 children.
Then the author wrote that a tree with L leaves such that every internal node has alteast 2 children, has atmost L-1 internal nodes. I am really confused why this is true.
Can somebody offer a inductive proof for it?
Inductive proof:
we will prove it by induction on
L
- the number of leaves in the tree.base: a tree made out of 1 leaf is actually a tree with only a root. It has 0 internal nodes, and the claim is true.
assume the claim is true for a compressed tree with L leaves.
Step: let T be a tree with L+1 leaves. choose an arbitrary leaf, let it be l, and trim it.
In order to make the tree compressed again - you need to make l's father a leaf [if l's father has more then 2 sons including l, skip this step]. We do it by giving it the same value as l's brother, and trimming the brother.
Now you have a tree T' with L leaves.
By induction: T' has at most L-1 internal nodes.
so, T had L-1+1 = L internal nodes, and L+1 leaves, at most.
Q.E.D.
alternative proof:
a binary tree with L leaves has L-1 internal nodes (1 + 2 + 4 + ... + L/2 = L-1)
Since at "worst case" you have a binary tree [every internal node has at least 2 sons!], then you cannot have more then L-1 internal nodes!