Meni

Struktura podatkov drevesa in kopice AVL v jeziku C ++

  • Glavni
  • Drugo
  • Struktura podatkov drevesa in kopice AVL v jeziku C ++

avl tree heap data structure c

Preizkusite Naš Instrument Za Odpravo Težav

primarne pravice dostopa do datotek v unixu so:

Ta vadnica ponuja podrobno razlago dreves AVL in strukture podatkov kopice v jeziku C ++ ter primere dreves AVL za boljše razumevanje:

AVL Tree je binarno drevo z uravnoteženo višino. Vsako vozlišče je povezano z uravnoteženim faktorjem, ki se izračuna kot razlika med višino levega in desnega poddrevesa.

Drevo AVL je dobilo ime po dveh izumiteljih, tj. G.M. Abelson-Velvety in E. M. Landis, objavljen pa je bil leta 1962 v prispevku 'Algoritem za organizacijo informacij'.

=> Poiščite celotno serijo usposabljanj za C ++ tukaj.

AVL drevesa in struktura podatkov o kopici v jeziku C ++

Kaj se boste naučili:

Drevo AVL v jeziku C ++

Da bi bilo drevo uravnoteženo, mora biti uravnoteženi faktor za vsako vozlišče med -1 in 1. V nasprotnem primeru bo drevo postalo neuravnoteženo.

Primer drevesa AVL je prikazan spodaj.

Primer drevesa AVL

V zgornjem drevesu lahko opazimo, da je razlika v višini levega in desnega pod drevesa enaka 1. To pomeni, da gre za uravnotežen BST. Ker je izravnalni faktor 1, to pomeni, da je levo poddrevo eno stopnjo višje od desnega.

Če je izravnalni faktor 0, potem to pomeni, da sta levo in desno poddrevje na isti ravni, torej vsebujeta enako višino. Če je izravnalni faktor -1, je levo poddrevo eno stopnjo nižje od desnega.

Drevo AVL nadzoruje višino binarnega drevesa iskanja in preprečuje, da bi se poševilo. Ker je binarno drevo poševno, je to najslabši primer (O (n)) za vse operacije. Z uporabo faktorja ravnovesja drevo AVL naloži omejitev binarnemu drevesu in tako ohrani vse operacije pri O (log n).

Delovanje dreves AVL

Sledijo operacije, ki jih podpirajo drevesa AVL.

# 1) Vstavljanje drevesa AVL

Postopek vstavljanja v drevo C ++ AVL je enak postopku binarnega drevesa iskanja. Edina razlika je v tem, da moramo za ohranitev faktorja ravnotežja drevo zasukati v levo ali desno, da ne postane neuravnoteženo.

# 2) Izbris drevesa AVL

Tudi operacija brisanja se izvede na enak način kot operacija brisanja v binarnem drevesu iskanja. Spet moramo ponovno uravnotežiti drevo tako, da izvedemo nekaj rotacij AVL Tree.

Izvedba drevesa AVL

Sledi program C ++ za prikaz drevesa AVL in njegovega delovanja.

// 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

Izhod:

Prehod med drevesi AVL je:

4 5 8 11 12 17 18

Prehod po prehodu po izbrisu vozlišča 5:

4 8 11 12 17 18

AVL izhod

Upoštevajte, da smo uporabili zgoraj prikazano drevo za prikaz drevesa AVL v programu.

Aplikacije dreves AVL

  1. Drevesa AVL se večinoma uporabljajo za vrste naborov in slovarjev v pomnilniku.
  2. Drevesa AVL se pogosto uporabljajo tudi v aplikacijah zbirk podatkov, pri katerih je vstavljanj in brisanj manj, vendar se zahtevane podatke pogosto išče.
  3. Uporablja se v aplikacijah, ki zahtevajo boljše iskanje, razen aplikacij v zbirki podatkov .

Struktura podatkov HEAP v jeziku C ++

Kup v jeziku C ++ je posebna podatkovna struktura, ki temelji na drevesu, in je popolno binarno drevo.

Kupi so lahko dve vrsti:

  • Min kup : V min-heap je najmanjši element koren drevesa in vsako vozlišče je večje ali enako nadrejenemu.
  • Največja kopica : V max-heap je največji element koren drevesa in vsako vozlišče je manjše ali enako nadrejenemu.

Upoštevajte naslednjo paleto elementov:

10 20 30 40 50 60 70

Minimalna kopica za zgornje podatke je predstavljena spodaj:

min-kup

Spodaj je prikazan največji kup z uporabo zgornjih podatkov:

največ kup

Binarni kup C ++

Binarni kup je običajna izvedba podatkovne strukture kopice.

Binarna kopica ima naslednje lastnosti:

  • To je popolno binarno drevo, ko so vse stopnje popolnoma zapolnjene, razen morda zadnje ravni, zadnja stopnja pa ima čim več ključev.
  • Binarni kup je lahko min-heap ali max-heap.

