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:
- Os nós que são menores que o nó raiz, que são colocados como filhos à esquerda do BST.
- Os nós que são maiores do que o nó raiz que é colocado como os filhos certos do BST.
- 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.
O que você aprenderá:
- Árvore de pesquisa binária C ++
- Operações básicas
- Implementação da árvore de pesquisa binária C ++
- Vantagens do BST
- Aplicações de BST
- Conclusão
- Leitura recomendada
Árvore de pesquisa binária C ++
Um exemplo de BST é mostrado abaixo.
Á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.
software sql grátis para windows 10
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.
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ó.
# 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.
# 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.
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
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.
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
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
agile entrevista perguntas e respostas para experientes
# 3) 60
# 4) 65
# 5) 70
Quando executamos a travessia em ordem no BST acima que acabamos de construir, a sequência é a seguinte.
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
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
- Estrutura de dados de árvore binária em C ++
- Árvore AVL e estrutura de dados heap em C ++
- Estrutura de dados da árvore B e da árvore B + em C ++
- Operações básicas de entrada / saída em C ++
- Operações básicas de E / S em Java (fluxos de entrada / saída)
- Árvores em C ++: terminologia básica, técnicas transversais e tipos de árvore C ++
- Operações de entrada de arquivo e saída em C ++
- Ponteiros e operações de ponteiro em C ++