A ambiguidade com a Visão de Cima de uma árvore binária

Question

O que exatamente é a vista de topo de uma árvore binária?

Acho ótimo, ambigüidade e falta de clareza de artigos que eu encontrar.

Por exemplo, isto é o que é usado para demonstrar a vista de cima, em geeksforgeeks:

       1
    /     \
   2       3
  /  \    / \
 4    5  6   7

Eles dizem que a vista de cima é de 4 2 1 3 7.O problema aqui é que eles deixam um monte de especulação sobre o que não está a vista de cima.Consequentemente, torna-se ambíguo para implementar no código.

Stackoverflow exemplos não são melhores. Hackerrank's exemplo é ainda pior.

Então, eu me cadastrei aqui na esperança de que alguém vai me dizer explicitamente o que a vista de cima, é porque eu tenho estado a tentar descobrir por 2 dias.Por exemplo, qual é a visão de cima da árvore:

      1
       \
        14
       /  \
      3    15
     / \
    2   7
       /  \
      4     13
     / \   /
    5   6 10
         /  \
        8    11
         \    \
          9    12

E se eu pode ser ousados para pedir, por que é importante?

Answer 1

Aqui está uma observação importante em primeiro lugar.Não, a vista de topo de uma árvore binária NÃO é importante, no entanto, ele é definido.É apenas temporário, conceito definido por causa de problema, embora possa ser interessante.

Agora, há várias formas de definir a vista de topo de uma árvore binária.Não há nenhuma forma definitiva.Isso não é um problema, desde que o exercício/desafio/tarefa de definir o bem e de forma inequívoca.No entanto, este não é o caso com que HackerRank problema, que NÃO se define como um conceito ambíguo claramente.Na verdade, não existe uma definição rigorosa.O exemplo dado ajuda a pouco.Na verdade, o problema e seu mais novo juiz espera de nós para ver uma árvore binária de uma forma que é diferente da minha primeira reação, bem como Steven interpretação!Eu poderia culpar o autor de que o problema, que era inexperiente, ou não prestar atenção suficiente ao criar o problema.(Para ser justo, ele pode ser muito mais inteligente e prudente do que nós.Aparentemente, não sobre este problema, no entanto.De qualquer maneira, podemos agradecer-lhe, pelo menos, para contribuir para a HackerRank site, mesmo se esse problema faz mais mal do que o progresso).

Lição aprendida, novamente:nem todos os recursos na internet são de confiança ou importante.

---

Agora, deixe-me explicar o que significa que HackerRank problema, como engenharia reversa a partir de resultados esperados e o problema testador solução.

Suponha que nós já temos a árvore binária na forma de uma raiz, vértices e de pais de crianças entre os vértices.Por exemplo, raiz 1, os vértices 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 e 5.esquerda=1, 5.direita=10, 1.direita=2, 10.esquerda=6, 2.direita=3, 6.direita=7, 3.direita=4, 7.direito=8, 8.direita=9.Agora vamos colocar a raiz em algum lugar no nível 0.

           5

Agora vamos adicionar as crianças de 5, 1 e 10 no nível imediatamente abaixo.À esquerda da criança, 1, será mover uma unidade para a esquerda.O direito da criança, de 10 anos, vai ser transferido de uma unidade para a direita.

           5
        /     \
      1         10

Agora coloque 1 filhos e, em seguida, 10 crianças no nível seguinte.Como antes, o direito da criança de 1, 2, vai ser colocado a um nível abaixo e uma unidade para a direita para 1.A esquerda criança de 10, 6, será colocado um nível abaixo e uma unidade para a esquerda 10.Desde que o lugar já está ocupado por 2, nós apenas colocamos 6 no mesmo lugar, juntamente com 2.No entanto, 6 é considerado coberto, indicado pelos parênteses em torno de 6.

           5
        /     \
      1         10
        \     /
          2(6)

Agora vamos colocar 2 e 6 crianças no nível seguinte.Nota-se que 7 é coberto, porque 3 tem prioridade.

           5
        /     \
      1         10
        \     /
          2(6)
              \
               3(7)

Agora vamos colocar 3 e 7 crianças no nível seguinte.Observe que 8 é coberto.

           5
        /     \
      1         10
        \     /
          2(6)
              \
               3(7)
                   \
                    4(8)

Agora vamos colocar de 4 e 8 filhos no próximo nível.Bem, desde 4 de não ter filhos, o direito da criança de 8, 9 não está coberto qualquer mais.

           5
        /     \
      1         10
        \     /
          2(6)
              \
               3(7)
                   \
                    4(8)
                        \
                          9

Temos construído uma representação visual de uma árvore binária.Agora, podemos citar a declaração original de HackerRank, "vista de cima significa que quando você olhar a árvore a partir do topo, o que você vai ver vai ser chamado a vista de topo da árvore." A vista de cima, é 1, 5, 10, 4, 9.Outros nós são cobertas, tal como 8 ou bloqueado por nós acima deles, tais como 2 e 3, ou ambos, como 6 e 7.

A vista de cima da árvore em questão é 2, 1, 14, 15, 12.

A ilustração acima, deve ser claro o suficiente, pois tem explicado tudo claro casos.Os leitores são encorajados a formular uma definição rigorosa.

Answer 2

Eu acho que o que eles estão tentando definir é a seguinte.

Dada uma enraizada árvore binária $T$, deixe $V(T)$ o conjunto de vértices de $T$.Para $v \V(G)$, deixe $P_v$ o único caminho a partir da raiz de $T$ para $v$.Vamos chamar uma borda $(u,w) \em P_v$ um borda esquerda se $w$ é filho à esquerda de u $$, e um margem direita caso contrário.

Deixe $\ell_v$ e $r_v$ ser o número de bordas esquerda e direita em $P_v$, respectivamente, e definir $\delta(v) = \ell_v - r_v = 2\ell_v - |P_v|$.

Deixe $h(u)$ ser a profundidade do vértice u $$ no $T$ e definir $\Delta(v) = \{ \delta_u \, :u \V(T) \wedge h(u) < h(v) \}$.O vista de cima de $T$ é o conjunto $\{ v \V(T) :\delta_v ão\in \Delta(v) \}$.

No seu exemplo, a vista de cima seria $\{1, 2, 12, 14, 15 \}$.Em geral, você pode calcular a vista de cima, em $O(|V(T)|)$ tempo pensei que um preorder DFS visita.

Eu não tenho nenhuma idéia de por que isso é importante, desculpe.