Quais combinações de sequencialização pré, pós e ordem são únicas?

28

Sabemos pós-encomenda,

post L(x)     => [x]
post N(x,l,r) => (post l) ++ (post r) ++ [x]

e pré-encomenda

pre L(x)     => [x]
pre N(x,l,r) => [x] ++ (pre l) ++ (pre r)

e passagem em ordem resp. sequencialização.

in L(x)     => [x]
in N(x,l,r) => (in l) ++ [x] ++ (in r)

Pode-se ver facilmente que nenhuma delas descreve uma dada árvore de maneira única, mesmo que assumamos chaves / rótulos distintos aos pares.

Quais combinações dos três podem ser usadas para esse fim e quais não podem?

As respostas positivas devem incluir um algoritmo (eficiente) para reconstruir a árvore e uma prova (idéia) de por que ela está correta. Respostas negativas devem fornecer exemplos contrários, ou seja, árvores diferentes que tenham a mesma representação.

Rafael
fonte

Respostas:

16

Primeiro, vou assumir que todos os elementos são distintos. Nenhuma quantidade de sequencializações lhe dirá a forma de uma árvore com elementos [3,3,3,3,3]. É possível reconstruir algumas árvores com elementos duplicados, é claro; Não sei que condições suficientes existem.

Continuando com os resultados negativos, você não pode reconstruir completamente uma árvore binária apenas a partir de suas seqüências de pré e pós-ordem. [1,2]pré [2,1]- encomenda, a pós-encomenda deve ter 1na raiz, mas 2pode ser a criança esquerda ou a criança certa. Se você não se importa com essa ambiguidade, pode reconstruir a árvore com o seguinte algoritmo:

  • Seja o percurso de pré-ordem e [ y n , , y 1 ] seja o percurso de pós-ordem. Devemos ter x 1 = y 1 , e esta é a raiz da árvore.[x1,,xn][yn,,y1]x1=y1
  • é o filho mais à esquerda da raiz e y 2 é o filho mais à direita. Se x 2 = y 2 , o nó raiz é unário; recursione sobre [ x 2 , , x n ] e [ y n , , y 2 ] para criar a única subárvore.x2y2x2=y2[x2,,xn][yn,,y2]
  • Caso contrário, deixa e j são os índices de tal modo que x 2 = y i e y 2 = x j . [ x 2 , , x j - 1 ] é a travessia de pré-ordem da subárvore esquerda, [ x j , , x n ] a da subárvore direita e da mesma forma para as travessias de pós-ordem. A subárvore esquerda tem j - 2 = n - i +Eujx2=yiy2=xj[x2,,xj1][xj,,xn] elementos e a subárvore direita possui i - 2 = n - j + 1 elementos. Recursar uma vez para cada subárvore. A propósito, esse método generaliza para árvores com ramificações arbitrárias. Com ramificações arbitrárias, descubra a extensão da subárvore esquerda e recorte seuselementos j - 2 de ambas as listas, depois repita para cortar a segunda subárvore da esquerda e assim por diante.j2=ni+1i2=nj+1
    j2

Como afirmado, o tempo de execução é com Θ ( n 2 ) no pior caso (no caso de dois filhos, pesquisamos cada lista linearmente). Você pode transformar isso em O ( nO(n2)Θ(n2) se você pré-processar as listas para criar um nO(nlg(n)) estrutura finita do mapa, dos valores dos elementos às posições nas listas de entrada. Também use uma matriz ou mapa finito para ir de índices a valores; atenha-se aos índices globais, para que as chamadas recursivas recebam todos os mapas e tomem um intervalo como argumento para saber em que agir.nlg(n)

Com o percurso de pré-ordem e o percurso em ordem [ z 1 , , z n ] , você pode reconstruir a árvore da seguinte maneira:[x1,,xn][z1,,zn]

  • A raiz é a cabeça da passagem de pré-ordem .x1
  • Seja o índice tal que z k = x 1 . Então [ z 1 , , z k - 1 ] é a travessia em ordem do filho esquerdo e [ z k + 1 , , z n ] é a travessia em ordem do filho certo. Indo pelo número de elementos, [ x 2 , , x k ] é a travessia de pré-ordem do filho esquerdo e [ x kkzk=x1[z1,,zk1][zk+1,,zn][x2,,xk]o da criança certa. Recomenda-se criar as subárvores esquerda e direita.[xk+1,,xn]

Novamente, esse algoritmo é conforme declarado, e pode ser executado em O ( nO(n2) se a lista for pré-processada em um mapa finito de valores a posições.O(nlg(n))

A pós-ordem e a ordem são obviamente simétricas.

Gilles 'SO- parar de ser mau'
fonte
Existe um erro de digitação aqui: "[1,2] pré-encomenda, [1,2] pós-pedido precisa ter 1 na raiz, mas 2 pode ser o filho esquerdo ou o filho certo." a árvore seria [2,1] e não [1,2] se 2 é um filho esquerdo ou direito. Além disso, você quer dizer se a pré-encomenda e a pós-encomenda são fornecidas, não podemos reconstruir a árvore, ou você quer dizer que se recebermos apenas uma delas, não podemos reconstruir a árvore?
CEGRD
@CEGRD De fato, a encomenda foi um erro de digitação. O exemplo mostra que você não pode reconstruir completamente a árvore neste caso: não é possível saber se 2é um filho esquerdo ou um filho direito. Isso corresponde ao caso "subárvore única" do algoritmo de reconstrução.
Gilles 'SO- stop be evil'
como isso muda se sabemos que é uma árvore de pesquisa binária? para o caso simples em seu exemplo ([1,2] pré-encomenda, [2,1] pós-ordem), poderíamos determinar que a raiz é 1 e que 2 é o filho certo (porque 2 é maior que 1) ... direito?
fersarr