El mejor caso "altura de sesgo" de un árbol arbitrario

Question

Dado un árbol binario arbitrario en $ n $ nodos, elija una asignación $ a $ de cada uno padre a uno de sus hijos (el "hijo favorito" como era). Definimos la altura del sesgo del árbol como $ h_a (\ mathsf {nil})= 0 $ y $ h_a (\ mathsf {nodo} \; a \; b)=max (h_a (a), h_a (b) +1) $ si $ a (\ mathsf {nodo } \; A \; B)= A $ es el niño favorito y el "contenedor de matemáticas" para niños y simétricos favoritos "> $ \ max (H_A (A) +1, H_A (B)) $ Si $ b $ es favorecido.

La pregunta es: para un árbol fijo $ t $ , ¿cuál es la altura mínima de sesgo sobre todas las tareas? Me gustaría obtener un ligado asintótico en $ f (n)=max_ {| t |= n} \ min_ah_a (t) $ .

Otras variaciones sobre este problema. Estoy interesado en que los árboles no son binarios (pero todavía hay un niño favorecido y todos los demás agregan uno a la altura), y cuando hay compartir (es decir, es un DAG), que no afecta el cálculo de la altura, pero permite "árboles" mucho más anchos mientras se mantiene bajo el $ n $ nodo enlazado.

Los límites obvios son $ f (n)=omega (\ log n) $ y $ f (n )= O (n) $ . Mi conjetura es que $ f (n)=theta (\ log n) $ para árboles binarios, y $ f ( n)=theta (\ sqrt n) $ para DAGS (con algún tipo de gráfico de cuadrícula como contraejemplo).

Answer 1

Para un árbol binario, deja $ h (t)=min_ah_a (t) $ , donde $ A $ rangos sobre todas las asignaciones favoritas de niños de $ t $ . Llama $ h (t) $ la altura skew de $ t $ .

Aquí hay una simple observación. La altura del sesgo de un árbol binario perfecto de la altura (ordinaria) $ n $ es $ n $ , también .

Para un árbol binario $ t $ , un borde se llama borde pasajero si uno de los puntos finales tiene exactamente un niño. Llamamos a un árbol binario $ m $ a b-menor de $ t $ si $ m $ se puede obtener eliminando un subárbol o contratando un borde que pasa repetidamente.

Para un árbol binario $ t $ , ¿cuál es su altura de sesgo? Aquí hay una caracterización visual.

la altura del sesgo de $ t $ es la altura máxima (ordinaria) de todos los árboles binarios perfectos que también son b-menores de $ t $ . hablar intuitivamente, un árbol binario es de sesgo de altura $ s $ $ \ iff $ it" contiene "un árbol binario perfecto de altura ordinaria $ s $ .

Prueba. Dado que tanto la eliminación de un subárbol y la contratación de un borde de paso no aumentan la altura del sesgo, $$ h (t) \ ge \ max_ { M \ texto {es un b-menor de t}} \ mathsf {altura} (m), $$ donde $ \ mathsf {altura} (\ cdot) $ es la altura (ordinaria) de un árbol. Por otro lado, mediante la inducción sobre el número de nodos de $ t $ , podemos mostrar que un árbol binario de skew height $ s $ debe contener un B-Minor que es un árbol binario perfecto de altura ordinaria $ s $ . $ \ quad \ checkmark $ .

---

Recordar que $ n $ es el número de nodos en $ t $ . Tenemos, $$ h (t) \ le \ lceil \ log_2 (n + 1) \ rceil - 1. $$ Prueba. inducción en $ n $ . El caso base, $ n= 1 $ es fácil de verificar.

Supongamos que es cierto si el número de nodos en $ t $ es más pequeño que $ n $ . Considere un árbol binario $ t $ de $ n $ nodos con nodo raíz $ r $ .

• si $ r $ tiene un solo hijo, por ejemplo, $ a $ , luego $$ h (t)= h (\ texto {el subárbol enraizado en} a) \ le \ lceil \ log_2 ((n-1) +1) \ rceil - 1 \ le \ lceil \ log_2 (n + 1) \ rceil - 1. $$
• si $ r $ tiene dos hijos, dicen, $ a $ y $ b $ . Dado que la cantidad de nodos en el subárbol enraizado en $ a $ y el subárbol enraizado en $ b $ es $ n-1 $ , uno de los subárboles tiene en la mayoría $ \ lfloor (n-1) / 2 \ rfloor $ nodos. Wlog, supongamos que es el subárbol enraizado en $ b $ . Luego $$ h (t)=max (H (\ texto {el subárbol enraizado en} a) + 1, h (\ texto {el subárbol enraizado en} b)) \\ \ le \ max (\ lceil \ log_2 (\ lfloor (N-1) / 2 \ rfloor + 1) \ rceil, \ lceil \ log_2 ((N-2) +1) \ rceil -1) $$ Desde $$ \ lceil \ log_2 (\ lfloor (n-1) / 2 \ rfloor + 1) \ rceil=lceil \ log_2 (\ lfloor (N + 1) / 2 \ rfloor) \ rceil=lceil \ log_2 (n + 1) \ rceil-1, $$ Tenemos $ h (t) \ le \ lceil \ log_2 (n + 1) \ rceil-1. $ $ \ Quad \ Checkmark $

---

Recordar que $ f (n)=max_ {t \ texto {es un árbol binario y} | t |= n} h (t) $ . La sección anterior ha demostrado $ f (n) \ le \ lceil \ log_2 (n + 1) \ rceil-1 $ .

Por otro lado, el peso sesgado del árbol binario perfecto con $ 2 ^ m-1 $ nodo es $ M-1 $ . Por eso, $$ f (n)=lceil \ log_2 (n + 1) \ rceil-1. $$