Menü

C ++ 'da AVL Ağacı ve Yığın Veri Yapısı

  • Ana
  • Diğer
  • C ++ 'da AVL Ağacı ve Yığın Veri Yapısı

avl tree heap data structure c

Sorunları Ortadan Kaldırmak Için Enstrümanımızı Deneyin

Bu Öğretici, Daha İyi Anlama için AVL Ağacı Örneklerinin yanı sıra C ++ 'da AVL Ağaçları ve Yığın Veri Yapısının Ayrıntılı Açıklamasını Sağlar:

AVL Ağacı, yüksekliği dengeli bir ikili ağaçtır. Her düğüm, sol alt ağacın yüksekliği ile sağ alt ağacın yüksekliği arasındaki fark olarak hesaplanan dengeli bir faktörle ilişkilendirilir.

AVL ağacı, iki mucidinden, yani G.M. Abelson-Velvety ve E.M. Landis, 1962'de “Bilginin organizasyonu için bir algoritma” adlı makalelerinde yayınlandı.

=> Tüm C ++ Eğitim Serisini Burada Arayın.

C ++

Ne öğreneceksin:

C ++ 'da AVL Ağacı

Ağacın dengelenmesi için her bir düğüm için dengeli faktör -1 ile 1 arasında olmalıdır. Aksi takdirde ağaç dengesiz hale gelecektir.

Örnek bir AVL Ağacı aşağıda gösterilmiştir.

Örnek AVL ağacı

Yukarıdaki ağaçta, sol ve sağ alt ağaçların yükseklik farkının 1 olduğunu görebiliriz. Bu, bunun dengeli bir BST olduğu anlamına gelir. Dengeleme faktörü 1 olduğundan, bu, sol alt ağacın, sağ alt ağaçtan bir düzey daha yüksek olduğu anlamına gelir.

Dengeleme faktörü 0 ise, bu, sol ve sağ alt ağaçların aynı seviyede olduğu, yani eşit yüksekliğe sahip oldukları anlamına gelir. Dengeleme faktörü -1 ise, sol alt ağaç, sağ alt ağaçtan bir düzey daha düşüktür.

AVL ağacı, bir ikili arama ağacının yüksekliğini kontrol eder ve eğrilmesini önler. Çünkü bir ikili ağaç eğik olduğunda, tüm işlemler için en kötü durumdur (O (n)). Denge faktörünü kullanarak, AVL ağacı ikili ağaca bir sınır getirir ve böylece tüm işlemleri O (log n) 'de tutar.

AVL Ağaç İşlemleri

Aşağıdakiler, AVL ağaçları tarafından desteklenen işlemlerdir.

jar dosyasını nasıl çalıştırırım

# 1) AVL Ağaç Ekleme

C ++ AVL ağacına ekleme işlemi, ikili arama ağacınınkiyle aynıdır. Tek fark, denge faktörünü korumak için ağacı, dengesiz hale gelmemesi için sola veya sağa döndürmemiz gerektiğidir.

# 2) AVL Ağacı Silme

Silme işlemi de İkili arama ağacındaki silme işlemiyle aynı şekilde gerçekleştirilir. Yine bazı AVL Ağacı rotasyonları yaparak ağacı yeniden dengelememiz gerekiyor.

AVL Ağacı Uygulaması

Aşağıda, AVL ağacını ve işlemlerini gösteren C ++ programı verilmiştir.

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

Çıktı:

AVL ağacı için sıralı geçiş:

4 5 8 11 12 17 18

Düğüm 5'in silinmesinden sonra sıralı geçiş:

4 8 11 12 17 18

AVL Çıkışı

Programda AVL Ağacını göstermek için yukarıda gösterilen örnek ağacı kullandığımıza dikkat edin.

AVL Ağaçlarının Uygulamaları

  1. AVL ağaçları çoğunlukla bellek içi tür kümeler ve sözlükler için kullanılır.
  2. AVL ağaçları, ekleme ve silme işlemlerinin daha az olduğu, ancak gerekli veri için sık aramaların olduğu veritabanı uygulamalarında da yaygın olarak kullanılır.
  3. Veritabanı uygulamaları dışında gelişmiş arama gerektiren uygulamalarda kullanılır. .

C ++ 'da HEAP Veri Yapısı

C ++ 'da bir yığın, ağaç tabanlı özel bir veri yapısıdır ve tam bir ikili ağaçtır.

Yığınlar iki tipte olabilir:

  • Min-yığın : Min-heap'de, en küçük eleman ağacın köküdür ve her bir düğüm, ebeveyninden büyük veya ona eşittir.
  • Maksimum yığın : Max-heap'de en büyük eleman ağacın köküdür ve her bir düğüm ebeveyninden küçük veya ona eşittir.

Aşağıdaki öğe dizisini düşünün:

10 20 30 40 50 60 70

Yukarıdaki veriler için minimum yığın aşağıda temsil edilmektedir:

min-yığın

Yukarıdaki verileri kullanan maksimum yığın aşağıda gösterilmiştir:

maksimum yığın

İkili Yığın C ++

İkili bir yığın, bir yığın veri yapısının ortak uygulamasıdır.

Bir ikili yığın aşağıdaki özelliklere sahiptir:

  • Muhtemelen son seviye hariç tüm seviyeler tamamen doldurulduğunda tam bir ikili ağaçtır ve son seviyenin anahtarları mümkün olduğunca bırakılmıştır.
  • İkili yığın, min-heap veya max-heap olabilir.

