avl tree heap data structure c
Ten samouczek zawiera szczegółowe wyjaśnienie drzew AVL i struktury danych sterty w języku C ++ wraz z przykładami drzew AVL dla lepszego zrozumienia:
Drzewo AVL to drzewo binarne o zrównoważonej wysokości. Każdy węzeł jest powiązany ze zrównoważonym współczynnikiem, który jest obliczany jako różnica między wysokością jego lewego poddrzewa i prawego poddrzewa.
Drzewo AVL zostało nazwane na cześć jego dwóch wynalazców, tj. G.M. Abelson-Velvety i E.M. Landis, i został opublikowany w 1962 roku w artykule „Algorytm organizacji informacji”.
=> Poszukaj całej serii szkoleń C ++ tutaj.
Czego się nauczysz:
Drzewo AVL w C ++
Aby drzewo było zrównoważone, współczynnik równowagi dla każdego węzła powinien wynosić od -1 do 1. Jeśli nie, drzewo stanie się niezrównoważone.
Przykładowe drzewo AVL pokazano poniżej.
fałszywy generator konta Gmail i hasło
Na powyższym drzewie możemy zauważyć, że różnica wysokości lewego i prawego poddrzewa wynosi 1. Oznacza to, że jest to zrównoważony BST. Ponieważ współczynnik równoważenia wynosi 1, oznacza to, że lewe poddrzewo jest o jeden poziom wyżej niż prawe poddrzewo.
Jeśli współczynnik równoważenia wynosi 0, oznacza to, że lewe i prawe poddrzewa są na tym samym poziomie, tj. Mają jednakową wysokość. Jeśli współczynnik równoważenia wynosi -1, to lewe poddrzewo jest o jeden poziom niżej niż prawe poddrzewo.
Drzewo AVL kontroluje wysokość binarnego drzewa wyszukiwania i zapobiega jego wypaczeniu. Ponieważ kiedy drzewo binarne zostaje wypaczone, jest to najgorszy przypadek (O (n)) dla wszystkich operacji. Używając współczynnika równowagi, drzewo AVL nakłada ograniczenie na drzewo binarne, a tym samym utrzymuje wszystkie operacje na poziomie O (log n).
Operacje na drzewie AVL
Poniżej przedstawiono operacje obsługiwane przez drzewa AVL.
# 1) Wstawianie drzewa AVL
Operacja wstawiania w drzewie C ++ AVL jest taka sama, jak w drzewie wyszukiwania binarnego. Jedyna różnica polega na tym, że aby zachować współczynnik równowagi, musimy obrócić drzewo w lewo lub w prawo, aby nie utraciło równowagi.
# 2) Usunięcie drzewa AVL
Operacja usuwania jest również wykonywana w taki sam sposób, jak operacja usuwania w drzewie wyszukiwania binarnego. Ponownie musimy zrównoważyć drzewo, wykonując kilka obrotów drzewa AVL.
Implementacja drzewa AVL
Poniżej znajduje się program C ++ do zademonstrowania drzewa AVL i jego operacji.
// 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 Wynik:
Przechodzenie w kolejności dla drzewa AVL to:
4 5 8 11 12 17 18
Przechodzenie w kolejności po usunięciu węzła 5:
4 8 11 12 17 18
Zauważ, że użyliśmy przykładowego drzewa pokazanego powyżej, aby zademonstrować drzewo AVL w programie.
Zastosowania drzew AVL
- Drzewa AVL są najczęściej używane do przechowywania zestawów i słowników w pamięci.
- Drzewa AVL są również szeroko stosowane w aplikacjach baz danych, w których wstawianie i usuwanie jest mniej, ale wymagane są częste wyszukiwania danych.
- Jest używany w aplikacjach wymagających ulepszonego wyszukiwania poza aplikacjami bazodanowymi .
Struktura danych HEAP w C ++
Sterta w C ++ jest specjalną strukturą danych opartą na drzewie i jest kompletnym drzewem binarnym.
Stosy mogą być dwojakiego rodzaju:
- Min-sterta : W min-heap najmniejszym elementem jest korzeń drzewa, a każdy węzeł jest większy lub równy swojemu rodzicowi.
- Max-heap : W max-heap, największym elementem jest korzeń drzewa, a każdy węzeł jest mniejszy lub równy swojemu rodzicowi.
Rozważ następującą tablicę elementów:
10 20 30 40 50 60 70
Minimalna sterta dla powyższych danych jest przedstawiona poniżej:
Maksymalna sterta wykorzystująca powyższe dane jest pokazana poniżej:
Sterta binarna C ++
Sterta binarna to typowa implementacja struktury danych sterty.
Sterta binarna ma następujące właściwości:
- Jest to kompletne drzewo binarne, w którym wszystkie poziomy są całkowicie wypełnione, z wyjątkiem ostatniego poziomu, a ostatni poziom ma jak najwięcej kluczy.
- Sterta binarna może być stertą min lub stertą maksymalną.
Sterta binarna jest kompletnym drzewem binarnym i dlatego najlepiej jest przedstawić ją jako tablicę.
Przyjrzyjmy się reprezentacji tablicowej stosu binarnego.
Rozważmy następujący stos binarny.
Na powyższym diagramie przemierzanie stosu binarnego nazywa się porządkiem poziomów.
Tak więc tablica dla powyższego stosu binarnego jest pokazana poniżej jako HeapArr:
jaki jest najlepszy bloker reklam dla Chrome
Jak pokazano powyżej, HeapArr (0) jest katalogiem głównym stosu binarnego. Pozostałe elementy możemy ogólnie przedstawić w następujący sposób:
Jeśli HeapArr (i) jest ithwęzeł w stosie binarnym, a następnie indeksy innych węzłów z ithwęzeł to:
- HeapArr ((i-1) / 2) => Zwraca węzeł nadrzędny.
- HeapArr ((2 * i) +1) => Zwraca lewy węzeł podrzędny.
- HeapArr ((2 * i) +2) => Zwraca prawy węzeł podrzędny.
Sterta binarna spełnia „właściwość porządkowania”, która ma dwa typy, jak podano poniżej:
- Właściwość Min Heap: Minimalna wartość znajduje się w korzeniu, a wartość każdego węzła jest większa lub równa jego rodzicowi.
- Właściwość Max Heap: Maksymalna wartość znajduje się w katalogu głównym, a wartość każdego węzła jest mniejsza lub równa jego rodzicowi.
Operacje na stosie binarnym
Poniżej przedstawiono podstawowe operacje wykonywane na minimalnym stosie. W przypadku maksymalnego stosu operacje odpowiednio się odwracają.
# 1) Wstaw () - Wstawia nowy klucz na końcu drzewa. W zależności od wartości włożonego klucza może być konieczne dostosowanie sterty bez naruszania właściwości sterty.
# 2) Usuń () - Usuwa klucz. Uwaga że złożoność czasowa zarówno operacji wstawiania, jak i usuwania sterty wynosi O (log n).
# 3) Zmniejsz Klucz () - Zmniejsza wartość klucza. Może być konieczne zachowanie właściwości sterty podczas wykonywania tej operacji. Złożoność czasowa operacji dropKey na stercie również wynosi O (log n).
# 4) extractMin () - Usuwa minimalny element ze sterty min. Musi zachować właściwość sterty po usunięciu minimalnego elementu. Zatem jego złożoność czasowa wynosi O (log n).
# 5) getMin () - Zwraca element główny sterty min. To jest najprostsza operacja, a jej złożoność czasowa wynosi O (1).
Implementacja struktury danych sterty
Poniżej podano implementację C ++, aby zademonstrować podstawową funkcjonalność 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: '< Wynik:
Sterta po włożeniu: 2 4 6 8 10 12
korzeń sterty: 2
Sterta po deletekey (2): 2 4 12 8 10
minimalny element w stercie: 2
nowy katalog główny sterty po zmniejszeniu Klucz: 1
Applications Of Heaps
- Heapsort: Algorytm Heapsort jest skutecznie implementowany przy użyciu binarnej sterty.
- Kolejki priorytetowe: Sterta binarna obsługuje wszystkie operacje wymagane do pomyślnej implementacji kolejek priorytetowych w czasie O (log n).
- Algorytmy graficzne: Niektóre algorytmy związane z grafami wykorzystują kolejkę priorytetową, a kolejka priorytetowa używa stosu binarnego.
- Złożoność algorytmu szybkiego sortowania w najgorszym przypadku można przezwyciężyć za pomocą sortowania stosu.
Wniosek
W tym samouczku widzieliśmy szczegółowo dwie struktury danych, tj. Drzewa AVL i sortowanie na stosie.
Drzewa AVL są zrównoważonymi drzewami binarnymi, które są najczęściej używane do indeksowania baz danych.
Wszystkie operacje wykonywane na drzewach AVL są podobne do tych na drzewach wyszukiwania binarnego, ale jedyna różnica w przypadku drzew AVL polega na tym, że musimy zachować współczynnik równowagi, tj. Struktura danych powinna pozostać zrównoważonym drzewem w wyniku różnych operacji. Osiąga się to za pomocą operacji obracania drzewa AVL.
Sterty to kompletne binarne struktury drzewiaste, które są klasyfikowane jako min-sterta lub max-sterta. Min-sterta ma minimalny element jako główny, a kolejne węzły są większe lub równe ich węzłowi nadrzędnemu. W max-heap sytuacja jest dokładnie odwrotna, tj. Maksymalny element jest pierwiastkiem stosu.
Sterty można przedstawić w postaci tablic z wartością 0thelement jako korzeń drzewa. Struktury danych sterty są używane głównie do implementacji sortowania sterty i kolejek priorytetowych.
=> Odwiedź tutaj, aby nauczyć się C ++ od podstaw.
rekomendowane lektury
- Struktura danych kolejki w C ++ z ilustracjami
- Struktura danych stosu w C ++ z ilustracjami
- Struktura danych listy połączonej cyklicznie w C ++ z ilustracją
- Struktura danych listy połączonej w C ++ z ilustracją
- Wprowadzenie do struktur danych w C ++
- Struktura danych kolejki priorytetowej w C ++ z ilustracją
- Struktura danych listy podwójnie połączonych w C ++ z ilustracjami
- Sortuj na stosie w C ++ z przykładami
