Travessia da árvore - Tree traversal

Na ciência da computação , travessia de árvore (também conhecido como busca em árvore e caminhada na árvore ) é uma forma de travessia de gráfico e se refere ao processo de visitar (por exemplo, recuperar, atualizar ou excluir) cada nó em uma estrutura de dados em árvore , exatamente uma vez. Essas travessias são classificadas pela ordem em que os nós são visitados. Os algoritmos a seguir são descritos para uma árvore binária , mas também podem ser generalizados para outras árvores.

Tipos

Ao contrário de listas vinculadas , matrizes unidimensionais e outras estruturas de dados lineares , que são percorridas canonicamente em ordem linear, as árvores podem ser percorridas de várias maneiras. Eles podem ser percorridos em primeira ordem de profundidade ou em amplitude . Existem três maneiras comuns de percorrê-los em profundidade - primeira ordem: no pedido, pré-pedido e pós-pedido. Além dessas travessias básicas, vários esquemas mais complexos ou híbridos são possíveis, como pesquisas de profundidade limitada, como pesquisa iterativa de aprofundamento em primeiro lugar . A última, bem como a pesquisa em largura, também pode ser usada para percorrer árvores infinitas, veja abaixo .

Estruturas de dados para travessia de árvore

Percorrer uma árvore envolve iterar todos os nós de alguma maneira. Como a partir de um determinado nó há mais de um próximo nó possível (não é uma estrutura de dados linear), então, assumindo computação sequencial (não paralela), alguns nós devem ser adiados - armazenados de alguma forma para visita posterior. Isso geralmente é feito por meio de uma pilha (LIFO) ou fila (FIFO). Como uma árvore é uma estrutura de dados autorreferencial (definida recursivamente), a travessia pode ser definida por recursão ou, mais sutilmente, correcursão , de uma forma muito natural e clara; nesses casos, os nós adiados são armazenados implicitamente na pilha de chamadas .

A pesquisa em profundidade é facilmente implementada por meio de uma pilha, incluindo recursivamente (por meio da pilha de chamadas), enquanto a pesquisa em largura é facilmente implementada por meio de uma fila, incluindo co-cursivamente.

Pesquisa em profundidade

Travessia em profundidade (caminho pontilhado) de uma árvore binária:

Na pesquisa em profundidade (DFS), a árvore de pesquisa é aprofundada tanto quanto possível antes de ir para o próximo irmão.

Para percorrer árvores binárias com pesquisa em profundidade, execute as seguintes operações em cada nó:

Se o nó atual estiver vazio, retorne.
Execute as três operações a seguir em uma determinada ordem:

N: Visite o nó atual.

L: Percorre recursivamente a subárvore esquerda do nó atual.

R: Percorre recursivamente a subárvore direita do nó atual.

Existem três métodos em que a posição da travessia em relação ao nó (na figura: vermelho, verde ou azul) a visita do nó deve ocorrer. A escolha de exatamente uma cor determina exatamente uma visita de um nó conforme descrito abaixo. A visita em todas as três cores resulta em uma visita tripla do mesmo nó, produzindo a sequencialização "em toda a ordem":

F - B - A - A - A - B - D - C - C - C - D - E - E - E - D - B - F - G - G - I - H - H - H - I - I - G - F

Pré-encomenda, NLR

Visite o nó atual (na figura: posição vermelha).
Percorra recursivamente a subárvore esquerda do nó atual.
Percorre recursivamente a subárvore direita do nó atual.

O percurso da pré-ordem é classificado topologicamente , porque um nó pai é processado antes que qualquer um de seus nós filho seja concluído.

Pós-pedido, LRN

Percorra recursivamente a subárvore esquerda do nó atual.
Percorre recursivamente a subárvore direita do nó atual.
Visite o nó atual (na figura: posição azul).

O traço de uma travessia é chamado de sequencialização da árvore. O traço transversal é uma lista de cada nó visitado. Nenhuma sequencialização de acordo com a pré, ordem ou pós-ordem descreve a árvore subjacente de maneira única. Dada uma árvore com elementos distintos, tanto a pré-ordem quanto a pós-ordem combinadas com a ordem são suficientes para descrever a árvore de maneira única. No entanto, a pré-encomenda com a pós-encomenda deixa alguma ambiguidade na estrutura da árvore.