İkili yığın, tam bir ikili ağaçtır ve bu nedenle en iyi şekilde bir dizi olarak temsil edilebilir.

İkili yığının dizi temsiline bakalım.

Aşağıdaki ikili yığını düşünün.

ikili yığın

iş sistemleri analisti mülakat soruları ve cevapları

Yukarıdaki diyagramda, ikili yığın için geçiş, seviye sırası olarak adlandırılır.

Dolayısıyla, yukarıdaki ikili yığın için dizi aşağıda HeapArr olarak gösterilmektedir:

HeapArr

Yukarıda gösterildiği gibi, HeapArr (0) ikili yığının köküdür. Diğer unsurları genel hatlarıyla şu şekilde ifade edebiliriz:

HeapArr (i) bir i iseincibir ikili öbek içindeki düğüm, ardından i'den diğer düğümlerin dizinleriincidüğümler:

  • HeapArr ((i-1) / 2) => Üst düğümü döndürür.
  • HeapArr ((2 * i) +1) => Sol alt düğümü döndürür.
  • HeapArr ((2 * i) +2) => Sağ çocuk düğümü döndürür.

İkili yığın, aşağıda belirtildiği gibi iki tür olan 'sıralama özelliğini' karşılar:

  • Min Yığın özelliği: Minimum değer köktedir ve her bir düğümün değeri ebeveyninden büyük veya ona eşittir.
  • Max Heap özelliği: Maksimum değer köktedir ve her bir düğümün değeri ebeveyninden küçük veya ona eşittir.

İkili Yığın Üzerinde İşlemler

Aşağıdakiler, minimum yığın üzerinde gerçekleştirilen temel işlemlerdir. Maksimum yığın durumunda işlemler buna göre tersine döner.

# 1) Ekle () - Ağacın sonuna yeni bir anahtar ekler. Girilen anahtarın değerine bağlı olarak, heap özelliğini ihlal etmeden öbeği ayarlamamız gerekebilir.

# 2) Sil () - Bir anahtarı siler. Not öbeğin hem ekleme hem de silme işlemlerinin zaman karmaşıklığının O (log n) olduğu.

# 3) azalmaKey () - Anahtarın değerini azaltır. Bu işlem gerçekleştiğinde heap özelliğini korumamız gerekebilir. Yığın düşüş anahtarı işleminin zaman karmaşıklığı da O (log n) 'dir.

# 4) extractMin () - Minimum öğeyi minimum yığınından kaldırır. Minimum öğeyi kaldırdıktan sonra yığın özelliğini korumalıdır. Dolayısıyla, zaman karmaşıklığı O (log n) 'dir.

#5) getMin() - Min-yığınının kök öğesini döndürür. Bu en basit işlemdir ve bu işlem için zaman karmaşıklığı O (1) 'dir.

Yığın Veri Yapısı Uygulaması

Aşağıda, min-heap'in temel işlevselliğini göstermek için C ++ uygulaması verilmiştir.

#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: '<

Çıktı:

Yerleştirmeden sonra yığın: 2 4 6 8 10 12

yığının kökü: 2

Silme sonrası yığın tuşu (2): 2 4 12 8 10

yığındaki minimum öğe: 2

Azaltıldıktan sonra yığının yeni kökü Anahtar: 1

Yığın Çıktısı

Yığın Uygulamaları

  • Yığın sıralaması: Yığın sıralaması algoritması, ikili bir yığın kullanılarak etkin bir şekilde uygulanır.
  • Öncelik Sıraları: İkili yığın, öncelik sıralarının O (log n) zamanında başarıyla uygulanması için gereken tüm işlemleri destekler.
  • Grafik algoritmaları: Grafiklerle ilgili bazı algoritmalar öncelik sırasını kullanır ve sırayla öncelik sırası ikili yığın kullanır.
  • Hızlı sıralama algoritmasının en kötü durum karmaşıklığı yığın sıralama kullanılarak aşılabilir.

Sonuç

Bu eğiticide, iki veri yapısı, yani AVL ağaçları ve Yığın sıralaması ayrıntılı olarak gördük.

AVL ağaçları, çoğunlukla veritabanı indekslemede kullanılan dengeli ikili ağaçlardır.

hangi programlar c ++ kullanıyor

AVL ağaçlarında gerçekleştirilen tüm işlemler, ikili arama ağaçlarınınkine benzer, ancak AVL ağaçları durumunda tek fark, denge faktörünü korumamız gerektiğidir, yani veri yapısı çeşitli işlemlerin bir sonucu olarak dengeli bir ağaç olarak kalmalıdır. Bu, AVL Ağaç Döndürme işlemi kullanılarak elde edilir.

Yığınlar, min-heap veya max-heap olarak sınıflandırılan tam ikili ağaç yapılarıdır. Min-heap, kökü olarak minimum elemana sahiptir ve sonraki düğümler ebeveyn düğümlerinden büyük veya ona eşittir. Max-heap'de durum tam tersidir, yani maksimum eleman yığının köküdür.

Yığınlar, 0 ile diziler şeklinde temsil edilebilirinciağacın kökü olarak öğe. Yığın veri yapıları, çoğunlukla yığın sıralaması ve öncelik sıralarını uygulamak için kullanılır.

=> Sıfırdan C ++ Öğrenmek İçin Burayı Ziyaret Edin.

Önerilen Kaynaklar

^