Estrutura de dados e algoritmos - árvore

A árvore representa os nós conectados por arestas. Discutiremos árvore binária ou árvore de busca binária especificamente.

Árvore binária é uma estrutura de dados especial usada para fins de armazenamento de dados. Uma árvore binária tem uma condição especial de que cada nó pode ter no máximo dois filhos. Uma árvore binária tem os benefícios de uma matriz ordenada e uma lista vinculada, pois a pesquisa é tão rápida quanto em uma matriz classificada e as operações de inserção ou exclusão são tão rápidas quanto em uma lista vinculada.

Termos importantes

A seguir estão os termos importantes com respeito à árvore.

Path - Caminho se refere à sequência de nós ao longo das bordas de uma árvore.
Root- O nó no topo da árvore é denominado raiz. Existe apenas uma raiz por árvore e um caminho do nó raiz para qualquer nó.
Parent - Qualquer nó, exceto o nó raiz, tem uma borda ascendente para um nó chamado pai.
Child - O nó abaixo de um determinado nó conectado por sua borda para baixo é chamado de nó filho.
Leaf - O nó que não possui nenhum nó filho é denominado nó folha.
Subtree - Subárvore representa os descendentes de um nó.
Visiting - A visita se refere à verificação do valor de um nó quando o controle está no nó.
Traversing - Atravessar significa passar pelos nós em uma ordem específica.
Levels- O nível de um nó representa a geração de um nó. Se o nó raiz está no nível 0, então seu próximo nó filho está no nível 1, seu neto está no nível 2 e assim por diante.
keys - A chave representa um valor de um nó com base no qual uma operação de pesquisa deve ser realizada para um nó.

Representação da árvore de busca binária

A árvore de pesquisa binária exibe um comportamento especial. O filho esquerdo de um nó deve ter um valor menor que o valor de seu pai e o filho direito do nó deve ter um valor maior que seu valor pai.

Vamos implementar árvore usando objeto de nó e conectá-los por meio de referências.

Nó de Árvore

O código para escrever um nó de árvore seria semelhante ao que é fornecido a seguir. Ele tem uma parte de dados e referências a seus nós filho esquerdo e direito.

struct node {
   int data;   
   struct node *leftChild;
   struct node *rightChild;
};

Em uma árvore, todos os nós compartilham uma construção comum.

Operações básicas de BST

As operações básicas que podem ser realizadas em uma estrutura de dados de árvore de pesquisa binária são as seguintes -

Insert - Insere um elemento em uma árvore / cria uma árvore.
Search - Pesquisa um elemento em uma árvore.
Preorder Traversal - Atravessa uma árvore de forma pré-encomenda.
Inorder Traversal - Percorre uma árvore de maneira ordenada.
Postorder Traversal - Percorre uma árvore de maneira pós-ordem.

Devemos aprender a criar (inserir em) uma estrutura de árvore e pesquisar um item de dados em uma árvore neste capítulo. Aprenderemos sobre os métodos de travessia de árvores no próximo capítulo.

Operação de inserção

A primeira inserção cria a árvore. Depois, sempre que um elemento for inserido, primeiro localize seu local apropriado. Comece a pesquisar a partir do nó raiz e, em seguida, se os dados forem menores que o valor-chave, procure o local vazio na subárvore esquerda e insira os dados. Caso contrário, pesquise o local vazio na subárvore certa e insira os dados.

Algoritmo

If root is NULL 
   then create root node
return

If root exists then
   compare the data with node.data
   
   while until insertion position is located

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree

   endwhile 
   
   insert data
	
end If

Implementação

A implementação da função de inserção deve ser semelhante a esta -

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty, create root node
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent  = NULL;

      while(1) {                
         parent = current;

         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;                
            
            //insert to the left
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }
			
         //go to right of the tree
         else {
            current = current->rightChild;
            
            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}

Operação de Pesquisa

Sempre que um elemento deve ser pesquisado, comece a pesquisar a partir do nó raiz e, em seguida, se os dados forem menores que o valor-chave, procure o elemento na subárvore esquerda. Caso contrário, procure o elemento na subárvore certa. Siga o mesmo algoritmo para cada nó.

Algoritmo

If root.data is equal to search.data
   return root
else
   while data not found

      If data is greater than node.data
         goto right subtree
      else
         goto left subtree
         
      If data found
         return node
   endwhile 
   
   return data not found
   
end if

A implementação deste algoritmo deve ser semelhante a esta.

struct node* search(int data) {
   struct node *current = root;
   printf("Visiting elements: ");

   while(current->data != data) {
      if(current != NULL)
      printf("%d ",current->data); 
      
      //go to left tree

      if(current->data > data) {
         current = current->leftChild;
      }
      //else go to right tree
      else {                
         current = current->rightChild;
      }

      //not found
      if(current == NULL) {
         return NULL;
      }

      return current;
   }  
}

Para saber mais sobre a implementação da estrutura de dados da árvore de pesquisa binária, clique aqui .