Estrutura de dados - árvore de pesquisa binária

Uma árvore de pesquisa binária (BST) é uma árvore em que todos os nós seguem as propriedades mencionadas abaixo -

• O valor da chave da subárvore esquerda é menor que o valor da chave do nó pai (raiz).

• O valor da chave da subárvore direita é maior ou igual ao valor da chave do nó pai (raiz).

Assim, o BST divide todas as suas subárvores em dois segmentos; a subárvore esquerda e a subárvore direita e podem ser definidas como -

left_subtree (keys) < node (key) ≤ right_subtree (keys)

Representação

O BST é uma coleção de nós organizados de forma a manter as propriedades do BST. Cada nó possui uma chave e um valor associado. Durante a pesquisa, a chave desejada é comparada com as chaves no BST e, se encontrada, o valor associado é recuperado.

A seguir está uma representação pictórica do BST -

Observamos que a chave do nó raiz (27) possui todas as chaves de menor valor na subárvore esquerda e as chaves de maior valor na subárvore direita.

Operações básicas

A seguir estão as operações básicas de uma árvore -

• Search - Pesquisa um elemento em uma árvore.

• Insert - Insere um elemento em uma árvore.

• Pre-order Traversal - Atravessa uma árvore de forma pré-encomenda.

• In-order Traversal - Percorre uma árvore de maneira ordenada.

• Post-order Traversal - Percorre uma árvore de maneira pós-ordem.

Nó

Defina um nó com alguns dados, referências a seus nós filhos esquerdo e direito.

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

Operação de Pesquisa

Sempre que um elemento deve ser pesquisado, comece a pesquisar a partir do nó raiz. Então, se os dados forem menores que o valor da 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

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;
}

Operação de inserção

Sempre que um elemento deve ser 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

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
   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;
            }
         }
      }            
   }
}