Límite inferior en el número de caminos "cortos" en un árbol enraizado con tamaño polinómico

10

Deje que sea ​​un árbol binario enraizado. Cada camino desde la raíz de hasta una hoja tiene una longitud . Cada nodo de siempre tiene un nodo hijo izquierdo y uno derecho, pero es posible que sean iguales (por lo que siempre hay rutas posibles). El tamaño de está limitado por . Un nodo con diferentes nodos secundarios se llama nodo de ramificación .TTnT2nTO(poly(n))

Decimos que dos rutas son diferentes si hay un nodo de ramificación compartido y una ruta va al nodo hijo izquierdo y la otra ruta va al nodo hijo derecho. Está claro que hay al menos una ruta en con nodos de ramificación. De lo contrario no habría demasiados nodos en .TO(logn)T

¿Hay un límite inferior mejor en el número de rutas con nodos de ramificación si sé que hay nodos de ramificación en el árbol?O(logn)ω(logn)

Marc Bury
fuente
@Marc: ¿La letra (5ta línea) obviamente proviene de `` demasiados nodos en '' (7ma línea)?T
Oleksandr Bondarenko
@Marc: ¿Podría, por favor, hacer más precisa su afirmación "dos rutas son diferentes si usan nodos secundarios diferentes en un nodo de ramificación". ¿Quiere decir que son diferentes si hay un nodo de ramificación en el que usan diferentes nodos secundarios?
Oleksandr Bondarenko
Edito la pregunta e intento hacerla más precisa.
Marc Bury
¿Qué pasa con el árbol que tiene una sola ruta ( nodos)? eso está permitido? n
Peter Shor
Esta es una buena pregunta. Está permitido, pero este no es el caso interesante :) Entonces deberíamos hacer un límite inferior en el número de nodos de ramificación en el árbol, por ejemplo, nodos de ramificación. ω(logn)
Marc Bury

Respuestas:

9

El límite inferior es rutas con nodos de ramificación , si tiene al menos nodos de ramificación en el árbol.O ( log n ) Ω ( log n )Ω(logn)O(logn)Ω(logn)

Esto se puede lograr: use un árbol que tenga una ruta larga (longitud ) cuyos nodos sean nodos de ramificación, sin otros nodos de ramificación en el árbol.n

Aquí hay un bosquejo del límite inferior.

Primero, compacte el árbol contrayendo cualquier nodo interior que no sea un nodo de ramificación. Si el tamaño original del árbol era , el nuevo árbol aún debe ser , ya que solo ha reducido el número de nodos. Ahora, la profundidad de una hoja es el número de nodos ramificados en la ruta original a esa hoja, y tenemos un árbol binario completo (cada nodo tiene un grado 2 o 0). < n c<nc<nc

Si no hay hojas de profundidad , entonces el número de caminos es uno más que el número de nodos de ramificación, que es , por lo que podemos suponer que al menos una hoja tiene profundidad .Ω ( log n ) Ω ( log n )Ω(logn)Ω(logn)Ω(logn)

A continuación, recuerde la desigualdad de Kraft. Si la profundidad de una hoja en un árbol binario completo es , entonces .Σ v l e a f 2 - d ( v ) = 1d(v)Σv leaf2d(v)=1

Ahora, tenemos menos de hojas. Queremos mostrar que tenemos muchos de ellos en profundidad . Supongamos que eliminamos de la consideración los que son de profundidad al menos . Esto elimina como máximo de la suma en la desigualdad de Kraft, por lo que para esas hojas en profundidad como máximo , tenemos . También tenemos (ya que al menos una hoja tiene una profundidad demasiado grande para ser incluida en esta suma).ncO(logn)log2(nc+1)=(c+1)log2n1/nvd(v)(c+1)log2nvlowdepthleaf2-d(v)<1v low depth leaf2d(v)>11nv low depth leaf2d(v)<1

Es bastante fácil demostrar que para obtener una suma de números estrictamente entre y , necesitamos al menos de ellos. Esto muestra que hay rutas con nodos de ramificación . 1 1 - 12k1 log2nΩ(logn)O(logn)11nlog2nΩ(logn)O(logn)

Peter Shor
fuente
Si alguien se pregunta por qué llamo desigualdad a una ecuación, la desigualdad de Kraft tiene un signo igual para árboles binarios completos .
Peter Shor
Gracias por esta buena respuesta. No conocía la desigualdad de Kraft hasta ahora. Desigualdad muy útil.
Marc Bury