Tudo o que precisa de saber sobre estruturas de dados em árvore

Quando aprender a codificar pela primeira vez, é comum aprender arrays como a “estrutura de dados principal”

Eventualmente, aprenderá sobre hash tables também. Se estiver a tirar uma licenciatura em Informática, terá de ter uma aula sobre estrutura de dados. Aprenderá também sobre linked listsqueues, e stacks. Essas estruturas de dados são chamadas estruturas de dados “lineares” porque todas elas têm um início e um fim lógicos.

Quando começamos a aprender sobre trees e graphs, pode tornar-se realmente confuso. Não armazenamos dados de uma forma linear. Ambas as estruturas de dados armazenam dados de uma forma específica.

Este post é para o ajudar a compreender melhor a Estrutura de Dados da Árvore e para esclarecer qualquer confusão que possa ter sobre ela.

Neste artigo, aprenderemos:

• O que é uma árvore
• Exemplos de árvores
• Terminologia de árvores e como funciona
• Como implementar estruturas de árvores em código.

Damos início a esta jornada de aprendizagem. 🙂

Definição

Ao iniciar a programação, é comum compreender melhor as estruturas de dados lineares do que estruturas de dados como árvores e gráficos.

As árvores são bem conhecidas como uma estrutura de dados não-linear. Não armazenam dados de uma forma linear. Organizam os dados hierarquicamente.

Vamos mergulhar em exemplos da vida real!

O que quero dizer quando digo de forma hierárquica?

Imagine uma árvore genealógica com relacionamentos de todas as gerações: avós, pais, filhos, irmãos, etc. Normalmente organizamos as árvores genealógicas hierarquicamente.

O desenho acima é a minha árvore genealógica. Tossico, Akikazu, Hitomi, e Takemi são os meus avós.

Toshiaki e Juliana são os meus pais.

TK, Yuji, Bruno, e Kaio são os filhos dos meus pais (eu e os meus irmãos).

A estrutura de uma organização é outro exemplo de hierarquia.

Em HTML, o Modelo de Objecto de Documento (DOM) funciona como uma árvore.

The HTML tag contém outras tags. Temos um head tag e um body tag. Essas etiquetas contêm elementos específicos. O head tag tem um e um title tags. O body tag tem elementos que mostram na interface do utilizador, por exemplo, h1ali, etc.

Uma definição técnica

A tree é um conjunto de entidades chamado nodes. Os nós são ligados por edges. Cada node contém um value ou data, e pode ou não ter um child node .

O first node do tree chama-se o root. Se este root node for ligado por outro node, o root é então um parent node e o ligado node é um child.

Todos Tree nodes estão ligados por links chamados edges. É uma parte importante de trees, porque gere a relação entre nodes.

Leaves são os últimos nodes num tree. São nós sem crianças. Como árvores reais, temos o rootbranches, e finalmente o leaves.

Outros conceitos importantes a compreender são height e depth.

O height de um tree é o comprimento do caminho mais longo para um leaf.

O depth de um node é o comprimento do caminho para o seu root.

Resumo terminológico

• Raiz é o mais alto node do tree
• Borda é a ligação entre dois nodes
• Criança é um node que tem um parent node
• Pai é a node que tem um edge a um child node
• Leaf é um node que não tem um child node no tree
• Altura é o comprimento do caminho mais longo para um leaf
• Profundidade é o comprimento do caminho para o seu root

Árvores binárias

Agora vamos discutir um tipo específico de tree. Chamamos-lhe obinary tree.

“Na informática, uma árvore binária é uma estrutura de dados de árvore em que cada nó tem no máximo duas crianças, que são referidas como a criança esquerda e a criança direita”. – Wikipedia

Então vejamos um exemplo de uma binary tree.

Vamos codificar uma árvore binária

A primeira coisa que precisamos de ter em mente quando implementamos um binary tree é que é uma colecção de nodes. Cada node tem três atributos: valueleft_child, e right_child.

Como implementar um simples binary tree que se inicializa com estas três propriedades?

Vamos ver.

class BinaryTree: def __init__(self, value): self.value = value self.left_child = None self.right_child = None

Aqui está. O nosso binary tree class.

Quando instanciamos um objecto, passamos o value (os dados do nó) como parâmetro. Veja-se o left_child e o right_child. Ambos estão definidos para None.

Porquê?

