Dizine alınmış ikili ağaç

Aşağıdaki türde bir sorunla karşılaştım. Aşağıdaki işlevleri sağlayan bir veri depolama konteynerinin uygulanması gereklidir:

• yeni öğe ekle
• öğeyi seri numarasına göre kaldır
• sıra numarasına göre eleman al
• veriler sıralanmış biçimde saklanır

Veriler sürekli olarak ekleniyor ve çıkarılıyor, yapının hızlı işlem hızını sağlaması gerekiyor. İlk başta standart kapları kullanarak böyle bir şeyi uygulamaya çalıştım. std. Bu yol başarı ile taçlandırılmadı ve bir şeyi kendim uygulamam gerektiği anlayışı geldi. Aklıma gelen tek şey ikili arama ağacı kullanmaktı. Çünkü verilerin hızlı eklenmesi, silinmesi ve sıralanmış biçimde saklanması ihtiyacını karşılamaktadır. Geriye kalan tek şey, tüm öğelerin nasıl indeksleneceğini bulmak ve ağaç değiştiğinde indeksleri yeniden hesaplamaktır.

struct node_s {    
    data_t data;

    uint64_t weight; // вес узла

    node_t *left;
    node_t *right;

    node_t *parent;
};

Makale koddan çok resim ve teori içerecektir. Kodu aşağıdaki bağlantıdan görebilirsiniz.

ağırlık

Bunu başarmak için ağaçta küçük bir değişiklik yapıldı ve hakkında ek bilgiler eklendi. ağırlık düğüm. Düğüm ağırlığı bu düğümün soyundan gelenlerin sayısı + 1 (tek bir elemanın ağırlığı).

Düğüm ağırlığını alma işlevi:

uint64_t bntree::get_child_weight(node_t *node) {
    if (node) {
        return node->weight;
    }

    return 0;
}

Sayfanın ağırlığı buna karşılık olarak eşittir 0.

Şimdi böyle bir ağaç örneğinin görsel temsiline geçelim. Siyah düğüm anahtarı renkli gösterilecektir (bu gerekli olmadığından değer gösterilmeyecektir), kırmızı - düğüm ağırlığı, yeşil — düğüm indeksi.

Ağacımız boş olduğunda ağırlığı 0 olur. Ona bir kök eleman ekleyelim:

Ağacın ağırlığı 1, kök elemanın ağırlığı 1 olur. Kök elemanın ağırlığı ağacın ağırlığıdır.

Birkaç öğe daha ekleyelim:

Her yeni eleman eklendiğinde, düğümlerin altına iniyoruz ve geçen her düğümün ağırlık sayacını arttırıyoruz. Yeni bir düğüm oluşturulduğunda ona bir ağırlık atanır. 1. Böyle bir anahtara sahip bir düğüm zaten mevcutsa, değerin üzerine yazacağız ve köke geri döneceğiz, geçtiğimiz tüm düğümlerin ağırlıklarındaki değişiklikleri iptal edeceğiz.
Bir düğüm kaldırılıyorsa aşağı ineriz ve geçirilen düğümlerin ağırlıklarını azaltırız.

Endeksler

Şimdi düğümlerin nasıl indeksleneceğine geçelim. Düğümler indekslerini açıkça saklamaz, düğümlerin ağırlığına göre hesaplanır. Eğer indekslerini sakladılarsa, bu gerekli olacaktır. O (n) Ağaçtaki her değişiklikten sonra tüm düğümlerin dizinlerini güncelleme zamanı.
Şimdi görsel anlatıma geçelim. Ağacımız boş, ona 1. düğümü ekleyelim:

İlk düğümün bir dizini var 0ve şimdi 2 durum mümkün. Birincisinde kök elemanın indeksi değişecek, ikincisinde ise değişmeyecektir.

Kökte sol alt ağacın ağırlığı 1'dir.

İkinci durum:

Kökün indeksi değişmedi çünkü sol alt ağacın ağırlığı 0 kaldı.

Bir düğümün dizini, sol alt ağacının ağırlığı + üst öğeden iletilen sayı olarak hesaplanır. Bu sayı nedir?, Bu indeks sayacıdır, başlangıçta eşittir 0, Çünkü kökün ebeveyni yoktur. O zaman her şey sol çocuğa veya sağ çocuğa nereye gittiğimize bağlıdır. Solda ise sayaca hiçbir şey eklenmez. Geçerli düğümün indeksini sağdakine eklersek.

Örneğin, anahtarı 8 olan (kökün sağ çocuğu) bir elemanın indeksi nasıl hesaplanır. Bu "Kök İndeksi" + "8 numaralı düğümün sol alt ağacının ağırlığı" + "1" == 3 + 2 + 1 == 6
6 anahtarına sahip öğenin dizini "Kök Dizini" + 1 == 3 + 1 == olacaktır. 4

Buna göre bir öğenin dizine göre alınması ve silinmesi zaman alır O (log n)çünkü istenen öğeyi elde etmek için önce onu bulmalıyız (kökten bu öğeye inmeliyiz).

derinlik

Ağırlığa bağlı olarak ağacın derinliğini de hesaplayabilirsiniz. Dengeleme için gereklidir.
Bunu yapmak için, mevcut düğümün ağırlığı, verilen ağırlıktan büyük veya ona eşit olan 2'nin üssü ilk sayıya yuvarlanmalı ve bundan ikili logaritması alınmalıdır. Dengeli olduğunu varsayarak bu bize ağacın derinliğini verecektir. Yeni bir öğe eklendikten sonra ağaç dengelenir. Ağaçların nasıl dengeleneceğine dair bir teori vermeyeceğim. Kaynak kodları bir dengeleme işlevi sağlar.

Ağırlığı derinliğe dönüştürme kodu.

/*
 * Возвращает первое число в степени 2, которое больше или ровно x
 */
uint64_t bntree::cpl2(uint64_t x) {
    x = x - 1;
    x = x | (x >> 1);
    x = x | (x >> 2);
    x = x | (x >> 4);
    x = x | (x >> 8);
    x = x | (x >> 16);
    x = x | (x >> 32);

    return x + 1;
}

/*
 * Двоичный логарифм от числа
 */
long bntree::ilog2(long d) {
    int result;
    std::frexp(d, &result);
    return result - 1;
}

/*
 * Вес к глубине
 */
uint64_t bntree::weight_to_depth(node_t *p) {
    if (p == NULL) {
        return 0;
    }

    if (p->weight == 1) {
        return 1;
    } else if (p->weight == 2) {
        return 2;
    }

    return this->ilog2(this->cpl2(p->weight));
}

sonuçlar

• yeni bir elemanın eklenmesi gerçekleşir O (log n)
• bir öğenin seri numarasına göre silinmesi O (log n)
• Seri numarasına göre bir elemanın elde edilmesi şu şekilde gerçekleşir: O (log n)

Hız O (log n) Tüm verilerin sıralanmış biçimde saklanması için ödeme yapıyoruz.

Böyle bir yapının nerede yararlı olabileceğini bilmiyorum. Ağaçların nasıl çalıştığını bir kez daha anlamak için sadece bir bulmaca. İlginiz için teşekkür ederiz.

referanslar

• Ağaç kaynak kodu

Proje, çalışma hızını kontrol etmek için test verilerini içerir. Ağaç doluyor 1000000 elementler. Ve öğelerin sıralı olarak silinmesi, eklenmesi ve alınması vardır 1000000 bir kere. Yani 3000000 operasyonlar. Sonuç oldukça iyi çıktı ~ 8 saniye.

Kaynak: habr.com