Em ordem, LNR

Percorra recursivamente a subárvore esquerda do nó atual.
Visite o nó atual (na figura: posição verde).
Percorre recursivamente a subárvore direita do nó atual.

Em uma árvore de pesquisa binária ordenada de forma que em cada nó a chave seja maior que todas as chaves em sua subárvore esquerda e menor que todas as chaves em sua subárvore direita, a travessia em ordem recupera as chaves em ordem de classificação crescente .

Pré-encomenda reversa, NRL

Visite o nó atual.
Percorre recursivamente a subárvore direita do nó atual.
Percorra recursivamente a subárvore esquerda do nó atual.

Pós-pedido reverso, RLN

Percorre recursivamente a subárvore direita do nó atual.
Percorra recursivamente a subárvore esquerda do nó atual.
Visite o nó atual.

Reverter em ordem, RNL

Percorre recursivamente a subárvore direita do nó atual.
Visite o nó atual.
Percorra recursivamente a subárvore esquerda do nó atual.

Em uma árvore de pesquisa binária ordenada de forma que em cada nó a chave seja maior do que todas as chaves em sua subárvore esquerda e menor que todas as chaves em sua subárvore direita, a travessia reversa em ordem recupera as chaves em ordem decrescente de classificação.

Árvores arbitrárias

Para percorrer árvores arbitrárias (não necessariamente árvores binárias) com pesquisa em profundidade, execute as seguintes operações em cada nó:

Se o nó atual estiver vazio, retorne.
Visite o nó atual para uma passagem de pré-encomenda.
Para cada i de 1 ao número de subárvores do nó atual - 1, ou do último para o anterior para travessia reversa, faça:
1. Percorra recursivamente a i -ésima subárvore do nó atual .
2. Visite o nó atual para uma travessia em ordem.
Percorre recursivamente a última subárvore do nó atual.
Visite o nó atual para travessia pós-pedido.

Dependendo do problema em questão, a pré-encomenda, a pós-encomenda e, especialmente, um do número de subárvores - 1 operações na ordem podem ser opcionais. Além disso, na prática, mais de uma das operações de pré-pedido, pós-pedido e ordem podem ser necessárias. Por exemplo, ao inserir em uma árvore ternária, uma operação de encomenda é realizada comparando os itens. Uma operação de pós-pedido pode ser necessária posteriormente para reequilibrar a árvore.

Pesquisa abrangente

Ordem de nível : F, B, G, A, D, I, C, E, H.

Na pesquisa em largura (BFS) ou na pesquisa de ordem de nível , a árvore de pesquisa é ampliada tanto quanto possível antes de ir para a próxima profundidade.

Outros tipos

Existem também algoritmos de travessia de árvore que não são classificados como pesquisa em profundidade nem pesquisa em largura. Um desses algoritmos é a pesquisa em árvore de Monte Carlo , que se concentra na análise dos movimentos mais promissores, baseando a expansão da árvore de pesquisa em uma amostragem aleatória do espaço de pesquisa.

Formulários

Árvore que representa a expressão aritmética: A * ( B - C ) + ( D + E )

A travessia de pré-ordem pode ser usada para fazer uma expressão de prefixo ( notação polonesa ) a partir de árvores de expressão : percorrer a árvore de expressão de maneira pré-ordenada. Por exemplo, percorrer a expressão aritmética representada na pré-encomenda resulta em "+ * A - B C + D E ".

A travessia pós-ordem pode gerar uma representação pós-fixada ( notação polonesa reversa ) de uma árvore binária. Percorrer a expressão aritmética representada na pós-ordem resulta em " A B C - * D E + +"; o último pode ser facilmente transformado em código de máquina para avaliar a expressão por uma máquina de pilha .

A travessia em ordem é muito comumente usada em árvores de pesquisa binária porque retorna valores do conjunto subjacente em ordem, de acordo com o comparador que configurou a árvore de pesquisa binária.