p>p>Porque quando criamos o nossonode, ele não tem filhos. Temos apenas onode data.

P>P>Teste-o:

tree = BinaryTree('a')print(tree.value) # aprint(tree.left_child) # Noneprint(tree.right_child) # None

P>É isso.

Podemos passar o stringa‘ como o value ao nosso Binary Tree node. Se imprimirmos o valueleft_child, e right_child, podemos ver os valores.

Vamos para a parte de inserção. O que precisamos de fazer aqui?

Implementaremos um método para inserir um novo node para o right e para o left.

Aqui estão as regras:

• se o actual node não tiver um left child, apenas criamos um novo node e definimo-lo para o nó actual left_child.
• se tiver o left child, criamos um novo nó e colocamo-lo no lugar do actual left child. Atribua este left child node ao novo nó left child.

Vamos retirá-lo. 🙂

Aqui está o código:

Again, se o nó actual não tiver um left child, apenas criamos um novo nó e definimo-lo para o nó actual left_child. Ou então criamos um novo nó e colocamo-lo no lugar do actual left child. Atribua isto left child node ao novo nó left child.

E fazemos o mesmo para inserir um right child node.

Done. 🙂

Mas não inteiramente. Ainda precisamos de o testar.

P>Vamos construir o seguintetree:

Para resumir a ilustração desta árvore:

• anode será o root do nosso binary Tree
• aleft childbnode
• aright childcnode
• bright childdnodebnode não tem um left child)
• cleft childenode
• cright childfnode
• both e e fnodes não tem filhos

Então aqui está o código para o tree:

Inserção é feita.

Agora temos de pensar em tree traversal.

Temos aqui duas opções: Depth-First Search (DFS) e Breadth-First Search (BFS).

• DFS “é um algoritmo para atravessar ou pesquisar a estrutura de dados em árvore. Começa-se pela raiz e explora-se, tanto quanto possível, ao longo de cada ramo antes de retroceder”. – Wikipedia
• BFS “é um algoritmo para atravessar ou pesquisar a estrutura de dados em árvore. Começa na raiz da árvore e explora os nós vizinhos primeiro, antes de passar para os vizinhos de nível seguinte”. – Wikipedia

Então vamos mergulhar em cada tipo de árvore que atravessa.

Depth-First Search (DFS)

DFS explora um caminho até uma folha antes de retroceder e explorar outro caminho. Vejamos um exemplo com este tipo de travessia.

O resultado para este algoritmo será 1-2-3-4-5-6-7.

Porquê?

Div>Div>>Div>>root (1). Imprima-o.

2. Vá para o left child (2). Imprima-o.

3. Depois vá para o left child (3). Imprima-o. (Este node não tem filhos)

4. Volte atrás e vá para o right child (4). Imprima-o. (Este node não tem filhos)

5. Voltar ao rootnode e ir para o right child (5). Imprima-o.

6. Vá a left child (6). Imprima-o. (Este node não tem filhos)

7. Volte atrás e vá para o right child (7). Imprima-o. (Este node não tem filhos)

8. Feito.

p> Quando vamos fundo para a folha e recuamos, isto chama-se algoritmo DFS.

Agora que estamos familiarizados com este algoritmo de travessia, discutiremos os tipos de DFS: pre-orderin-order, e post-order.

Pre-order

Foi exactamente o que fizemos no exemplo acima.

1. Imprimir o valor do node.
2. Ir para o left child e imprimi-lo. Isto é se, e só se, tiver um left child.

>li>> Ir ao right child e imprimi-lo. Isto é se, e só se, tiver um right child.

In-order

O resultado do algoritmo na ordem para este tree exemplo é 3-2-4-1-6-5-7.

A esquerda primeiro, o segundo do meio, e o último à direita.

Agora vamos codificá-lo.

def in_order(self): if self.left_child: self.left_child.in_order() print(self.value) if self.right_child: self.right_child.in_order()

1. >Ir para o left child e imprimi-lo. Isto é se, e só se, tiver um left child.
2. Imprimir o node valor
3. Ir para o right child e imprimi-lo. Isto é se, e só se, tiver um right child.

Pós-ordem

O resultado do post order algoritmo para este tree exemplo é 3-4-2-6-7-5-1.

A primeira à esquerda, a segunda à direita, e a última do meio.

Vamos codificar isto.