Binarni kup je popolno binarno drevo in ga je zato najbolje predstaviti kot matriko.

Oglejmo si matrično predstavitev binarne kopice.

Razmislite o naslednjem binarnem kupu.

binarni kup

V zgornjem diagramu se prehod za binarno kopico imenuje nivojski vrstni red.

Tako je matrika za zgornji binarni kup prikazana spodaj kot HeapArr:

HeapArr

Kot je prikazano zgoraj, je HeapArr (0) koren binarne kopice. Ostale elemente lahko na splošno predstavimo na naslednji način:

Če je HeapArr (i) ithvozlišče v binarni kopici, nato indeksi drugih vozlišč iz ithvozlišče so:

  • HeapArr ((i-1) / 2) => Vrne nadrejeno vozlišče.
  • HeapArr ((2 * i) +1) => Vrne levo podrejeno vozlišče.
  • HeapArr ((2 * i) +2) => Vrne desno podrejeno vozlišče.

Binarna kopica izpolnjuje dve lastnosti, kot je navedeno spodaj:

  • Lastnost Min Heap: Najmanjša vrednost je v korenu in vrednost vsakega vozlišča je večja ali enaka nadrejenemu.
  • Lastnost Max Heap: Največja vrednost je v korenu in vrednost vsakega vozlišča je manjša ali enaka nadrejenemu.

Operacije na binarnem kupu

Sledijo osnovne operacije, ki se izvajajo na minimalni kopici. V primeru največjega kopičenja se postopki ustrezno obrnejo.

# 1) Vstavi () - Vstavi nov ključ na koncu drevesa. Glede na vrednost vstavljenega ključa bomo morda morali prilagoditi kopico, ne da bi pri tem kršili lastnost kopice.

# 2) Izbriši () - Izbriše ključ. Opomba da je časovna zapletenost operacij vstavljanja in brisanja kopice O (log n).

# 3) reduceKey () - Zmanjša vrednost ključa. Ko se izvede ta operacija, bomo morda morali vzdrževati lastnost kopice. Časovna zapletenost padajočega ključnega delovanja kupa je tudi O (log n).

# 4) extractMin () - Odstrani najmanjši element iz min-kopice. Po odstranitvi najmanjšega elementa mora ohranjati lastnost kopice. Tako je njegova časovna zapletenost O (log n).

# 5) getMin () - Vrne korenski element min-kopice. To je najpreprostejša operacija in časovna zahtevnost te operacije je O (1).

Izvajanje strukture podatkov o kopici

Spodaj je predstavljena izvedba C ++ za prikaz osnovne funkcionalnosti 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: '<

Izhod:

Kup po vstavitvi: 2 4 6 8 10 12

kaj je dober prenosnik glasbe za android

koren kupa: 2

Kup po tipki za brisanje (2): 2 4 12 8 10

najmanjši element na kopici: 2

nov koren kupa po znižanjuKljuč: 1

Izpis kopičenja

Uporabe kopic

  • Heapsort: Algoritem Heapsort se učinkovito izvaja z binarno kopijo.
  • Prednostne čakalne vrste: Binarni kup podpira vse operacije, potrebne za uspešno izvajanje prioritetnih čakalnih vrst v času O (log n).
  • Grafični algoritmi: Nekateri algoritmi, povezani z grafi, uporabljajo prednostno vrsto, prednostna vrsta pa binarno kopico.
  • Najslabšo zapletenost algoritma hitrega sortiranja je mogoče premagati z uporabo sortiranja kopice.

Zaključek

V tej vadnici smo podrobno videli dve podatkovni strukturi, npr. Drevesa AVL in sortiranje kopice.

Drevesa AVL so uravnotežena binarna drevesa, ki se večinoma uporabljajo pri indeksiranju baz podatkov.

Vse operacije, izvedene na drevesih AVL, so podobne tistim pri binarnih drevesih iskanja, vendar je edina razlika v primeru dreves AVL ta, da moramo vzdrževati faktor ravnotežja, tj.podatkovna struktura naj ostane uravnoteženo drevo kot rezultat različnih operacij. To dosežemo z uporabo operacije vrtenja dreves AVL.

Kupe so popolne binarne drevesne strukture, ki so razvrščene v min-heap ali max-heap. Min-heap ima za koren najmanjši element, naslednja vozlišča pa so večja ali enaka nadrejenemu vozlišču. V primeru max-heap je situacija ravno nasprotna, tj.Maksimalni element je koren kupa.

Kupe lahko predstavimo v obliki nizov z 0thelement kot koren drevesa. Podatkovne strukture kopice se v glavnem uporabljajo za izvajanje vrst razvrščanja kopice in prioritet.

=> Obiščite tukaj, če se želite naučiti C ++ iz nič.

Priporočeno branje

^