Нижняя граница для числа «коротких» путей в корневом дереве с полиномиальным размером

Пусть - корневое двоичное дерево. Каждый путь от корня до листа имеет длину . Каждый узел всегда имеет левый и правый дочерние узлы, но возможно, что они одинаковы (поэтому всегда возможно путей). Размер ограничен . Узел с разными дочерними узлами называется ветвящимся узлом .$T$$T$$n$$T$$2^n$$T$$O(poly(n))$

Мы говорим, что два пути различны, если есть один общий ветвящийся узел, и один путь идет к левому дочернему узлу, а другой путь идет к правому дочернему узлу. Ясно, что в есть хотя бы один путь с ветвящимися узлами. Иначе в было бы слишком много узлов .$T$$O(\log n)$$T$

Существует ли лучшая нижняя граница для числа путей с ветвящимися узлами, если я знаю, что в дереве есть ветвящихся узлов?$O(\log n)$$\omega(\log n)$

Нижняя граница - пути с ветвящимися узлами, если в дереве есть хотя бы ветвящихся узлов.O ( log n ) Ω ( log n $\Omega(\log n)$$O(\log n)$$\Omega(\log n)$

Это может быть достигнуто: используйте дерево, которое имеет один длинный путь (длина ), все узлы которого являются узлами ветвления, без других узлов ветвления в дереве.$n$

Вот эскиз нижней границы.

Во-первых, уплотните дерево, сжимая любой внутренний узел, который не является ветвящимся узлом. Если исходный размер дерева был , новое дерево все равно должно быть , поскольку вы только сократили количество узлов. Теперь глубина листа - это число ветвящихся узлов на исходном пути к этому листу, и у нас есть полное двоичное дерево (каждый узел имеет степень 2 или 0). < n $< n^c$$< n^c$

Если нет листьев глубины , то число путей на единицу больше, чем число ветвящихся узлов, которое равно , поэтому мы можем предположить, что хотя бы один лист имеет глубина .Ω ( log n ) Ω ( log n $\Omega(\log n)$$\Omega(\log n)$$\Omega(\log n)$

Далее вспомним неравенство Крафта. Если глубина листа в полном двоичном дереве равна , то .Σ v l e a f 2 - d ( v ) = $d(v)$$\Sigma_{v \mathrm{\ leaf}} 2^{-d(v)} = 1$

Теперь у нас меньше, чем листьев. Мы хотим показать, что у нас их много на глубине . Предположим, мы исключаем из рассмотрения те, которые имеют глубину не менее . Это убирает не более веса из суммы в неравенстве Крафта, поэтому для этих листьев на глубине не более , мы имеем . У нас также есть (поскольку по крайней мере один лист имеет слишком большую глубину, чтобы включить его в эту сумму). O ( log n ) log 2 ( n c + 1 ) = ( c + 1 ) log 2 n 1 / n v d ( v ) ≤ ( c + 1 ) log 2 n ∑ v l o w d e p t h l e a f 2 - d ( $n^c$$O(\log n)$$\log_2(n^{c+1}) = (c+1) \log_2 n$$1/n$$v$$d(v)\leq (c+1) \log_2 n$$\sum_{v\mathrm{\ low \ depth \ leaf}} 2^{-d(v)} > 1-\frac{1}{n}$$\sum_{v\mathrm{\ low\ depth\ leaf}} 2^{-d(v)} < 1$

Довольно легко показать, что для получения суммы чисел строго между и нам нужно по крайней мере из них. Это показывает, что существуют пути с ветвящимися узлами.$2^{-k}$$1$$1-\frac{1}{n}$$\log_2 n$$\Omega(\log n)$$O(\log n)$