İndekslənmiş ikili ağac

Aşağıdakı problem növü ilə qarşılaşdım. Aşağıdakı funksionallığı təmin edən məlumat saxlama qabını tətbiq etmək lazımdır:

• yeni element daxil edin
• elementi seriya nömrəsi ilə çıxarın
• elementi sıra nömrəsi ilə əldə edin
• məlumatlar çeşidlənmiş formada saxlanılır

Məlumatlar daim əlavə olunur və silinir, struktur sürətli əməliyyat sürətini təmin etməlidir. Əvvəlcə standart konteynerlərdən istifadə edərək belə bir şeyi həyata keçirməyə çalışdım std. Bu yol müvəffəqiyyətlə taclanmadı və başa düşdüm ki, mən özüm nəyisə həyata keçirməliyəm. Ağlıma gələn tək şey ikili axtarış ağacından istifadə etmək idi. Çünki o, məlumatların çeşidlənmiş formada sürətli daxil edilməsi, silinməsi və saxlanması tələbinə cavab verir. Bütün elementləri indeksləşdirməyi və ağac dəyişdikdə indeksləri yenidən hesablamağı anlamaq qalır.

struct node_s {    
    data_t data;

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

    node_t *left;
    node_t *right;

    node_t *parent;
};

Məqalədə koddan daha çox şəkil və nəzəriyyə olacaq. Koda aşağıdakı linkdən baxmaq olar.

Çəki

Buna nail olmaq üçün ağacda kiçik bir dəyişiklik edildi, haqqında əlavə məlumatlar əlavə edildi çəki düyün. Düyün çəkisi bu node nəslinin sayı + 1 (tək elementin çəkisi).

Düyün çəkisini almaq üçün funksiya:

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

    return 0;
}

Vərəqin çəkisi müvafiq olaraq bərabərdir 0.

Sonra, belə bir ağacın nümunəsinin vizual təsvirinə keçək. Qara node açarı rəngli göstəriləcək (dəyər göstərilməyəcək, çünki bu lazım deyil), qırmızı - düyün çəkisi, yaşıl - qovşaq indeksi.

Ağacımız boş olduqda onun çəkisi 0-dır. Ona kök elementi əlavə edək:

Ağacın çəkisi 1, kök elementinin çəkisi 1 olur. Kök elementin çəkisi ağacın çəkisidir.

Daha bir neçə element əlavə edək:

Hər dəfə yeni bir element əlavə edildikdə, biz qovşaqlardan aşağı enirik və keçən hər bir nodeun çəki sayğacını artırırıq. Yeni bir node yaradıldıqda, ona bir çəki təyin edilir 1. Əgər belə bir açarı olan bir qovşaq artıq mövcuddursa, biz keçdiyimiz bütün qovşaqların çəkilərindəki dəyişiklikləri ləğv edərək, dəyərin üzərinə yazacağıq və kökə qayıdacağıq.
Bir düyün çıxarılırsa, aşağı enib keçən qovşaqların çəkisini azaldırıq.

Indeksləri

İndi keçək qovşaqları necə indeksləşdirməyə. Düyünlər indekslərini açıq şəkildə saxlamır, qovşaqların çəkisi əsasında hesablanır. Əgər indekslərini saxlasalar, o zaman tələb olunacaq O (n) ağacdakı hər dəyişiklikdən sonra bütün qovşaqların indekslərini yeniləmək üçün vaxt.
Vizual təqdimata keçək. Ağacımız boşdur, ona 1-ci node əlavə edək:

Birinci node bir indeksə malikdir 0, və indi 2 hal mümkündür. Birincidə kök elementin indeksi dəyişəcək, ikincisində dəyişməyəcək.

Kökdə sol alt ağacın çəkisi 1-dir.

İkinci hal:

Kökün indeksi dəyişmədi, çünki onun sol alt ağacının çəkisi 0 olaraq qaldı.

Bir node indeksi onun sol alt ağacının çəkisi + valideyndən alınan nömrə kimi hesablanır. Bu rəqəm nədir?, Bu indeks sayğacıdır, əvvəlcə ona bərabərdir 0, çünki kökün valideyni yoxdur. Sonra hər şey sol uşağa və ya sağa endiyimiz yerdən asılıdır. Əgər sola, onda sayğaca heç nə əlavə olunmur. Cari qovşağın indeksini sağa əlavə etsək.

Məsələn, 8 açarı olan elementin indeksi (kökün sağ uşağı) necə hesablanır. Bu, "Kök İndeksi" + "8 düyməsi olan qovşağın sol alt ağacının çəkisi" + "1" == 3 + 2 + 1 == 6
6 açarı olan elementin indeksi "Kök İndeksi" + 1 == 3 + 1 == olacaq 4

Müvafiq olaraq, elementi indekslə əldə etmək və silmək üçün vaxt lazımdır O (log n), çünki istədiyiniz elementi əldə etmək üçün ilk növbədə onu tapmaq lazımdır (kökdən bu elementə enmək).

Dərinlik

Ağırlığa əsasən, ağacın dərinliyini də hesablaya bilərsiniz. Balans üçün lazımdır.
Bunun üçün cari düyünün çəkisi verilmiş çəkidən böyük və ya ona bərabər olan 2-nin gücünə birinci ədədə yuvarlaqlaşdırılmalı və ondan ikili loqarifmi götürməlidir. Bu, tarazlı olduğunu fərz etsək, ağacın dərinliyini verəcəkdir. Ağac yeni element daxil etdikdən sonra balanslaşdırılır. Ağacları necə tarazlaşdırmaq barədə bir nəzəriyyə verməyəcəyəm. Mənbə kodları balanslaşdırma funksiyasını təmin edir.

Ağırlığı dərinliyə çevirmək üçün kod.

/*
 * Возвращает первое число в степени 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));
}

Nəticələri

• yeni elementin daxil edilməsi baş verir O (log n)
• elementin seriya nömrəsi ilə silinməsi ilə baş verir O (log n)
• elementin seriya nömrəsi ilə əldə edilməsi baş verir O (log n)

Sürət O (log n) Bütün məlumatların çeşidlənmiş formada saxlanmasına görə ödəyirik.

Belə bir quruluşun harada faydalı ola biləcəyini bilmirəm. Ağacların necə işlədiyini bir daha başa düşmək üçün sadəcə bir tapmaca. Diqqətinizə görə təşəkkürlər.

References

• Ağac mənbə kodu

Layihədə əməliyyat sürətini yoxlamaq üçün test məlumatları var. Ağac dolur 1000000 elementləri. Və elementlərin ardıcıl silinməsi, daxil edilməsi və axtarışı var 1000000 bir dəfə. Yəni 3000000 əməliyyatlar. Nəticə olduqca yaxşı oldu ~ 8 saniyə.

Mənbə: www.habr.com