Nel migliore dei casi “altezza di inclinazione” di un albero arbitrario

Question

Dato un albero binario arbitrario su $n$ nodi, scegli un compito $A$ da ciascun genitore a uno dei suoi figli (il "figlio favorito" per così dire).Definiamo l'altezza di inclinazione dell'albero come $H_A(\mathsf{nil})=0$ E $H_A(\mathsf{nodo}\;a\;b)=\max(H_A(a), H_A(b)+1)$ Se $A(\mathsf{nodo}\;a\;b)=a$ è il figlio prediletto e simmetricamente $\max(H_A(a)+1, H_A(b))$ Se $b$ è favorito.

La domanda è:Per un albero fisso $T$, qual è l'altezza di inclinazione minima su tutte le assegnazioni?Vorrei ottenere un limite asintotico $f(n)=\max_{|T|=n}\min_AH_A(T)$.

Altre variazioni di questo problema che mi interessano sono quando gli alberi non sono binari (ma c'è comunque un figlio favorito e tutti gli altri ne aggiungono uno all'altezza), e quando c'è condivisione (cioèè un dag), che non influisce sul calcolo dell'altezza ma consente "alberi" molto più ampi rimanendo sotto $n$ vincolato al nodo.

I limiti evidenti sono $f(n)=\Omega(\log n)$ E $f(n)=O(n)$.La mia ipotesi è questa $f(n)= heta(\log n)$ per alberi binari e $f(n)= heta(\sqrt n)$ per dag (con una sorta di grafico a griglia come controesempio).

Answer 1

Per un albero binario, poniamo $H(T)=\min_AH_A(T)$, Dove $A$ spazia su tutte le assegnazioni di figli favoriti di $T$.Chiamata $H(T)$ IL altezza inclinata di $T$.

Ecco una semplice osservazione.L'altezza inclinata di un albero binario perfetto di altezza (ordinaria). $n$ È $n$, pure.

Per un albero binario $T$, un arco è detto arco passante se uno degli estremi ha esattamente un figlio.Chiamiamo albero binario $M$ un si minore di $T$ Se $M$ può essere ottenuto rimuovendo un sottoalbero o contraendo ripetutamente un bordo passante.

Per un albero binario $T$, qual è la sua altezza di inclinazione?Ecco una caratterizzazione visiva.

L'altezza di inclinazione di $T$ è l'altezza massima (ordinaria) di tutti gli alberi binari perfetti che sono anche b-minori di $T$. Intuitivamente parlando, un albero binario ha un'altezza obliqua $s$ $\iff$ esso "contiene" un albero binario perfetto di altezza ordinaria $s$.

Prova. Poiché sia ​​la rimozione di un sottoalbero che la contrazione di un bordo di passaggio non aumentano l'altezza di inclinazione, $$H(T)\ge \max_{M ext{ è un si minore di T}}\mathsf{altezza}(M),$$ Dove $\mathsf{altezza}(\cdot)$ è l'altezza (ordinaria) di un albero.D'altra parte, per induzione sul numero di nodi di $T$, possiamo mostrare che un albero binario di altezza obliqua $s$ deve contenere un si minore che sia un albero binario perfetto di altezza ordinaria $s$. $\quadretto\segno di spunta$.

---

Richiama questo $n$ è il numero di nodi in $T$.Abbiamo,$$H(T) \le \lceil \log_2(n+1) ceil - 1.$$ Prova. Induzione attiva $n$.Il caso base, $n = 1$ è facile da verificare.

Supponiamo che sia vero se il numero di nodi in $T$ è più piccolo di $n$.Consideriamo un albero binario $T$ Di $n$ nodi con nodo radice $r$.

• Se $r$ ha un solo figlio, diciamo, $a$, Poi $$H(T)=H( ext{il sottoalbero con radice in } a)\le \lceil \log_2((n-1)+1) ceil - 1\le \lceil \log_2(n+1)\ rceil - 1.$$
• Se $r$ ha due figli, diciamo, $a$ E $b$.Poiché il numero di nodi nel sottoalbero ha la sua radice $a$ e il sottoalbero ha le sue radici $b$ È $n-1$, uno dei sottoalberi ha al massimo $\lpiano (n-1)/2 piano$ nodi.WLOG, supponiamo che sia il sottoalbero con radice $b$.Poi$$H(T)=\max(H( ext{il sottoalbero radicato in }a ) + 1, H( ext{il sottoalbero radicato in } b)) \\ \le \max(\lceil \log_2(\lfloor(n-1)/2 floor+1) ceil,\lceil \log_2((n-2)+1) ceil -1) $$Da $$ \lceil \log_2(\lfloor(n-1)/2 floor+1) ceil=\lceil \log_2(\lfloor(n+1)/2 floor) ceil=\lceil \log_2(n +1) ceil-1,$$abbiamo $H(T)\le \lceil \log_2(n+1) ceil-1.$ $\quadretto\segno di spunta$

---

Richiama questo $f(n)=\max_{T ext{ è un albero binario e }|T|=n}H(T)$.La sezione precedente lo ha dimostrato $f(n)\le \lceil\log_2(n+1) ceil-1$.

D'altra parte, il peso inclinato dell'albero binario perfetto con $2^m-1$ il nodo è $m-1$.Quindi,$$f(n)=\lceil\log_2(n+1) ceil-1.$$