Uma árvore pode ser atravessada sem recursão, pilha ou fila e apenas alguns ponteiros?

15

Meia década atrás, eu estava sentado em uma classe de estruturas de dados em que o professor oferecia crédito extra se alguém pudesse atravessar uma árvore sem usar recursão, pilha, fila etc. (ou qualquer outra estrutura de dados semelhante) e apenas alguns indicadores. Eu vim com o que eu pensava ser uma resposta óbvia a essa pergunta que foi finalmente aceita pelo professor. Eu estava sentado em uma aula de matemática discreta com outro professor do mesmo departamento - e ele afirmou que era impossível atravessar uma árvore sem recursão, pilha, fila etc., e que minha solução era inválida.

Então, é possível ou impossível? Por que ou por que não?

Edit: Para adicionar alguns esclarecimentos, eu implementei isso em uma árvore binária que tinha três elementos - os dados armazenados em cada nó e ponteiros para dois filhos. Minha solução pode ser estendida para árvores n-árias com apenas algumas alterações.

Meu professor de estruturas de dados não impôs restrições contra a mutação da árvore e, de fato, descobri mais tarde que sua própria solução era usar os ponteiros filhos para apontar de volta para a árvore em seu caminho. Meu discreto professor de matemática disse que qualquer mutação de uma árvore significa que ela não é mais uma árvore de acordo com a definição matemática de uma árvore; sua definição também impediria qualquer indicação para os pais - o que corresponderia ao caso em que eu a resolvi acima.

NL - Peça desculpas a Monica
fonte
3
Você precisa especificar as restrições. Posso mudar a árvore? Como a árvore é representada? (Por exemplo, cada nó possui um ponteiro pai para seu pai?) A resposta dependerá das restrições específicas; sem especificar essas restrições, esse não é um problema bem colocado.
DW
2
Eu acho que o contraint que os professores realmente queriam expressar era "com espaço adicional". Mas qual foi a sua solução, afinal? O(1)
Raphael

Respostas:

17

Muitas pesquisas nessa área foram realizadas, motivadas pelo método de "baratear" a travessia de árvores e estruturas gerais de listas no contexto da coleta de lixo.

Uma árvore binária encadeada é uma representação adaptada de árvores binárias onde alguns ponteiros nulos são usados ​​para vincular a nós sucessores na árvore. Esta informação extra pode ser usada para atravessar uma árvore sem pilha. No entanto, é necessário um bit extra por nó para distinguir threads de ponteiros filhos. Wikipedia: Tree_traversal

Até onde eu sei, as árvores binárias implementadas usando ponteiros da maneira usual (ponteiro esquerdo e direito por nó) podem ser percorridas usando o método de threads, em um método atribuído a Morris . Os ponteiros NIL são temporariamente reutilizados para encadear um caminho de volta à raiz. A parte inteligente é que, durante a travessia, é possível distinguir as arestas originais dos elos de encadeamento temporários, usando a forma como eles formam ciclos na árvore).

Boa parte: sem estrutura de dados extra. Parte ruim: levemente trapaceira, a pilha está dentro da árvore de uma maneira inteligente. Muito esperto.

Uma prova da pilha oculta é mostrada em P. Mateti e R. Manghirmalani: Algoritmo transversal de árvore de Morris reconsiderado DOI: 10.1016 / 0167-6423 (88) 90063-9

JM Morris: Atravessar árvores binárias de maneira simples e barata. IPL 9 (1979) 197-200 DOI: 10.1016 / 0020-0190 (79) 90068-1

Depois, há também a digitalização Lindstrom . Este método "gira" os três ponteiros envolvidos em cada nó (pai e dois filhos). Se você deseja executar qualquer algoritmo decente de pré-encomenda ou pós-encomenda, precisa de bits extras por nó. Se você quiser apenas visitar todos os nós (três vezes, mas nunca souber qual visita realizar), isso poderá ser feito sem os bits.

G. Lindstrom: estruturas de lista de varredura sem pilhas ou bits de tag. IPL 2 (1973) 47-51. DOI: 10.1016 / 0020-0190 (73) 90012-4

Talvez a maneira mais direta seja um método de Robson . Aqui, a pilha necessária para o algoritmo clássico é enfiada através das folhas.

JM Robson: Um algoritmo aprimorado para atravessar árvores binárias sem pilha auxiliar IPL 1 (1973) 149-152. 10.1016 / 0020-0190 (73) 90018-5

IPL = Cartas de processamento de informações

