avl tree heap data structure c
Този урок предоставя подробно обяснение на AVL дърветата и структурата на данните от купчина в C ++ заедно с примери за AVL дърво за по-добро разбиране:
AVL Tree е балансирано по височина двоично дърво. Всеки възел е свързан с балансиран коефициент, който се изчислява като разлика между височината на лявото му поддърво и дясното поддърво.
Дървото AVL е кръстено на двамата си изобретатели, т.е. Abelson-Velvety и E.M. Landis и е публикуван през 1962 г. в техния доклад „Алгоритъм за организиране на информацията“.
=> Потърсете тук цялата серия за обучение на C ++.
Какво ще научите:
Дърво на AVL в C ++
За да бъде балансирано дървото, балансираният коефициент за всеки възел трябва да бъде между -1 и 1. Ако не, дървото ще стане небалансирано.
Примерно AVL дърво е показано по-долу.
В горното дърво можем да забележим, че разликата във височините на лявото и дясното дървета е 1. Това означава, че това е балансиран BST. Тъй като балансиращият фактор е 1, това означава, че лявото поддърво е с едно ниво по-високо от дясното поддърво.
Ако балансиращият фактор е 0, това означава, че лявото и дясното дървета са на едно и също ниво, т.е.съдържат еднаква височина. Ако балансиращият фактор е -1, тогава лявото поддърво е с едно ниво по-ниско от дясното поддърво.
AVL дървото контролира височината на двоично дърво за търсене и предотвратява изкривяването му. Защото когато двоичното дърво се изкриви, това е най-лошият случай (O (n)) за всички операции. Използвайки фактора на баланса, AVL дървото налага ограничение на двоичното дърво и по този начин поддържа всички операции при O (log n).
Операции с AVL дърво
Следват операциите, поддържани от AVL дървета.
# 1) Вмъкване на дърво AVL
Операцията за вмъкване в дървото на C ++ AVL е същата като тази на бинарното дърво за търсене. Единствената разлика е, че за да запазим балансиращия фактор, трябва да завъртим дървото наляво или надясно, за да не стане балансирано.
# 2) Изтриване на AVL дърво
Операцията за изтриване също се извършва по същия начин като операцията за изтриване в двоично дърво за търсене. Отново трябва да балансираме дървото, като извършим някои ротации на AVL Tree.
Внедряване на AVL Tree
Следва програмата C ++ за демонстриране на AVL дървото и неговите операции.
// 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 Изход:
Вътрешното обръщане за AVL дървото е:
4 5 8 11 12 17 18
Вътрешно обръщане след изтриване на възел 5:
4 8 11 12 17 18
Обърнете внимание, че ние използвахме примерното дърво, показано по-горе, за да демонстрираме AVL Tree в програмата.
Приложения на AVL дървета
- AVL дърветата се използват най-вече за видове набори и речници в паметта.
- AVL дърветата също се използват широко в приложения за бази данни, при които вмъкванията и изтриванията са по-малко, но има често търсене на необходимите данни.
- Използва се в приложения, които изискват подобрено търсене, освен приложенията в базата данни .
Структура на HEAP данни в C ++
Купчина в C ++ е специална структура на данни, базирана на дърво и представлява пълно двоично дърво.
Купчините могат да бъдат два вида:
- Мин куп : В min-heap най-малкият елемент е коренът на дървото и всеки възел е по-голям или равен на своя родител.
- Макс купчина : В max-heap най-големият елемент е коренът на дървото и всеки възел е по-малък или равен на своя родител.
Обмислете следния масив от елементи:
10 20 30 40 50 60 70
Минималната купчина за горните данни е представена по-долу:
Максималната купчина, използваща горните данни, е показана по-долу:
Двоична купчина C ++
Двоична купчина е често срещаното изпълнение на структура от данни на купчина.
Двоична купчина има следните свойства:
- Това е пълно двоично дърво, когато всички нива са напълно запълнени, с изключение на последното ниво и последното ниво има ключове колкото е възможно повече.
- Двоична купчина може да бъде min-heap или max-heap.
Двоичната купчина е пълно двоично дърво и по този начин тя може най-добре да бъде представена като масив.
Нека да разгледаме представянето на масива на двоична купчина.
Да разгледаме следната двоична купчина.
В горната диаграма обръщането на двоичната купчина се нарича ред на ниво.
По този начин масивът за горната двоична купчина е показан по-долу като HeapArr:
Както е показано по-горе, HeapArr (0) е коренът на двоичната купчина. Можем да представим останалите елементи най-общо, както следва:
най-доброто средство за почистване на файлове за Windows 10
Ако HeapArr (i) е iтивъзел в двоична купчина, след това индексите на останалите възли от iтивъзел са:
- HeapArr ((i-1) / 2) => Връща родителския възел.
- HeapArr ((2 * i) +1) => Връща левия дъщерен възел.
- HeapArr ((2 * i) +2) => Връща десния възел на детето.
Двоичната купчина отговаря на „свойството за подреждане“, което е два вида, както е посочено по-долу:
- Min Heap свойство: Минималната стойност е в корена и стойността на всеки възел е по-голяма или равна на неговия родител.
- Свойство Max Heap: Максималната стойност е в корена и стойността на всеки възел е по-малка или равна на неговия родител.
Операции върху двоична купчина
Следват основните операции, които се извършват на минимална купчина. В случай на максимална купчина, операциите се обръщат съответно.
# 1) Вмъкване () - Вмъква нов ключ в края на дървото. В зависимост от стойността на вложения ключ може да се наложи да коригираме купчината, без да нарушаваме свойството купчина.
отваряне на .jar файлове на Windows 10
# 2) Изтриване () - Изтрива ключ. Забележка че сложността във времето както на операциите за вмъкване, така и за изтриване на купчината е O (log n).
# 3) reduceKey () - Намалява стойността на ключа. Може да се наложи да поддържаме свойството на купчината, когато се извърши тази операция. Сложността във времето на функцията за намаляване на клавиша на купчината също е O (log n).
# 4) extractMin () - Премахва минималния елемент от min-heap. Той трябва да поддържа свойството на купчината след премахване на минималния елемент. По този начин неговата времева сложност е O (log n).
# 5) getMin () - Връща основния елемент на min-heap. Това е най-простата операция и сложността във времето за тази операция е O (1).
Внедряване на структурата данни от купчина
По-долу е дадено изпълнението на C ++, за да се демонстрира основната функционалност на 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: '< Изход:
Купчина след вмъкване: 2 4 6 8 10 12
корен на купчината: 2
Купчина след бутон за изтриване (2): 2 4 12 8 10
минимален елемент в купчината: 2
нов корен на купчината след намаляванеКлюч: 1
Приложения на купчини
- Хепсорт: Алгоритъмът за сортиране се прилага ефективно с помощта на двоична купчина.
- Приоритетни опашки: Двоичната купчина поддържа всички операции, необходими за успешно внедряване на приоритетните опашки за O (log n) време.
- Графични алгоритми: Някои от алгоритмите, свързани с графики, използват приоритетна опашка и от своя страна приоритетната опашка използва двоична купчина.
- Сложността на алгоритъма за бърза сортировка в най-лошия случай може да бъде преодоляна чрез сортиране на купчина.
Заключение
В този урок видяхме две структури от данни, т.е. AVL дървета и Heap сортиране в детайли.
AVL дърветата са балансирани двоични дървета, които се използват най-вече при индексиране на база данни.
Всички операции, извършвани върху AVL дървета, са подобни на тези при бинарни дървета за търсене, но единствената разлика в случая на AVL дървета е, че трябва да поддържаме фактора на баланса, т.е.структурата на данните трябва да остане балансирано дърво в резултат на различни операции. Това се постига с помощта на операцията AVL Tree Rotation.
Купчините са пълни двоични дървовидни структури, които са класифицирани в min-heap или max-heap. Min-heap има минимален елемент като свой корен и следващите възли са по-големи или равни на техния родителски възел. В max-heap ситуацията е точно обратна, т.е.максималният елемент е коренът на купчината.
Купчините могат да бъдат представени под формата на масиви с 0тиелемент като корен на дървото. Структурите на купчините данни се използват главно за внедряване на опашки за сортиране и приоритет на купчина.
=> Посетете тук, за да научите C ++ от нулата.
Препоръчително четене
- Структура на данните за опашката в C ++ с илюстрация
- Структура на данните за стека в C ++ с илюстрация
- Структура на данните от кръгов обвързан списък в C ++ с илюстрация
- Свързана списъчна структура на данните в C ++ с илюстрация
- Въведение в структурите на данни в C ++
- Структура на данните за приоритетна опашка в C ++ с илюстрация
- Структура на данните от списъка с двойно свързване в C ++ с илюстрация
- Сортиране на купчини в C ++ с примери