A travessia pós-pedido durante a exclusão ou liberação de nós e valores pode excluir ou liberar uma árvore binária inteira. Assim, o nó é liberado após liberar seus filhos.

Além disso, a duplicação de uma árvore binária produz uma sequência de ações pós-ordem, porque a cópia do ponteiro para a cópia de um nó é atribuída ao campo filho correspondente N.child dentro da cópia do pai N imediatamente após a returncópia no procedimento recursivo . Isso significa que o pai não pode terminar antes que todos os filhos tenham terminado.

Implementações

Pesquisa em profundidade

Pedido antecipado

procedure preorder(node)
    if node = null
        return
    visit(node)
    preorder(node.left)
    preorder(node.right)

procedure iterativePreorder(node)
    if node = null
        return
    stack ← empty stack
    stack.push(node)
    while not stack.isEmpty()
        node ← stack.pop()
        visit(node)
        // right child is pushed first so that left is processed first
        if node.right ≠ null
            stack.push(node.right)
        if node.left ≠ null
            stack.push(node.left)

Se a árvore for representada por uma matriz (o primeiro índice é 0), é possível calcular o índice do próximo elemento:

procedure bubbleUp(array, i, leaf)
    k ← 1
    i ← (i - 1)/2
    while (leaf + 1) % (k * 2) ≠ k
        i ← (i - 1)/2
        k ← 2 * k
    return i

procedure preorder(array)
    i ← 0
    while i ≠ array.size
        visit(array[i])
        if i = size - 1
            i ← size
        else if i < size/2
            i ← i * 2 + 1
        else
            leaf ← i - size/2
            parent ← bubble_up(array, i, leaf)
            i ← parent * 2 + 2

Pós-pedido

procedure postorder(node)
    if node = null
        return
    postorder(node.left)
    postorder(node.right)
    visit(node)

procedure iterativePostorder(node)
    stack ← empty stack
    lastNodeVisited ← null
    while not stack.isEmpty() or node ≠ null
        if node ≠ null
            stack.push(node)
            node ← node.left
        else
            peekNode ← stack.peek()
            // if right child exists and traversing node
            // from left child, then move right
            if peekNode.right ≠ null and lastNodeVisited ≠ peekNode.right
                node ← peekNode.right
            else
                visit(peekNode)
                lastNodeVisited ← stack.pop()

Em ordem

procedure inorder(node)
    if node = null
        return
    inorder(node.left)
    visit(node)
    inorder(node.right)

procedure iterativeInorder(node)
    stack ← empty stack
    while not stack.isEmpty() or node ≠ null
        if node ≠ null
            stack.push(node)
            node ← node.left
        else
            node ← stack.pop()
            visit(node)
            node ← node.right

Avançando para o próximo nó ou nó anterior

O nodepara começar com pode ter sido encontrado na árvore de pesquisa binária bstpor meio de uma função de pesquisa padrão , que é mostrada aqui em uma implementação sem ponteiros pai, ou seja, usa um stackpara manter os ponteiros ancestrais.

procedure search(bst, key)
    // returns a (node, stack)
    node ← bst.root
    stack ← empty stack
    while node ≠ null
        stack.push(node)
        if key = node.key
            return (node, stack)
        if key < node.key
            node ← node.left    
        else
            node ← node.right
    return (null, empty stack)

A função inorderNext retorna um no-fim-vizinho node, ou o in-ordem- suc cessora (para dir=1) ou a in-ordem- prede cessora (para dir=0), eo atualizada stack, para que a árvore de busca binária pode ser sequencialmente in- a ordem é percorrida e pesquisada na direção fornecida dirmais adiante.

procedure inorderNext(node, dir, stack)
    newnode ← node.child[dir]
    if newnode ≠ null
        do
            node ← newnode
            stack.push(node)
            newnode ← node.child[1-dir]
        until newnode = null
        return (node, stack)
    // node does not have a dir-child:
    do
        if stack.isEmpty()
            return (null, empty stack)
        oldnode ← node
        node ← stack.pop()   // parent of oldnode
    until oldnode ≠ node.child[dir]
    // now oldnode = node.child[1-dir],
    // i.e. node = ancestor (and predecessor/successor) of original node
    return (node, stack)

