Menu

Árvore de pesquisa binária C ++: implementação e operações BST com exemplos

  • Principal
  • Outro
  • Árvore de pesquisa binária C ++: implementação e operações BST com exemplos

binary search tree c

Tutorial detalhado sobre árvore de pesquisa binária (BST) em C ++, incluindo operações, implementação de C ++, vantagens e programas de exemplo:

Uma árvore de pesquisa binária ou BST, como é popularmente chamada, é uma árvore binária que atende às seguintes condições:

  1. Os nós que são menores que o nó raiz, que são colocados como filhos à esquerda do BST.
  2. Os nós que são maiores do que o nó raiz que é colocado como os filhos certos do BST.
  3. As subárvores esquerda e direita são, por sua vez, as árvores binárias de pesquisa.

Este arranjo de ordenar as chaves em uma seqüência particular facilita o programador a realizar operações como busca, inserção, exclusão, etc. com mais eficiência. Se os nós não estiverem ordenados, podemos ter que comparar cada um dos nós antes de obter o resultado da operação.

=> Verifique a série de treinamento C ++ completa aqui.

Árvore de pesquisa binária em C ++

O que você aprenderá:

Árvore de pesquisa binária C ++

Um exemplo de BST é mostrado abaixo.

Amostra BST

software sql grátis para windows 10

Árvores binárias de pesquisa também são chamadas de “Árvores binárias ordenadas” devido a esta ordem específica de nós.

A partir do BST acima, podemos ver que a subárvore esquerda tem nós menores que a raiz, ou seja, 45, enquanto a subárvore direita tem nós maiores que 45.

Agora vamos discutir algumas operações básicas do BST.

Operações básicas

# 1) Inserir

A operação de inserção adiciona um novo nó em uma árvore de pesquisa binária.

O algoritmo para a operação de inserção da árvore de pesquisa binária é fornecido abaixo.

Insert(data) Begin If node == null Return createNode(data) If(data >root->data) Node->right = insert(node->left,data) Else If(data data) Node->right = insert(node>right,data) Return node; end

Conforme mostrado no algoritmo acima, temos que garantir que o nó seja colocado na posição apropriada para que não violemos a ordem BST.

Inserir operação no BST

Como vemos na seqüência de diagramas acima, fazemos uma série de operações de inserção. Após comparar a chave a ser inserida com o nó raiz, a subárvore esquerda ou direita é escolhida para a chave a ser inserida como um nó folha na posição apropriada.

# 2) Excluir

A operação de exclusão exclui um nó que corresponde à chave fornecida do BST. Também nesta operação, temos que reposicionar os nós restantes após a exclusão para que a ordenação BST não seja violada.

Portanto, dependendo de qual nó temos que excluir, temos os seguintes casos para exclusão no BST:

# 1) Quando o nó é um nó folha

Quando o nó a ser excluído é um nó folha, excluímos diretamente o nó.

O nó é um nó folha

# 2) Quando o nó tem apenas um filho

Quando o nó a ser excluído tem apenas um filho, copiamos o filho para o nó e excluímos o filho.

Node tem apenas um filho

# 3) Quando o nó tem dois filhos

Se o nó a ser excluído tiver dois filhos, encontraremos o sucessor em ordem para o nó e, em seguida, copiaremos o sucessor em ordem para o nó. Posteriormente, excluímos o sucessor inorder.

Node tem dois filhos

Na árvore acima, para excluir o nó 6 com dois filhos, primeiro encontramos o sucessor em ordem para esse nó a ser excluído. Encontramos o sucessor da ordem encontrando o valor mínimo na subárvore certa. No caso acima, o valor mínimo é 7 na subárvore certa. Nós o copiamos para o nó a ser excluído e, em seguida, excluímos o sucessor do pedido.

# 3) Pesquisar

A operação de pesquisa do BST procura um item específico identificado como “chave” no BST. A vantagem de pesquisar um item no BST é que não precisamos pesquisar a árvore inteira. Em vez disso, por causa da ordem no BST, apenas comparamos a chave com a raiz.

Se a chave for a mesma de root, retornamos root. Se a chave não for raiz, então a comparamos com a raiz para determinar se precisamos pesquisar a subárvore esquerda ou direita. Assim que encontrarmos a subárvore, precisamos pesquisar a chave em e, recursivamente, procuramos por ela em qualquer uma das subárvores.

A seguir está o algoritmo para uma operação de pesquisa em BST.

Search(key) Begin If(root == null || root->data == key) Return root; If(root->key left,key) Else if (root->key >key ) Search(root->right,key); end

Operação de pesquisa em BST

Se quisermos pesquisar uma chave com valor 6 na árvore acima, primeiro comparamos a chave com o nó raiz, ou seja, if (6 == 7) => Não if (6<7) =Yes; this means that we will omit the right subtree and search for the key in the left subtree.

Em seguida, descemos para a subárvore esquerda. Se (6 == 5) => Não.