1. Ir para o left child e imprimi-lo. Isto é se, e só se, tiver um left child.

li>>Vá ao right child e imprima-o. Isto é se, e só se, tiver um right child.

2. Imprimir o node‘s value

Breadth-First Search (BFS)

BFS algoritmo atravessa o tree nível por nível e profundidade por profundidade.

Aqui está um exemplo que ajuda a explicar melhor este algoritmo:

Portanto, atravessamos nível por nível. Neste exemplo, o resultado é 1-2-5-3-3-4-6-7.

• Nível/Depth 0: apenas node com valor 1
• Nível/Depth 1: nodes com os valores 2 e 5
• Nível/Depth 2: nodes com os valores 3, 4, 6, e 7

Agora vamos codificá-lo.

Para implementar um algoritmo BFS, usamos o queue estrutura de dados para ajudar.

Como funciona?

Aqui está a explicação.

1. Primeiro adicionar o rootnode no método queue com o método put.
2. Iterar enquanto o queue não está vazio.
3. Obter o primeiro node no queue, e depois imprimir o seu valor.
4. Adicionar ambos left e rightchildren em o queue (se o actual node tem children).
5. div>. Vamos imprimir o valor de cada node, nível por nível, com o nosso queuehelper.

Árvore de Pesquisa Binária

“Uma Árvore de Pesquisa Binária é por vezes chamada árvores binárias ordenadas ou ordenadas, e mantém os seus valores em ordem ordenada, para que a pesquisa e outras operações possam usar o princípio da pesquisa binária” – Wikipedia

Uma propriedade importante de um Binary Search Tree é que o valor de a Binary Search Treenode é maior que o valor da descendência da sua left child, mas inferior ao valor da descendência do seu right child.“

a Aqui está uma repartição da ilustração acima:

• A está invertida. O subtree 7-5-8-6 precisa de estar do lado direito, e o subtree 2-1-3 precisa de estar do lado esquerdo.
• B é a única opção correcta. Ela satisfaz o Binary Search Tree property.
• C tem um problema: o node com o valor 4. Tem de estar do lado esquerdo do root porque é menor que 5.

Vamos codificar uma árvore de pesquisa binária!

Agora é hora de codificar!

O que veremos aqui? Vamos inserir novos nós, procurar um valor, eliminar nós, e o saldo do tree.

P>Vamos começar.

Inserção: adicionar novos nós à nossa árvore

Imagine que temos um tree vazio e queremos adicionar novo nodes com os seguintes valores nesta ordem: 50, 76, 21, 4, 32, 100, 64, 52.

p> A primeira coisa que precisamos de saber é se 50 é orootda nossa árvore.

Podemos agora começar a inserir node por node.

• 76 é superior a 50, por isso inserir 76 do lado direito.
• 21 é inferior a 50, por isso inserir 21 do lado esquerdo.
• 4 é inferior a 50. Node com valor 50 tem um left child 21. Uma vez que 4 é menor que 21, insira-o no lado esquerdo deste node.
• 32 é menor que 50. Node com valor 50 tem um left child 21. Uma vez que 32 é superior a 21, inserir 32 no lado direito deste node.
• 100 é superior a 50. Node com valor 50 tem um right child 76. Como 100 é superior a 76, inserir 100 no lado direito deste node.
• 64 é superior a 50. Node com valor 50 tem um right child 76. Uma vez que 64 é menor que 76, inserir 64 no lado esquerdo deste node.
• 52 é maior que 50. Node com valor 50 tem um right child 76. Uma vez que 52 é menor que 76, node com valor 76 tem um left child 64. 52 é menor que 64, por isso insira 54 no lado esquerdo deste node.

Nota um padrão aqui?

P>Div>Div>

1. É o novo node valor maior ou menor que o actual node?
2. se o valor do novo node for maior que o actual node, ir para a direita subtree. Se a corrente node não tiver um right child, insira-a aí, ou então retroceda para o passo #1.
3. se o valor do novo node for inferior ao actual node, vá para a esquerda subtree. Se o actual node não tiver um left child, insira-o aí, ou então volte para o passo #1.
4. Não tratámos de casos especiais aqui. Quando o valor de um novo node é igual ao valor actual do node, utilizar a regra número 3. Considere inserir valores iguais no lado esquerdo do subtree.

Agora vamos codificá-lo.

Parece muito simples.

