Мени

Структура података АВЛ стабла и гомиле у Ц ++

avl tree heap data structure c

Испробајте Наш Инструмент За Елиминисање Проблема

Овај водич пружа детаљно објашњење АВЛ стабала и структуре података гомиле у Ц ++-у, заједно са примерима АВЛ стабла за боље разумевање:

АВЛ стабло је бинарно стабло уравнотежено по висини. Сваки чвор је повезан са уравнотеженим фактором који се израчунава као разлика између висине његовог левог и десног подстабла.

Дрво АВЛ је добило име по своја два проналазача, тј. Г.М. Абелсон-Велвети и Е.М. Ландис, а објављен је 1962. у њиховом раду „Алгоритам за организацију информација“.

=> Овде потражите целу серију обука за Ц ++.

АВЛ дрвеће и структура података гомиле у Ц ++

Шта ћете научити:

АВЛ стабло у Ц ++

Да би стабло било уравнотежено, уравнотежени фактор за сваки чвор требао би бити између -1 и 1. Ако не, стабло ће постати неуравнотежено.

Пример АВЛ стабла је приказан испод.

Пример АВЛ стабла

У горњем стаблу можемо приметити да је разлика у висини левог и десног подстабла 1. То значи да је то уравнотежени БСТ. Како је фактор уравнотежења 1, то значи да је лево подстабло један ниво више од десног подстабла.

Ако је фактор уравнотежења 0, то значи да су лево и десно подстабла на истом нивоу, тј. Садрже једнаку висину. Ако је фактор уравнотежења -1, онда је лево подстабло један ниво ниже од десног подстабла.

АВЛ стабло контролише висину бинарног стабла претраживања и спречава његово искривљење. Јер када бинарно стабло постане искривљено, то је најгори случај (О (н)) за све операције. Користећи фактор равнотеже, АВЛ стабло намеће ограничење бинарном стаблу и тако задржава све операције на О (лог н).

Операције АВЛ стабла

Следе операције које подржавају АВЛ стабла.

# 1) Уметање АВЛ стабла

Операција уметања у стабло Ц ++ АВЛ је иста као и бинарно стабло претраживања. Једина разлика је у томе што да бисмо одржали фактор равнотеже, дрво морамо ротирати лево или десно како не би постало неуравнотежено.

# 2) АВЛ брисање стабла

Операција брисања се такође изводи на исти начин као и операција брисања у бинарном стаблу претраживања. Поново морамо да уравнотежимо дрво извођењем неких ротација АВЛ стабла.

Имплементација АВЛ стабла

Следи програм Ц ++ за демонстрацију АВЛ стабла и његових операција.

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

Излаз:

узорци биографије за тестирање софтвера 2 године искуства

Преокрет за АВЛ стабло је:

4 5 8 11 12 17 18

Унутрашња обилазница након брисања чвора 5:

4 8 11 12 17 18

АВЛ излаз

Имајте на уму да смо користили приказано стабло горе за демонстрацију АВЛ стабла у програму.

Примене АВЛ дрвећа

  1. АВЛ стабла се углавном користе за врсте скупова и речнике у меморији.
  2. АВЛ стабла се такође широко користе у апликацијама база података у којима је уметања и брисања мање, али се често траже подаци који су потребни.
  3. Користи се у апликацијама које захтевају побољшано претраживање осим апликација базе података .

Структура података ХЕАП у језику Ц ++

Гомила у Ц ++-у је посебна структура података заснована на стаблу и представља комплетно бинарно стабло.

Гомиле могу бити две врсте:

  • Мин-гомила : У мин-хеап-у најмањи елемент је корен стабла и сваки чвор је већи или једнак свом родитељу.
  • Мак-хеап : У мак-хеап-у највећи елемент је корен стабла и сваки чвор је мањи или једнак свом родитељу.

Размотрите следећи низ елемената:

10 20 30 40 50 60 70

Минимална гомила за горње податке представљена је у наставку:

мин-гомила

Максимална гомила која користи горње податке приказана је у наставку:

мак гомила

Бинарна гомила Ц ++

Бинарна гомила је уобичајена имплементација структуре података гомиле.

Бинарна гомила има следећа својства:

  • Потпуно је бинарно стабло када су сви нивои потпуно испуњени, осим могућег последњег нивоа, а последњи ниво има своје кључеве што је више могуће.
  • Бинарна гомила може бити мин-хеап или мак-хеап.

