Limite inférieure du nombre de chemins «courts» dans un arbre enraciné de taille polynomiale

Soit un arbre binaire enraciné. Chaque chemin de la racine de à une feuille a une longueur . Chaque nœud de a toujours un nœud enfant gauche et un droit, mais il est possible qu'ils soient identiques (il y a donc toujours chemins possibles). La taille de est délimitée par . Un nœud avec différents nœuds enfants est appelé nœud de branchement .$T$$T$$n$$T$$2^n$$T$$O(poly(n))$

Nous disons que deux chemins sont différents si il n'y a qu'un nœud de branchement partagé et un chemin va au nœud enfant gauche et l'autre chemin va au nœud enfant droit. Il est clair qu'il existe au moins un chemin dans avec des nœuds de branchement . Sinon , il y aurait trop de noeuds dans .$T$$O(\log n)$$T$

Y a-t-il une meilleure limite inférieure sur le nombre de chemins avec des nœuds de branchement si je sais qu'il y a des nœuds de branchement dans l'arborescence?$O(\log n)$$\omega(\log n)$

La limite inférieure est des chemins avec des nœuds de branchement , si vous avez au moins des nœuds de branchement dans l'arborescence.O ( log n ) Ω ( log n $\Omega(\log n)$$O(\log n)$$\Omega(\log n)$

Ceci peut être réalisé: utilisez un arbre qui a un long chemin (longueur ) dont tous les nœuds sont des nœuds de ramification, sans aucun autre nœud de ramification dans l'arbre.$n$

Voici un croquis de la borne inférieure.

Tout d'abord, compactez l'arbre en contractant tout nœud intérieur qui n'est pas un nœud de ramification. Si la taille d'origine de l'arborescence était , la nouvelle arborescence doit toujours être , puisque vous n'avez réduit que le nombre de nœuds. Maintenant, la profondeur d'une feuille est le nombre de nœuds de branchement sur le chemin d'origine vers cette feuille, et nous avons un arbre binaire complet (chaque nœud a un degré 2 ou 0). < n $< n^c$$< n^c$

S'il n'y a pas de feuilles de profondeur , alors le nombre de chemins est un de plus que le nombre de nœuds de branchement, qui est , donc nous pouvons supposer qu'au moins une feuille a profondeur .Ω ( log n ) Ω ( log n $\Omega(\log n)$$\Omega(\log n)$$\Omega(\log n)$

Rappelons ensuite l'inégalité de Kraft. Si la profondeur d'une feuille dans un arbre binaire complet est , alors .Σ v l e a f 2 - d ( v ) = $d(v)$$\Sigma_{v \mathrm{\ leaf}} 2^{-d(v)} = 1$

Maintenant, nous avons moins de feuilles. Nous voulons montrer que nous en avons beaucoup à la profondeur . Supposons que nous éliminions de la considération celles qui sont en profondeur au moins . Cela supprime au plus le poids de la somme de l'inégalité de Kraft, donc pour ces feuilles en profondeur au plus , nous avons . Nous avons également (car au moins une feuille a une profondeur trop grande pour être incluse dans cette somme). 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$

Il est assez facile de montrer que pour obtenir une somme de nombres strictement compris entre et , nous avons besoin d'au moins d'entre eux. Cela montre qu'il existe des chemins avec des nœuds de branchement .$2^{-k}$$1$$1-\frac{1}{n}$$\log_2 n$$\Omega(\log n)$$O(\log n)$