Observe que a função não usa chaves, o que significa que a estrutura sequencial é completamente gravada pelas arestas da árvore de busca binária. Para travessias sem mudança de direção, a complexidade média ( amortizada ) ocorre porque uma travessia completa dá passos para um BST de tamanho 1 para a borda acima e 1 para a borda abaixo. O pior caso de complexidade é com a altura da árvore. ${\ displaystyle {\ mathcal {O}} (1),}$ ${\ displaystyle 2n-2}$ ${\ displaystyle n,}$ ${\ displaystyle {\ mathcal {O}} (h)}$ ${\ displaystyle h}$

Todas as implementações acima requerem um espaço de pilha proporcional à altura da árvore, que é uma pilha de chamadas para as recursivas e uma pilha pai (ancestral) para as iterativas. Em uma árvore mal balanceada, isso pode ser considerável. Com as implementações iterativas, podemos remover o requisito de pilha mantendo ponteiros pais em cada nó ou encadeando a árvore (próxima seção).

Percurso em ordem de Morris usando threading

Uma árvore binária é encadeada fazendo com que cada ponteiro filho esquerdo (que de outra forma seria nulo) aponte para o predecessor em ordem do nó (se existir) e cada ponteiro filho direito (que de outra forma seria nulo) aponte para o in- sucessor de ordem do nó (se existir).

Vantagens:

Evita a recursão, que usa uma pilha de chamadas e consome memória e tempo.
O nó mantém um registro de seu pai.

Desvantagens:

A árvore é mais complexa.
Podemos fazer apenas uma travessia de cada vez.
É mais sujeito a erros quando os dois filhos não estão presentes e ambos os valores dos nós apontam para seus ancestrais.

Traversal de Morris é uma implementação de travessia em ordem que usa threading:

Crie links para o sucessor em ordem.
Imprima os dados usando esses links.
Reverta as alterações para restaurar a árvore original.

Pesquisa abrangente

Além disso, está listado abaixo um pseudocódigo para uma passagem de ordem de nível baseada em fila simples e exigirá espaço proporcional ao número máximo de nós em uma determinada profundidade. Isso pode ser até metade do número total de nós. Uma abordagem mais eficiente em termos de espaço para este tipo de travessia pode ser implementada usando uma pesquisa aprofundada em profundidade iterativa .

procedure levelorder(node)
    queue ← empty queue
    queue.enqueue(node)
    while not queue.isEmpty()
        node ← queue.dequeue()
        visit(node)
        if node.left ≠ null
            queue.enqueue(node.left)
        if node.right ≠ null
            queue.enqueue(node.right)

Se a árvore for representada por uma matriz (o primeiro índice é 0), é suficiente iterar por todos os elementos:

procedure levelorder(array)
    for i from 0 to array.size
        visit(array[i])

Árvores infinitas

Embora o percurso geralmente seja feito para árvores com um número finito de nós (e, portanto, profundidade finita e fator de ramificação finito ), também pode ser feito para árvores infinitas. Isso é de interesse particular na programação funcional (particularmente com avaliação preguiçosa ), já que estruturas de dados infinitas podem ser facilmente definidas e trabalhadas, embora não sejam (estritamente) avaliadas, pois isso levaria tempo infinito. Algumas árvores finitas são muito grandes para serem representadas explicitamente, como a árvore do jogo para xadrez ou go , e por isso é útil analisá-las como se fossem infinitas.

Um requisito básico para travessia é visitar cada nó eventualmente. Para árvores infinitas, algoritmos simples geralmente falham nisso. Por exemplo, dada uma árvore binária de profundidade infinita, uma pesquisa em profundidade irá descer um lado (por convenção, o lado esquerdo) da árvore, nunca visitando o resto, e de fato uma travessia em ordem ou pós-ordem nunca irá visite qualquer nó, uma vez que não atingiu uma folha (e de fato nunca o fará). Em contraste, uma travessia em largura (ordem de nível) percorrerá uma árvore binária de profundidade infinita sem problema e, de fato, percorrerá qualquer árvore com fator de ramificação limitado.

