Proof for number of internal nodes in a tree
-
16-04-2021 - |
Pergunta
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?
Solução
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!
Outras dicas
You should try drawing a tree with L internal nodes, where every node has 2 children and there are L leaves. If you see why this is impossible, it won't be hard to figure out why it does work for L-1 internal nodes.
Ok, so I'll have a go.
Define trees for a start:
T_0 = { Leaf }
T_i = T_i-1 union { Node(c1, ..., cn) | n >= 1 && ci in T_i-1 }
Trees = sum T_i
Now, the (sketch) proof of your assertion.
It is easy to check it for
T_0
For
T_i
: ift \in T_i
it is either inT_i-1
or in the new elements. In the former case, use IH. In the latter case check the assertion (simple: ifci
s haveL_i
leaves,t
hasL = L_1 + ... + L_n
leaves. It also hase no more thanL_1 - 1 + L_2 - 1 + ... + L_n - 1 + 1
inner nodes (by IH for children, +1 for self). Because we assume each inner node has at least two children (that's the fact from the trie definition), it is no more thanL_1 + l_2 + ... + L_n - 2 + 1 = L - 1
).By induction, if the assertion holds for
t in T_i
for alli
, it holds fort in Trees
.