A parte poderosa deste algoritmo é a parte de recorrência, que está na linha 9 e na linha 13. Ambas as linhas de código chamam o método insert_node, e usam-no para o seu left e rightchildren, respectivamente. As linhas 11 e 15 são as que fazem a inserção para cada child.

Vamos procurar o valor do nó… Ou não….

O algoritmo que vamos construir agora é sobre fazer pesquisas. Para um dado valor (número inteiro), diremos se o nosso Binary Search Tree tem ou não esse valor.

Um item importante a notar é como definimos o algoritmo de inserção de árvore. Primeiro temos o nosso rootnode. Toda a esquerda subtreenodes terá valores menores do que o rootnode. E todos os direitos subtreenodes terão valores maiores que o rootnode.

Vejamos um exemplo.

Imagine que temos isto tree.

Agora queremos saber se temos um nó baseado no valor 52.

P>Div>Div>

1. Comecemos com o rootnode como o nosso actual node. O valor dado é menor que o actual node valor? Se sim, então procuraremos à esquerda subtree.
2. É o valor dado maior que o actual node valor? Se sim, então iremos procurá-lo à direita subtree.
3. Se as regras #1 e #2 forem ambas falsas, podemos comparar o valor actual node e o valor dado se forem iguais. Se a comparação retornar true, então podemos dizer, “Sim! O nosso tree tem o valor dado”, caso contrário, dizemos, “Não, não tem.”

agora vamos codificá-lo.

Vamos dar o bico ao código:

• Linhas 8 e 9 enquadram-se na regra #1.
• Linhas 10 e 11 enquadram-se na regra #2.
• Linha 13 enquadra-se na regra #3.

Como é que a testamos?

P>Vamos criar o nosso Binary Search Tree inicializando o rootnode com o valor 15.

bst = BinarySearchTree(15)

E agora vamos inserir muitos novos nodes.

Para cada inserido node , testaremos se o nosso find_node método funciona realmente.

sim, funciona para estes valores dados! Vamos testar para um valor que não existe no nosso Binary Search Tree.

print(bst.find_node(0)) # False

Oh yeah.

A nossa pesquisa é feita.

Deleção: remoção e organização

Deleção é um algoritmo mais complexo porque precisamos de lidar com casos diferentes. Para um dado valor, precisamos de remover o node com este valor. Imagine os seguintes cenários para este node : não tem children, tem um único child, ou tem dois children.

• Cenário #1: A node sem childrenleafnode).

# |50| |50|# / \ / \# |30| |70| (DELETE 20) ---> |30| |70|# / \ \# |20| |40| |40|

Se o node que queremos apagar não tem filhos, apagamo-lo simplesmente. O algoritmo não precisa de reorganizar o tree.

• Cenário #2: A node com apenas uma criança (left ou right criança).

# |50| |50|# / \ / \# |30| |70| (DELETE 30) ---> |20| |70|# / # |20|

Neste caso, o nosso algoritmo precisa de fazer com que o pai do node aponte para o child nó. Se o node for o left child, fazemos o parente do left child apontar para o child. Se o node for o right child do seu pai, fazemos com que o pai do right child aponte para o child.

>li> Cenário #3: A node com duas crianças.

# |50| |50|# / \ / \# |30| |70| (DELETE 30) ---> |40| |70|# / \ /# |20| |40| |20|

Quando o node tem 2 filhos, precisamos de encontrar o node com o valor mínimo, começando pelo node‘sright child. Vamos colocar isto node com valor mínimo no lugar do node queremos remover.

é tempo de codificar.

