Доказательство количества внутренних узлов в дереве

Question

Я читал о сжатых попытках и читал следующее:

сжатый файл - это дерево с L листьями, и у каждого внутреннего узла в дереве есть как минимум 2 дочерних элемента.

Затем автор написал, что дерево с L выходит таким образом, что у каждого внутреннего узла есть по крайней мере 2 дочерних элемента, но не более L-1 внутренних узлов.Я действительно смущен, почему это так.

Может ли кто-нибудь предложить индуктивное доказательство этого?

Answer 1

Индуктивное доказательство:
мы докажем это индукцией по L - количеству листьев в дереве.
основание: дерево, сделанное из 1 листа, на самом деле является деревом только с корнем.У него 0 внутренних узлов, и утверждение верно.
предположим, утверждение верно для сжатого дерева с L листьями.
Шаг: пусть T - дерево с L + 1 листьями.выберите произвольный лист, пусть он будет l, и обрежьте его.
Чтобы снова сжать дерево - вы должны сделать отца l листом [если у отца l более 2 сыновей, включая l, пропустите этот шаг].Мы делаем это, придавая то же значение, что и брат Л, и обрезая брата.
Теперь у вас есть дерево T с L листьями.
По индукции: T 'имеет не более L-1 внутренних узлов.
Итак, у T было L-1 + 1 = L внутренних узлов, а L + 1 не более.
QED

альтернативное доказательство:
бинарное дерево с L листьями имеет L-1 внутренних узлов (1 + 2 + 4 + ... + L / 2 = L-1)
Поскольку в «худшем случае» у вас есть двоичное дерево [у каждого внутреннего узла есть как минимум 2 сына!], То вы не можете иметь больше, чем внутренних узлов L-1!

Answer 2

Хорошо, так что я пойду.

Определим деревья для начала:

T_0 = { Leaf }

T_i = T_i-1 union { Node(c1, ..., cn) | n >= 1 && ci in T_i-1 }

Trees = sum T_i

Теперь (набросок) подтверждение вашего утверждения.

1. Легко проверить это для T_0

2. Для T_i: если t \in T_i, это либо в T_i-1, либо в новых элементах,В первом случае используйте IH.В последнем случае проверьте утверждение (просто: если ci s имеет L_i листьев, t имеет L = L_1 + ... + L_n листьев. Он также имеет не более L_1 - 1 + L_2 - 1 + ... + L_n - 1 + 1 внутренних узлов (по IH для детей, +1 дляself). Поскольку мы предполагаем, что у каждого внутреннего узла есть как минимум два дочерних элемента (это факт из определения trie), он не более чем L_1 + l_2 + ... + L_n - 2 + 1 = L - 1).

3. По индукции, еслиутверждение верно для t in T_i для всех i, оно выполняется для t in Trees.

Answer 3

Вы должны попробовать нарисовать дерево с L внутренними узлами, где у каждого узла есть 2 дочерних элемента и есть L листьев.Если вы видите, почему это невозможно, нетрудно понять, почему это работает для внутренних узлов L-1.