Hendrik Jan
fonte
Também gosto dessa solução, embora não seja nada que eu tenha inventado durante meu primeiro ano de aulas de ciência da computação. Sim, provavelmente trapaceando de acordo com as regras do meu professor.
NL - desculpe-se com Monica
2
Você pode fornecer links / referências para as estratégias?
Raphael
1
A parte realmente ruim desse método é que você não pode ter mais de uma travessia por vez.
Gilles 'SO- stop be evil' (
6

v

Yuval Filmus
fonte
Isso é semelhante à solução que o professor de estruturas de dados que propôs o problema usou para resolvê-lo. O discreto professor de matemática objetou que "isso se tornou um gráfico, e não uma árvore", se houver indicações para os pais.
NL - Peça desculpas a Monica no dia
@ NathanLiddle: Isso dependeria da definição de árvore usada (que você não forneceu). No "mundo real", a representação das árvores de Yuval é razoável, mesmo que a teoria dos grafos diga que as coisas que ele define não são árvores, é claro.
Raphael
@ Rafael Sim, e atende aos requisitos do professor original, por isso é uma resposta aceitável para mim.
NL - Desculpe-se com Monica
0

Minha solução foi uma travessia de primeira geração usando loops for-aninhados para forçar brutalmente a árvore. Isso não é eficiente de forma alguma e, de fato, uma estrutura de dados recursiva como uma árvore está implorando por uma passagem recursiva, mas a questão não era se uma árvore poderia ser atravessada com eficiência, é se isso era possível.

Pseudocode:
root = pointer root 
depth = integer 0
finished = bool false
//If we n-ary tree also track how many children have been found 
//on the node with the most children for the purposes of this psuedocode 
//we'll assume a binary tree and insert a magic number of 2 so that we 
//can use bitwise operators instead of integer division 
while(!finished)
    ++depth
    treePosition = pointer root
    finished = true;
    for i := 0..2**depth
        for j := 0..depth
            if (i & j) //bitwise operator explained below
                // if right child doesn't exist break the loop
                treePosition = treePosition.rightChild
            else
                // if left child doesn't exist break the loop
                treePosition = treePosition.leftChild
        if j has any children
            finished = false
            do anything else you want when visiting the node

Para os primeiros níveis, seria assim, como você pode ver, o operador bit a bit no pseudocódigo simplesmente decide uma curva à esquerda ou à direita em uma árvore binária:

2**1       0               1
2**2   00      01      10      11
2**3 000 001 010 011 100 101 110 111

Para n-ária, você usaria i% (maxChildren ** j) / j para determinar qual caminho seguir entre 0 e maxChildren.

Em cada nó no n-ário, você também precisa verificar se o número de filhos é maior que maxChildren e atualizá-lo adequadamente.

NL - Peça desculpas a Monica
fonte
Se você quisesse usar mais que o binário, seria necessário substituir o número mágico 2 por uma variável que seria incrementada para corresponder ao máximo de filhos que ele viu e, em vez de operadores bit a bit, seria necessário dividir pela mesma variável aumentada para o poder da profundidade da árvore onde você estava.
NL - Peça desculpas a Monica
Se bem entendi, esta solução usa mais de espaço adicional. Se a árvore estiver equilibrada, ela usa O ( lgO(1)O(lgn)O(1)O(n)O(1)espaço adicional "). Por exemplo, o que você faz se depthexceder a largura de int?
DW
DW, o professor que colocou o problema não colocou essa restrição no problema, e o que me incomodou tanto na minha discussão com o discreto professor de matemática é que NUNCA reconheceu que era possível atravessar uma árvore sem recursão, pilha, ou fila, qualquer que seja o custo. A única coisa que a minha solução demonstra é que é possível fazer nada de forma iterativa que pode ser feito de forma recursiva, mesmo se você remover opções para a pilha, fila, etc.
NL - Desculpe-se com Monica
Uma coisa é dizer que é insolúvel sem espaço adicional O (1); é outra completamente declarar o problema insolúvel sem recursão, pilha ou fila. E, na verdade, depois de ver meu código, o discreto professor de matemática ainda não concordava com o argumento, porque ele disse que "i" no primeiro loop for estava substituindo uma fila. Como é isso para cabeça-dura?
NL - Peça desculpas a Monica
1
@NathanLiddle, verifique novamente. Seu número inteiro item depthbits de largura. Se depthé (que poderia ser, em árvores desequilibradas), então você precisa Θ ( n ) espaço para armazenar o número inteiro , de modo que as necessidades de soluções mais do que OΘ(n)Θ(n)iO(1)