Por outro lado, dada uma árvore de profundidade 2, onde a raiz tem infinitos filhos, e cada um desses filhos tem dois filhos, uma pesquisa em profundidade visitará todos os nós, pois uma vez que esgota os netos (filhos dos filhos de um nó), ele passará para o próximo (assumindo que não seja pós-ordem, caso em que nunca atinge a raiz). Em contraste, uma busca abrangente nunca alcançará os netos, pois visa exaurir os filhos primeiro.

Uma análise mais sofisticada do tempo de execução pode ser fornecida por meio de números ordinais infinitos ; por exemplo, a pesquisa em largura da árvore de profundidade 2 acima levará ω · 2 etapas: ω para o primeiro nível e, em seguida, outro ω para o segundo nível.

Assim, pesquisas simples de profundidade ou largura primeiro não percorrem todas as árvores infinitas e não são eficientes em árvores muito grandes. No entanto, os métodos híbridos podem atravessar qualquer árvore infinita (contável), essencialmente por meio de um argumento diagonal ("diagonal" - uma combinação de vertical e horizontal - corresponde a uma combinação de profundidade e largura).

Concretamente, dada a árvore infinitamente ramificada de profundidade infinita, rotule a raiz (), os filhos da raiz (1), (2), ..., os netos (1, 1), (1, 2), ..., (2 , 1), (2, 2),… e assim por diante. Os nós estão, portanto, em uma correspondência um a um com sequências finitas (possivelmente vazias) de números positivos, que são contáveis e podem ser colocados em ordem primeiro pela soma das entradas e, em seguida, por ordem lexicográfica dentro de uma determinada soma (apenas finitamente muitas sequências somam um determinado valor, portanto, todas as entradas são alcançadas - formalmente, há um número finito de composições de um determinado número natural, especificamente 2 ^{n −1} composições de n ≥ 1 ), o que dá uma travessia. Explicitamente:

()
(1)
(1, 1) (2)
(1, 1, 1) (1, 2) (2, 1) (3)
(1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) (4)

etc.

Isso pode ser interpretado como mapear a árvore binária de profundidade infinita nesta árvore e, em seguida, aplicar a pesquisa em largura: substitua as bordas "para baixo" conectando um nó pai a seu segundo filho e as bordas "direitas" do primeiro filho ao segundo filho, do segundo filho ao terceiro filho, etc. Assim, em cada passo, pode-se descer (acrescentar um (, 1) ao final) ou ir para a direita (adicionar um ao último número) (exceto a raiz, que é extra e só pode descer), o que mostra a correspondência entre a árvore binária infinita e a numeração acima; a soma das entradas (menos um) corresponde à distância da raiz, o que concorda com os 2 ^{n −1} nós na profundidade n - 1 na árvore binária infinita (2 corresponde ao binário).

Referências

Fontes

Dale, Nell. Lilly, Susan D. "Pascal Plus Data Structures". DC Heath and Company. Lexington, MA. 1995. Quarta Edição.
Drozdek, Adam. "Estruturas de dados e algoritmos em C ++". Brook / Cole. Pacific Grove, CA. 2001. Segunda edição.
"Tree Transversal" (math.northwestern.edu)

Languages

In other projects

Travessia da árvore - Tree traversal

Conteúdo

Tipos

Estruturas de dados para travessia de árvore

Pesquisa em profundidade

Pré-encomenda, NLR

Pós-pedido, LRN

Em ordem, LNR

Pré-encomenda reversa, NRL

Pós-pedido reverso, RLN

Reverter em ordem, RNL

Árvores arbitrárias

Pesquisa abrangente

Outros tipos

Formulários

Implementações

Pesquisa em profundidade

Pedido antecipado

Pós-pedido

Em ordem

Avançando para o próximo nó ou nó anterior

Percurso em ordem de Morris usando threading

Pesquisa abrangente

Árvores infinitas

Referências

Fontes

links externos