Se (6 Não; isso significa 6> 5 e temos que mover para a direita.

Se (6 == 6) => Sim; a chave foi encontrada.

# 4) Traversals

Já discutimos os percursos da árvore binária. Também no caso do BST, podemos percorrer a árvore para obter a sequência inOrder, preorder ou postOrder. Na verdade, quando atravessamos o BST na sequência Inorder01, obtemos a sequência classificada.

Mostramos isso na ilustração abaixo.

travessias

As travessias para a árvore acima são as seguintes:

Travessia em ordem (lnr): 3 5 6 7 8 9 10
Traversal de pré-ordem (nlr): 7 5 3 6 9 8 10
PostOrder traversal (lrn): 3 6 5 8 10 9 7

Ilustração

Vamos construir uma árvore de busca binária a partir dos dados fornecidos abaixo.

45 30 60 65 70

Tomemos o primeiro elemento como o nó raiz.

# 1) 45

nó raiz

Nas etapas subsequentes, colocaremos os dados de acordo com a definição da árvore de pesquisa binária, ou seja, se os dados forem menores que o nó pai, eles serão colocados no filho esquerdo e se os dados forem maiores que o nó pai, então será a criança certa.

Essas etapas são mostradas a seguir.

# 2) 30

Árvore de pesquisa binária Etapa 1 30

# 3) 60

Árvore de pesquisa binária Etapa 2 60

# 4) 65

11 Árvore de pesquisa binária etapa 3

# 5) 70

Árvore de pesquisa binária, etapa 4

Quando executamos a travessia em ordem no BST acima que acabamos de construir, a sequência é a seguinte.

Sequência de travessia em ordem

Podemos ver que a sequência de travessia possui elementos organizados em ordem crescente.

Implementação da árvore de pesquisa binária C ++

Vamos demonstrar o BST e suas operações usando a implementação C ++.

#include using namespace std; //declaration for new bst node struct bstnode { int data; struct bstnode *left, *right; }; // create a new BST node struct bstnode *newNode(int key) { struct bstnode *temp = new struct bstnode(); temp->data = key; temp->left = temp->right = NULL; return temp; } // perform inorder traversal of BST void inorder(struct bstnode *root) { if (root != NULL) { inorder(root->left); cout<data<<' '; inorder(root->right); } } /* insert a new node in BST with given key */ struct bstnode* insert(struct bstnode* node, int key) { //tree is empty;return a new node if (node == NULL) return newNode(key); //if tree is not empty find the proper place to insert new node if (key data) node->left = insert(node->left, key); else node->right = insert(node->right, key); //return the node pointer return node; } //returns the node with minimum value struct bstnode * minValueNode(struct bstnode* node) { struct bstnode* current = node; //search the leftmost tree while (current && current->left != NULL) current = current->left; return current; } //function to delete the node with given key and rearrange the root struct bstnode* deleteNode(struct bstnode* root, int key) { // empty tree if (root == NULL) return root; // search the tree and if key data) root->left = deleteNode(root->left, key); // if key > root, go for rightmost tree else if (key > root->data) root->right = deleteNode(root->right, key); // key is same as root else { // node with only one child or no child if (root->left == NULL) { struct bstnode *temp = root->right; free(root); return temp; } else if (root->right == NULL) { struct bstnode *temp = root->left; free(root); return temp; } // node with both children; get successor and then delete the node struct bstnode* temp = minValueNode(root->right); // Copy the inorder successor's content to this node root->data = temp->data; // Delete the inorder successor root->right = deleteNode(root->right, temp->data); } return root; } // main program int main() { /* Let us create following BST 40 / 30 60 65 70*/ struct bstnode *root = NULL; root = insert(root, 40); root = insert(root, 30); root = insert(root, 60); root = insert(root, 65); root = insert(root, 70); cout<<'Binary Search Tree created (Inorder traversal):'<

Resultado:

Árvore de pesquisa binária criada (travessia em ordem):

30 40 60 65 70

Excluir nó 40

Traversal em ordem para a árvore de pesquisa binária modificada:

30 60 65 70

No programa acima, geramos o BST para a seqüência de passagem em ordem.

Vantagens do BST

# 1) A pesquisa é muito eficiente

Temos todos os nós do BST em uma ordem específica, portanto, a busca por um determinado item é muito eficiente e rápida. Isso ocorre porque não precisamos pesquisar a árvore inteira e comparar todos os nós.

Temos apenas que comparar o nó raiz com o item que estamos pesquisando e então decidir se precisamos pesquisar na subárvore esquerda ou direita.

# 2) Trabalho eficiente quando comparado a matrizes e listas vinculadas

agile entrevista perguntas e respostas para experientes

Quando pesquisamos um item no caso de BST, eliminamos metade da subárvore esquerda ou direita em cada etapa, melhorando assim o desempenho da operação de pesquisa. Isso contrasta com matrizes ou listas vinculadas nas quais precisamos comparar todos os itens sequencialmente para pesquisar um item específico.

# 3) Inserir e excluir são mais rápidos

As operações de inserção e exclusão também são mais rápidas quando comparadas a outras estruturas de dados, como listas e matrizes vinculadas.

Aplicações de BST

Algumas das principais aplicações do BST são as seguintes:

  • O BST é usado para implementar a indexação multinível em aplicativos de banco de dados.
  • O BST também é usado para implementar construções como um dicionário.
  • O BST pode ser usado para implementar vários algoritmos de pesquisa eficientes.
  • O BST também é usado em aplicativos que exigem uma lista classificada como entrada, como as lojas online.
  • BSTs também são usados ​​para avaliar a expressão usando árvores de expressão.

Conclusão

Árvores binárias de busca (BST) são uma variação da árvore binária e são amplamente utilizadas na área de software. Eles também são chamados de árvores binárias ordenadas, pois cada nó no BST é colocado de acordo com uma ordem específica.

A passagem em ordem do BST nos dá a seqüência classificada de itens em ordem crescente. Quando BSTs são usados ​​para pesquisa, é muito eficiente e é feito rapidamente. BSTs também são usados ​​para uma variedade de aplicações, como codificação de Huffman, indexação multinível em bancos de dados, etc.

=> Leia a popular série de treinamento C ++ aqui.

Leitura recomendada

^