Melhor caso "altura de inclinação" de uma árvore arbitrária

Question

Dada uma árvore binária arbitrária na $ n $ nós, escolha uma atribuição $ a $ de cada pai a um de seus filhos (a "criança favorecida" como era). Definimos a altura do espeto da árvore como $ h_a (\ mathsf {nil})= 0 $ e $ h_a (\ mathsf {nó} \; a \; b)=max (h_a (a), h_a (b) +1) $ se $ a (\ mathsf {nó } \; a \; b)= a $ é a criança favorita e simetricamente $ \ max (h_a (A) +1, h_a (b)) $ Se $ B $ é favorecido.

A questão é: para uma árvore fixa $ t $ , qual é a altura mínima inclinação sobre todas as atribuições? Eu gostaria de obter um limite assintótico em $ f (n)=max_ {| t |= n} \ min_ah_a (t) $ .

Outras variações sobre este problema que estou interessado são quando as árvores não são binárias (mas ainda há uma criança favorecida e todas as outras adicionam uma para a altura), e quando há compartilhamento (ou seja, é um DAG), O que não afeta a cálculo de altura, mas permite "árvores" muito mais amplas enquanto permanece sob a $ n $ nó ligado.

Os limites óbvios são $ F (n)=ômega (\ log n) $ e $ f (n )= O (n) $ . Meu palpite é que $ f (n)=theta (\ log n) $ para árvores binárias, e $ f ( n)=theta (\ sqrt n) $ para dags (com algum tipo de grade gráfico como contra-exemplo).

Answer 1

para uma árvore binária, deixe $ h (t)=min_ah_a (t) $ , onde $ a $ intervalos sobre todas as atribuições favoritas de criança de $ t $ . Chame $ h (t) $ a altura de inclinação de $ t $ .

Aqui está uma observação simples. A altura inclinada de uma árvore binária perfeita de altura (comum) $ n $ é $ n $ também .

Para uma árvore binária $ t $ , uma borda é chamada de borda passageira se um dos pontos de extremidade tiver exatamente uma criança. Chamamos uma árvore binária $ m $ um B-menor de $ t $ se $ m $ pode ser obtido removendo uma subárvore ou contratando uma borda passageira repetidamente.

Para uma árvore binária $ t $ , qual é a sua altura de inclinação? Aqui está uma caracterização visual.

a altura de inclinação da $ t $ é a altura máxima (comum) de todas as árvores binárias perfeitas que também são b-menores de $ t $ . Intuitivamente falando, uma árvore binária é de altura de inclinação $ S $ $ \ iff $ IT" contém "uma árvore binária perfeita da altura comum $ S $ .

Prova. Desde que ambos removem uma subárvore e contratam uma borda de passagem não aumentam a altura de inclinação, $$ H (T) \ GE \ MAX_ { M \ text {é um b-menor de t}} \ mathsf {alture} (m), $$ onde $ \ mathsf {altura} (\ Cdot) $ é a altura (comum) de uma árvore. Por outro lado, por indução sobre o número de nós de $ T $ , podemos mostrar que uma árvore binária de altura de inclinação $ S $ deve conter um B-Minor que é uma árvore binária perfeita da altura comum $ S $ . $ \ Quad \ Checkmark $ .

---

.

Lembre-se de que $ n $ é o número de nós na $ t $ . Nós temos, $$ h (t) \ le \ lceil \ log_2 (n + 1) \ rceil - 1 $$ Prova. Indução na $ N $ . A caixa de base, $ n= 1 $ é fácil de verificar.

Suponha que seja verdade se o número de nós na $ t $ é menor que $ n $ . Considere uma árvore binária $ t $ de $ n $ nós com nó raiz $ R $ .

• se $ R $ tem apenas uma criança, digamos, $ a $ , então $$ h (t)= h (\ text {a subárvore enraizada no} a) \ le \ lceil \ log_2 ((n-1) +1) \ rceil - 1 \ le \ lceil \ rceil log_2 (n + 1) \ rceil - 1 $$
• se $ R $ tem dois filhos, digamos, $ a $ e $ B $ . Desde o número de nós na subárvore enraizada na $ a $ e a subárvore enraizada na $ B $ é $ n-1 $ , uma das subárdicas tem no máximo $ \ lFloor (N-1) / 2 \ RFloor $ Nós nós. Wlog, suponha que seja a subárvore enraizada na $ B $ . Então $$ h (t)=max (h (\ text {a subárvore enraizada em} a) + 1, h (\ text {a subárvore enraizada em} 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 \ rbroor) \ rceil=lceil \ log_2 (n + 1) \ rceil-1, $$ Temos $ h (t) \ le \ lceil \ log_2 (n + 1) \ rceil-1. $ $ \ Quad \ Checkmark $

---

.

Lembre-se de que $ f (n)=max_ {t \ text {é uma árvore binária e} | t |= n} h (t) $ . A seção acima provou $ f (n) \ le \ lceil \ log_2 (n + 1) \ rceil-1 $ .

Por outro lado, o peso inclinado da árvore binária perfeita com $ 2 ^ m-1 $ nó é $ m-1 $ . Por isso, $$ f (n)=lceil \ log_2 (n + 1) \ rceil-1. $$