avl tree heap data structure c
Este tutorial fornece uma explicação detalhada de árvores AVL e estrutura de dados Heap em C ++ junto com exemplos de árvores AVL para melhor compreensão:
AVL Tree é uma árvore binária com altura balanceada. Cada nó está associado a um fator balanceado que é calculado como a diferença entre a altura de sua subárvore esquerda e a subárvore direita.
A árvore AVL recebeu o nome de seus dois inventores, ou seja, G.M. Abelson-Velvety e E.M. Landis, e foi publicado em 1962 em seu artigo “Um algoritmo para a organização da informação”.
=> Procure toda a série de treinamento C ++ aqui.
como remover o elemento array em java
O que você aprenderá:
Árvore AVL em C ++
Para que a árvore seja balanceada, o fator balanceado para cada nó deve estar entre -1 e 1. Caso contrário, a árvore ficará desequilibrada.
Um exemplo de árvore AVL é mostrado abaixo.
Na árvore acima, podemos notar que a diferença nas alturas das subárvores esquerda e direita é 1. Isso significa que é um BST equilibrado. Como o fator de equilíbrio é 1, isso significa que a subárvore esquerda está um nível acima da subárvore direita.
Se o fator de equilíbrio for 0, isso significa que as subárvores esquerda e direita estão no mesmo nível, ou seja, elas contêm altura igual. Se o fator de balanceamento for -1, então a subárvore esquerda está um nível abaixo da subárvore direita.
A árvore AVL controla a altura de uma árvore de pesquisa binária e evita que ela seja distorcida. Porque quando uma árvore binária fica distorcida, é o pior caso (O (n)) para todas as operações. Ao usar o fator de equilíbrio, a árvore AVL impõe um limite à árvore binária e, portanto, mantém todas as operações em O (log n).
AVL Tree Operations
A seguir estão as operações suportadas pelas árvores AVL.
# 1) Inserção de árvore AVL
A operação de inserção na árvore AVL C ++ é a mesma da árvore de pesquisa binária. A única diferença é que, para manter o fator de equilíbrio, precisamos girar a árvore para a esquerda ou direita para que ela não fique desequilibrada.
# 2) Exclusão da árvore AVL
A operação de exclusão também é realizada da mesma maneira que a operação de exclusão em uma árvore de pesquisa binária. Novamente, precisamos reequilibrar a árvore executando algumas rotações da árvore AVL.
Implementação de árvore AVL
A seguir está o programa C ++ para demonstrar a árvore AVL e suas operações.
// C++ program for AVL Tree #include using namespace std; // An AVL tree node class AVLNode { public: int key; AVLNode *left; AVLNode *right; int depth; }; //get max of two integers int max(int a, int b){ return (a > b)? a : b; } //function to get height of the tree int depth(AVLNode *n) { if (n == NULL) return 0; return n->depth; } // allocate a new node with key passed AVLNode* newNode(int key) { AVLNode* node = new AVLNode(); node->key = key; node->left = NULL; node->right = NULL; node->depth = 1; // new node added as leaf return(node); } // right rotate the sub tree rooted with y AVLNode *rightRotate(AVLNode *y) { AVLNode *x = y->left; AVLNode *T2 = x->right; // Perform rotation x->right = y; y->left = T2; // Update heights y->depth = max(depth(y->left), depth(y->right)) + 1; x->depth = max(depth(x->left), depth(x->right)) + 1; // Return new root return x; } // left rotate the sub tree rooted with x AVLNode *leftRotate(AVLNode *x) { AVLNode *y = x->right; AVLNode *T2 = y->left; // Perform rotation y->left = x; x->right = T2; // Update heights x->depth = max(depth(x->left), depth(x->right)) + 1; y->depth = max(depth(y->left), depth(y->right)) + 1; // Return new root return y; } // Get Balance factor of node N int getBalance(AVLNode *N) { if (N == NULL) return 0; return depth(N->left) - depth(N->right); } //insertion operation for node in AVL tree AVLNode* insert(AVLNode* node, int key) { //normal BST rotation if (node == NULL) return(newNode(key)); if (key key) node->left = insert(node->left, key); else if (key > node->key) node->right = insert(node->right, key); else // Equal keys not allowed return node; //update height of ancestor node node->depth = 1 + max(depth(node->left), depth(node->right)); int balance = getBalance(node); //get balance factor // rotate if unbalanced // Left Left Case if (balance > 1 && key left->key) return rightRotate(node); // Right Right Case if (balance node->right->key) return leftRotate(node); // Left Right Case if (balance > 1 && key > node->left->key) { node->left = leftRotate(node->left); return rightRotate(node); } // Right Left Case if (balance <-1 && key right->key) { node->right = rightRotate(node->right); return leftRotate(node); } return node; } // find the node with minimum value AVLNode * minValueNode(AVLNode* node) { AVLNode* current = node; // find the leftmost leaf */ while (current->left != NULL) current = current->left; return current; } // delete a node from AVL tree with the given key AVLNode* deleteNode(AVLNode* root, int key) { if (root == NULL) return root; //perform BST delete if ( key key ) root->left = deleteNode(root->left, key); else if( key > root->key ) root->right = deleteNode(root->right, key); else { // node with only one child or no child if( (root->left == NULL) || (root->right == NULL) ) { AVLNode *temp = root->left ? root->left : root->right; if (temp == NULL) { temp = root; root = NULL; } else // One child case *root = *temp; free(temp); } else { AVLNode* temp = minValueNode(root->right); root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); } } if (root == NULL) return root; // update depth root->depth = 1 + max(depth(root->left), depth(root->right)); // get balance factor int balance = getBalance(root); //rotate the tree if unbalanced // Left Left Case if (balance > 1 && getBalance(root->left) >= 0) return rightRotate(root); // Left Right Case if (balance > 1 && getBalance(root->left) left = leftRotate(root->left); return rightRotate(root); } // Right Right Case if (balance right) <= 0) return leftRotate(root); // Right Left Case if (balance right)> 0) { root->right = rightRotate(root->right); return leftRotate(root); } return root; } // prints inOrder traversal of the AVL tree void inOrder(AVLNode *root) { if(root != NULL) { inOrder(root->left); cout Resultado:
A passagem em ordem para a árvore AVL é:
4 5 8 11 12 17 18
Traversal em ordem após a exclusão do nó 5:
4 8 11 12 17 18
Selênio webdriver entrevista perguntas e respostas com 3 anos de experiência
Observe que usamos a árvore de exemplo mostrada acima para demonstrar a árvore AVL no programa.
Aplicações de árvores AVL
- As árvores AVL são usadas principalmente para tipos de conjuntos e dicionários na memória.
- As árvores AVL também são amplamente utilizadas em aplicativos de banco de dados em que as inserções e exclusões são menores, mas há pesquisas frequentes de dados necessários.
- É usado em aplicativos que requerem pesquisa aprimorada além dos aplicativos de banco de dados .
Estrutura de dados HEAP em C ++
Um heap em C ++ é uma estrutura de dados especial baseada em árvore e é uma árvore binária completa.
Pilhas podem ser de dois tipos:
- Pilha mínima : No min-heap, o menor elemento é a raiz da árvore e cada nó é maior ou igual a seu pai.
- Pilha máxima : No heap máximo, o maior elemento é a raiz da árvore e cada nó é menor ou igual a seu pai.
Considere a seguinte matriz de elementos:
10 20 30 40 50 60 70
O heap mínimo para os dados acima é representado a seguir:
O heap máximo usando os dados acima é mostrado abaixo:
Binary Heap C ++
Um heap binário é a implementação comum de uma estrutura de dados de heap.
Um heap binário tem as seguintes propriedades:
- É uma árvore binária completa quando todos os níveis estão completamente preenchidos, exceto possivelmente o último nível e o último nível tem suas chaves o máximo possível.
- Um heap binário pode ser um heap mínimo ou heap máximo.
Um heap binário é uma árvore binária completa e, portanto, pode ser melhor representado como um array.
Vamos dar uma olhada na representação de array do heap binário.
Considere o seguinte heap binário.
No diagrama acima, a travessia do heap binário é chamada de ordem de nível.
Portanto, a matriz para o heap binário acima é mostrada abaixo como HeapArr:
Conforme mostrado acima, HeapArr [0] é a raiz do heap binário. Podemos representar os outros elementos em termos gerais da seguinte forma:
Se HeapArr [i] é um iºnó em um heap binário, então os índices dos outros nós do iºnós são:
- HeapArr [(i-1) / 2] => Retorna o nó pai.
- HeapArr [(2 * i) +1] => Retorna o nó filho esquerdo.
- HeapArr [(2 * i) +2] => Retorna o nó filho certo.
O heap binário satisfaz a 'propriedade de pedido', que é de dois tipos, conforme declarado abaixo:
- Propriedade de pilha mínima: O valor mínimo está na raiz e o valor de cada nó é maior ou igual a seu pai.
- Propriedade de pilha máxima: O valor máximo está na raiz e o valor de cada nó é menor ou igual a seu pai.
Operações em heap binário
A seguir estão as operações básicas que são realizadas no heap mínimo. No caso do heap máximo, as operações são invertidas de acordo.
# 1) Inserir () - Insere uma nova chave no final da árvore. Dependendo do valor da chave inserida, podemos ter que ajustar o heap, sem violar a propriedade heap.
# 2) Excluir () - Exclui uma chave. Observação que a complexidade de tempo de ambas as operações de inserção e exclusão do heap é O (log n).
# 3) diminuirKey () - Diminui o valor da chave. Podemos precisar manter a propriedade heap quando esta operação ocorrer. A complexidade de tempo da operação de aggregKey do heap também é O (log n).
# 4) extractMin () - Remove o elemento mínimo do heap mínimo. Ele precisa manter a propriedade de heap depois de remover o elemento mínimo. Assim, sua complexidade de tempo é O (log n).
# 5) getMin () - Retorna o elemento raiz do heap mínimo. Esta é a operação mais simples e a complexidade de tempo para esta operação é O (1).
Implementação da estrutura de dados heap
A seguir, é fornecida a implementação C ++ para demonstrar a funcionalidade básica do min-heap.
#include #include using namespace std; // swap two integers void swap(int *x, int *y) { int temp = *x; *x = *y; *y = temp; } // Min-heap class class Min_Heap { int *heaparr; // pointer to array of elements in heap int capacity; // maximum capacity of min heap int heap_size; // current heap size public: Min_Heap(int cap){ heap_size = 0; capacity = cap; heaparr = new int[capacity]; } // to heapify a subtree with the root at given index void MinHeapify(int ); int parent(int i) { return (i-1)/2; } // left child of node i int left(int i) { return (2*i + 1); } // right child of node i int right(int i) { return (2*i + 2); } // extract minimum element in the heap(root of the heap) int extractMin(); // decrease key value to newKey at i void decreaseKey(int i, int newKey); // returns root of the min heap int getMin() { return heaparr[0]; } // Deletes a key at i void deleteKey(int i); // Inserts a new key 'key' void insertKey(int key); void displayHeap(){ for(int i = 0;i heaparr[i]) { swap(&heaparr[i], &heaparr[parent(i)]); i = parent(i); } } void Min_Heap::decreaseKey(int i, int newKey) { heaparr[i] = newKey; while (i != 0 && heaparr[parent(i)] > heaparr[i]) { swap(&heaparr[i], &heaparr[parent(i)]); i = parent(i); } } int Min_Heap::extractMin() { if (heap_size <= 0) return INT_MAX; if (heap_size == 1) { heap_size--; return heaparr[0]; } // Store the minimum value,delete it from heap int root = heaparr[0]; heaparr[0] = heaparr[heap_size-1]; heap_size--; MinHeapify(0); return root; } void Min_Heap::deleteKey(int i) { decreaseKey(i, INT_MIN); extractMin(); } void Min_Heap::MinHeapify(int i) { int l = left(i); int r = right(i); int min = i; if (l < heap_size && heaparr[l] < heaparr[i]) min = l; if (r < heap_size && heaparr[r] < heaparr[min]) min = r; if (min != i) { swap(&heaparr[i], &heaparr[min]); MinHeapify(min); } } // main program int main() { Min_Heap h(11); h.insertKey(2); h.insertKey(4); h.insertKey(6); h.insertKey(8); h.insertKey(10); h.insertKey(12); cout<<'Heap after insertion:'; h.displayHeap(); cout<<'root of the heap: '< Resultado:
tipos de herança em c ++
Pilha após a inserção: 2 4 6 8 10 12
raiz da pilha: 2
Pilha após deletekey (2): 2 4 12 8 10
elemento mínimo na pilha: 2
nova raiz do heap após diminuiKey: 1
Aplicações de Heaps
- Heapsort: O algoritmo Heapsort é efetivamente implementado usando um heap binário.
- Filas prioritárias: O heap binário oferece suporte a todas as operações necessárias para implementar com êxito as filas de prioridade em tempo O (log n).
- Algoritmos de gráfico: Alguns dos algoritmos relacionados a gráficos usam fila de prioridade e, por sua vez, a fila de prioridade usa heap binário.
- A complexidade do pior caso do algoritmo de classificação rápida pode ser superada usando a classificação de heap.
Conclusão
Neste tutorial, vimos duas estruturas de dados, ou seja, árvores AVL e classificação Heap em detalhes.
As árvores AVL são árvores binárias balanceadas, usadas principalmente na indexação de banco de dados.
Todas as operações realizadas nas árvores AVL são semelhantes às das árvores de busca binárias, mas a única diferença no caso das árvores AVL é que precisamos manter o fator de equilíbrio, ou seja, a estrutura de dados deve permanecer uma árvore equilibrada como resultado de várias operações. Isso é conseguido usando a operação AVL Tree Rotation.
Heaps são estruturas de árvore binárias completas que são classificadas em min-heap ou max-heap. O heap mínimo tem o elemento mínimo como sua raiz e os nós subsequentes são maiores ou iguais ao seu nó pai. No heap máximo, a situação é exatamente oposta, ou seja, o elemento máximo é a raiz do heap.
Pilhas podem ser representadas na forma de matrizes com o 0ºelemento como a raiz da árvore. As estruturas de dados heap são usadas principalmente para implementar classificação de heap e filas de prioridade.
=> Visite aqui para aprender C ++ do zero.
Leitura recomendada
- Estrutura de dados da fila em C ++ com ilustração
- Estrutura de pilha de dados em C ++ com ilustração
- Estrutura de dados de lista vinculada circular em C ++ com ilustração
- Estrutura de dados de lista vinculada em C ++ com ilustração
- Introdução às estruturas de dados em C ++
- Estrutura de dados da fila de prioridade em C ++ com ilustração
- Estrutura de dados de lista duplamente vinculada em C ++ com ilustração
- Classificação de heap em C ++ com exemplos