İndekslenebilir ikili ağaç

Bana aşağıdaki türde bir görev verildi. Aşağıdaki işlevselliği sağlayan bir veri saklama konteyneri uygulamak gerekiyor:

• yeni bir öğe eklemek
• sıralı numara ile öğeyi silmek
• sıralı numara ile öğeyi almak
• veriler sıralı olarak saklanır

Veriler sürekli eklenip silindiğinden, yapı hızlı çalışma hızını sağlamalıdır. Öncelikle, bunu standart konteynerler kullanarak uygulamayı denedim std. Bu yol başarılı olmadı ve kendim bir şeyler uygulamam gerektiğini anladım. Akla gelen tek şey, hızlı ekleme, silme ve verilerin sıralı bir şekilde saklanmasını sağladığı için ikili arama ağacı kullanmaktı. Tüm öğeleri nasıl indeksleyeceğimi ve ağacın değiştiğinde indeksleri nasıl yeniden hesaplayacağımı düşünmem gerekiyordu.

struct node_s {    
    data_t data;

    uint64_t weight; // düğümün ağırlığı

    node_t *left;
    node_t *right;

    node_t *parent;
};

Makalede daha fazla resim ve teori olacak, kod aşağıdaki bağlantıdan görülebilir.

Çəki

Bunun için ağaçta küçük bir modifikasyon yapıldı, düğüm hakkında ek bilgi eklendi ağırlık düğümün ağırlığı. Ağırlık, bu düğümün alt düğüm sayısıdır + 1 (birim öğenin ağırlığı).

Düğümün ağırlığını alma fonksiyonu:

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

    return 0;
}

Yaprağın ağırlığı ise 0.

Şimdi böyle bir ağacın örneğini görselleştirelim. Siyah renkle düğümün anahtarı gösterilecek (değer gösterilmeyecek çünkü buna gerek yok), kırmızı — düğümün ağırlığı, yeşil — düğümün indeksi.

Ağacımız boşken, ağırlığı 0'dır. Kök öğeyi ekleyelim:

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

Birkaç öğe daha ekleyelim:

Yeni bir öğe eklerken her seferinde, düğümler üzerinden inerek geçtiğimiz her düğümün ağırlık sayacını artırıyoruz. Yeni bir düğüm oluşturulduğunda, ağırlığı belirlenir 1. Eğer böyle bir anahtara sahip düğüm zaten varsa, değeri güncelleriz ve yukarı köke doğru, geçtiğimiz tüm düğümlerin ağırlık değişikliklerini iptal ederek geri döneriz.
Eğer bir düğümü siliyorsak, aşağıya iniyor ve geçtiğimiz düğümlerin ağırlıklarını azaltıyoruz.

İndeksler

Şimdi düğümleri nasıl indeksleyeceğimize geçelim. Düğümlerin açık bir şekilde kendi indekslerini saklamadıklarını, düğümlerin ağırlığına dayanarak hesaplandığını söyleyebilirim. Eğer kendi indekslerini saklarlarsa, gerekecektir O(n) her ağaç değişikliğinden sonra tüm düğümlerin indekslerini güncellemek için zaman alacaktır.
Görselleştirmeye geçelim. Ağacımız boş, içine 1. düğümü ekleyelim:

İlk düğüm indeksini alır 0, şimdi iki durum mümkün. İlk durumda kök öğenin indeksi değişecek, ikincisinde değişmeyecek.

Kökün sol alt ağacı 1 ağırlığındadır.

İkinci durum:

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

Bir düğümün indeksi nasıl hesaplanır, bu sol alt ağacının ağırlığı + ebeveynden alınan sayıdır. O sayı nedir? Bu indeks sayacıdır, başlangıçta değeri 0, çünkü kökün ebeveyni yoktur. Daha sonra her şey sol çocuğa mı yoksa sağ çocuğa mı gittiğimize bağlıdır. Sol çocuğa gitmemiz durumunda sayaca hiçbir şey eklenmez. Sağ çocuğa gidersek, mevcut düğümün indeksine ekleriz.

Örneğin, anahtar 8 olan elemanın indeksi nasıl hesaplanır (kökün sağ çocuğu). Bu, "Kök indeksi" + "anahtar 8 olan düğümün sol alt ağacının ağırlığı" + "1" == 3 + 2 + 1 == 6
Anahtar 6 olan elemanın indeksi "Kök indeksi" + 1 == 3 + 1 == 4

Dolayısıyla bir öğeyi indeksle almak için gereken zaman O(log n), çünkü gerekli elemanı elde etmek için önce onu bulmamız gerekir (kökten o elemana inmemiz gerekir).

Derinlik

Ağırlığa dayanarak ağacın derinliğini de hesaplayabiliriz. Bu, dengelemek için gereklidir.
Bunun için, mevcut düğümün ağırlığını, bu ağırlıktan büyük veya eşit olan 2'nin ilk kuvvetine yuvarlamak ve ondan ikili logaritma almak gerekir. Böylece, ağacın dengeli olduğu varsayımı altında ağacın derinliğini elde ederiz. Yeni bir eleman eklendikten sonra ağaç dengelenir. Ağaçları dengelemekle ilgili teoriyi burada vermeyeceğim. Kaynak kodlarda dengeleme işlevi bulunmaktadır.

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));
}

Yekunlar

• Yeni bir elemanın eklenmesi O(log n)
• sıralı numara ile elemanın silinmesi O(log n)
• sıralı numara ile elemanın alınması O(log n)

Hız O(log n) Verilerin sıralı bir biçimde saklanmasının bedelini ödüyoruz.

Böyle bir yapının nerede işe yarayacağına dair fikrim yok. Sadece ağaçların nasıl çalıştığını tekrar anlamak için bir problem. İlgilendiğiniz için teşekkür ederim.

Bağlantılar

• Ağaç kaynak kodu

Projede, çalışma hızını test etmek için test verileri bulunmaktadır. Ağaç 1000000 öğelerle doldurulur. Ve ardışık olarak silme, ekleme ve elemanları alma işlemleri gerçekleştirilir 1000000 kez. Yani 3000000 işlemler. Sonuç oldukça iyi oldu ~ 8 saniye.

Mənbə: habr.com