Бинарна гомила је комплетно бинарно стабло и стога се најбоље може представити као низ.

Погледајмо приказ низа бинарне хрпе.

Размотрите следећу бинарну гомилу.

бинарна гомила

У горњем дијаграму, обилазак бинарне хрпе назива се редослед нивоа.

Стога је низ за горњу бинарну хрпу приказан испод као ХеапАрр:

претворити цхар низ у инт ц ++

ХеапАрр

Као што је горе приказано, ХеапАрр (0) је корен бинарне хрпе. Остале елементе можемо представити генерално на следећи начин:

Ако је ХеапАрр (и) итхчвор у бинарној гомили, затим индекси осталих чворова из итхчвор су:

  • ХеапАрр ((и-1) / 2) => Враћа надређени чвор.
  • ХеапАрр ((2 * и) +1) => Враћа леви подређени чвор.
  • ХеапАрр ((2 * и) +2) => Даје прави подређени чвор.

Бинарна гомила задовољава „својство наручивања“, које је две врсте, како је наведено у наставку:

  • Својство Мин Хеап: Минимална вредност је у корену, а вредност сваког чвора је већа или једнака надређеном.
  • Својство Мак Хеап: Максимална вредност је у корену, а вредност сваког чвора је мања или једнака надређеном.

Операције на бинарној гомили

Следе основне операције које се изводе на минималној гомили. У случају максималне гомиле, операције се обрћу у складу с тим.

# 1) Уметни () - Убацује нови кључ на крај стабла. У зависности од вредности убаченог кључа, можда ћемо морати да прилагодимо гомилу, без кршења својства гомиле.

# 2) Избриши () - Брише кључ. Белешка да је временска сложеност операција уметања и брисања гомиле О (лог н).

# 3) редуцеКеи () - Смањује вредност кључа. Можда ће бити потребно да одржавамо својство гомиле када се одвија ова операција. Временска сложеност смањењаКључни рад гомиле је такође О (лог н).

# 4) ектрацтМин () - Уклања минимални елемент из мин-хеап-а. Потребно је да одржи својство гомиле након уклањања минималног елемента. Стога је његова временска сложеност О (лог н).

# 5) гетМин () - Враћа основни елемент мин-хеап-а. Ово је најједноставнија операција, а временска сложеност ове операције је О (1).

Имплементација структуре података гомиле

Доље је дата примена Ц ++ за демонстрацију основне функционалности мин-хеап-а.

#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

Излаз гомиле

Примене гомиле

  • Хеапсорт: Хеапсорт алгоритам се ефикасно имплементира помоћу бинарне хрпе.
  • Приоритетни редови: Бинарна гомила подржава све операције потребне за успешну примену редова приоритета у О (лог н) времену.
  • Графички алгоритми: Неки од алгоритама који се односе на графиконе користе ред приоритета, а ред приоритета користи бинарну хрпу.
  • Сложеност алгоритма брзог сортирања у најгорем случају може се превазићи коришћењем сортирања гомиле.

Закључак

У овом упутству видели смо две структуре података, тј. АВЛ стабла и Хеап детаљно сортирање.

АВЛ стабла су уравнотежена бинарна стабла која се углавном користе у индексирању базе података.

Све операције изведене на АВЛ стаблима сличне су операцијама бинарних стабала претраживања, али једина разлика у случају АВЛ стабала је та што морамо одржавати фактор равнотеже, тј. Структура података треба да остане уравнотежено стабло као резултат различитих операција. То се постиже коришћењем операције АВЛ ротације дрвета.

Гомиле су комплетне бинарне структуре стабла које се класификују у мин-хеап или мак-хеап. Мин-хеап има као основни елемент минимални елемент, а следећи чворови су већи или једнаки њиховом надређеном чвору. У мак-хеап-у је ситуација потпуно супротна, тј. Максимални елемент је корен гомиле.

Гомиле се могу представити у облику низова са 0тхелемент као корен стабла. Структуре података гомиле углавном се користе за примену редова сортирања хрпе и приоритета.

=> Посетите овде да бисте научили Ц ++ из огреботина.

ц # питања за интервју за искусне

Препоручено читање

^