1. Primeiro: Note os parâmetros value e parent. Queremos encontrar o node que tem este value , e o node do pai é importante para a remoção do node.
2. Segundo: Anote o valor de retorno. O nosso algoritmo irá retornar um valor booleano. Ele retorna True se encontrar o node e remove-o. Caso contrário, retorna False.
3. da linha 2 à linha 9: Começamos a procurar o node que tem o value que estamos à procura. Se o value for menor que o current nodevalue , vamos ao left subtree, recursivamente (se, e apenas se, o current node tiver um left child). Se o value for maior, vá para o right subtree, recursivamente.
4. Linha 10: Começamos a pensar no remove algoritmo.
5. Da linha 11 à linha 13: Cobrimos o node sem children , e é o left child do seu parent. Removemos o node, definindo o parent‘s left child a None.
6. Linhas 14 e 15: Cobrimos o node sem children , e é o right child a partir do seu parent. Removemos o node definindo o parent‘s right child a None.
7. Método do nó claro: Vou mostrar o clear_node código abaixo. Define os nós left child , right child, e o seu value a None.
8. da linha 16 à linha 18: Cobrimos o node com apenas um childleft child), e é o left child a partir do seu parent. Definimos o parent‘s left child para o node‘s left child (o único filho que tem).
9. da linha 19 para a linha 21: Cobrimos o node com apenas um childleft child), e é o right child do seu parent. Definimos o parent‘s right child para o node‘s left child (o único filho que tem).
10. da linha 22 para a linha 24: Cobrimos o node com apenas um childright child), e é o left child do seu parent. Definimos o parent‘s left child para o node‘s right child (o único filho que tem).
11. Da linha 25 para a linha 27: Cobrimos o node com apenas um childright child) , e é o right child do seu parent. Definimos o parent‘s right child para o node‘s right child (o único filho que tem).
12. Da linha 28 para a linha 30: Cobrimos o node com ambos left e rightcrianças. Obtemos o node com o mais pequeno value (o código é mostrado abaixo) e definimo-lo para o value do current node . Termine-o removendo o mais pequeno node.
13. Linha 32: Se encontrarmos o node que procuramos, precisa de regressar True. Da linha 11 à linha 31, nós tratamos deste caso. Portanto, basta devolver True e já está.

para usar o método clear_node: definir o None valor para os três atributos – (valueleft_child, e right_child)

def clear_node(self): self.value = None self.left_child = None self.right_child = None

li> Para usar o método find_minimum_value: ir muito para a esquerda. Se não conseguirmos encontrar mais nós, encontramos o mais pequeno.

def find_minimum_value(self): if self.left_child: return self.left_child.find_minimum_value() else: return self.value

Agora vamos testá-lo.

Usaremos este tree para testar o nosso remove_node algoritmo.

# |15|# / \# |10| |20|# / \ / \# |8| |12| |17| |25|# \# |19|

Vamos remover o node com o value 8. É um node sem criança.

print(bst.remove_node(8, None)) # Truebst.pre_order_traversal()# |15|# / \# |10| |20|# \ / \# |12| |17| |25|# \# |19|

Agora vamos remover o node com o 17. É um node com apenas uma criança.

print(bst.remove_node(17, None)) # Truebst.pre_order_traversal()# |15|# / \# |10| |20|# \ / \# |12| |19| |25|

Finalmente, removeremos um node com duas crianças. Este é o root do nosso tree.

print(bst.remove_node(15, None)) # Truebst.pre_order_traversal()# |19|# / \# |10| |20|# \ \# |12| |25|

Os testes estão agora terminados. 🙂

É tudo por agora!

Aprendemos muito aqui.

Parabéns por terminar este denso conteúdo. É realmente difícil compreender um conceito que não conhecemos. Mas conseguiu-o. 🙂

Este é mais um passo em frente na minha jornada para aprender e dominar algoritmos e estruturas de dados. Pode ver a documentação da minha viagem completa aqui na minha publicação Renaissance Developer.

Divertir-se, continuar a aprender e codificar.

Meu Twitter & Github. ☺

Recursos adicionais

• Introdução à Estrutura de Dados da Árvore por micodeschool
• Árvore por Wikipedia
• Como Não Ser Atingido pelas Árvores pelo talentoso Vaidehi Joshi
• Intro às Árvores, Palestra do Professor Jonathan Cohen
• Intro às Árvores, Palestra do Professor David Schmidt
• Intro to Trees, Palestra do Professor Victor Adamchik
• Trees com Gayle Laakmann McDowell
• Implementação de Árvores Binárias e Testes por TK
• Curso de Cursera: Estruturas de Dados por Universidade da Califórnia, San Diego
• Curso de Cursera Estruturas de Dados e Desempenho pela Universidade da Califórnia, San Diego
• Conceitos de Árvore de Pesquisa Binária e Implementação por Paul Programming
• Implementação de Árvore de Pesquisa Binária e Testes por TK
• Tree Traversal por Wikipedia
• Árvore de Pesquisa Binária Remove Algoritmo de Nó por GeeksforGeeks
• Árvore de Pesquisa Binária Remove Algoritmo de Nó por Algolist
• Learning Python From Zero to Hero