Tangkal binér indéks

Kuring datang di sakuliah jenis handap masalah. Perlu nerapkeun wadah panyimpen data anu nyayogikeun pungsionalitas ieu:

• nyelapkeun unsur anyar
• miceun unsur ku nomer serial
• meunang unsur ku angka ordinal
• data disimpen dina bentuk diurutkeun

Data terus-terusan ditambah sareng dipiceun, strukturna kedah mastikeun laju operasi gancang. Mimitina kuring nyobian ngalaksanakeun hal sapertos nganggo wadah standar tina STD. jalur ieu teu crowned kalawan kasuksésan sarta pamahaman sumping yén kuring diperlukeun pikeun nerapkeun hiji hal sorangan. Hiji-hijina hal anu datang ka pikiran éta ngagunakeun tangkal pilarian binér. Sabab meets sarat tina sisipan gancang, ngahapus jeung neundeun data dina bentuk diurutkeun. Sadaya anu tetep nyaéta kumaha carana ngindeks sadaya unsur sareng ngitung deui indéks nalika tangkalna robih.

struct node_s {    
    data_t data;

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

    node_t *left;
    node_t *right;

    node_t *parent;
};

Artikel bakal ngandung leuwih gambar jeung téori ti kode. Kodeu tiasa ditingali dina tautan di handap.

beurat

Pikeun ngahontal ieu, tangkal underwent a modifikasi slight, informasi tambahan ieu ditambahkeun ngeunaan beurat titik. Beurat titik nyaéta Jumlah turunan tina titik ieu + 1 (beurat hiji unsur).

Fungsi pikeun meunangkeun beurat titik:

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

    return 0;
}

Beurat lambar téh correspondingly sarua jeung 0.

Salajengna, hayu urang ngaléngkah ka gambaran visual ngeunaan conto tangkal sapertos kitu. Hideung konci titik bakal ditingalikeun dina warna (nilaina moal ditingalikeun, sabab ieu henteu diperyogikeun), beureum - beurat simpul, hejo - indéks titik.

Nalika tangkal urang kosong, beuratna 0. Hayu urang tambahkeun unsur akar kana éta:

Beurat tangkal jadi 1, beurat unsur akar jadi 1. Beurat unsur akar beurat tangkal.

Hayu urang tambahkeun sababaraha elemen deui:

Unggal waktos unsur anyar ditambahkeun, urang turun titik jeung ningkatkeun counter beurat unggal titik diliwatan. Nalika titik anyar dijieun, beurat ditugaskeun ka dinya 1. Upami titik anu gaduh konci sapertos kitu parantos aya, maka urang bakal nimpa nilai sareng balik deui ka akar, ngabatalkeun parobihan dina beurat sadaya titik anu urang parantos lulus.
Upami hiji titik dileungitkeun, teras urang turun sareng ngirangan beurat titik anu diliwatan.

Indéks

Ayeuna hayu urang ngaléngkah ka kumaha carana indéks titik. Titik henteu sacara eksplisit nyimpen indéksna, éta diitung dumasar kana beurat titik. Upami aranjeunna nyimpen indéksna, maka éta diperyogikeun O (n) waktos pikeun ngapdet indexes sadaya titik sanggeus unggal robah dina tangkal.
Hayu urang ngaléngkah ka representasi visual. Tangkal kami kosong, hayu urang tambahkeun titik ka-1 kana éta:

Titik kahiji ngagaduhan indéks 0, tur ayeuna 2 kasus anu mungkin. Dina kahiji, indéks unsur root bakal robah, dina kadua moal robah.

Dina akar, subtree kénca beuratna 1.

Kasus kadua:

Indéks akar henteu robih kusabab beurat subtree kéncana tetep 0.

Indéks titik diitung salaku beurat subtree kénca + jumlah anu disalurkeun ti indungna. Naon angka ieu?, Ieu counter indéks, mimitina sarua jeung 0, sabab akarna teu boga kolot. Lajeng eta sadayana gumantung kana dimana urang turun ka anak kénca atawa katuhu. Lamun ka kénca, lajeng nanaon ditambahkeun kana loket. Lamun urang tambahkeun indéks tina titik ayeuna ka katuhu.

Contona, kumaha indéks unsur kalawan konci 8 (anak katuhu akar) diitung. Ieu "Indéks Akar" + "beurat subtree kénca titik kalayan konci 8" + "1" == 3 + 2 + 1 == 6
Indéks unsur sareng konci 6 bakal "Indéks Akar" + 1 == 3 + 1 == 4

Sasuai, butuh waktu pikeun meunangkeun tur mupus hiji unsur ku indéks O (lebet n), sabab pikeun meunangkeun unsur nu dipikahoyong urang kudu manggihan heula (turun ti akar ka unsur ieu).

jerona

Dumasar beurat, anjeun ogé tiasa ngitung jero tangkal. Dipikabutuh pikeun kasaimbangan.
Jang ngalampahkeun ieu, beurat titik ayeuna kudu rounded kana angka kahiji kana kakuatan 2 nu leuwih gede atawa sarua jeung beurat dibikeun tur nyandak logaritma binér ti dinya. Ieu bakal masihan urang jero tangkal, asumsina éta saimbang. Tangkal saimbang saatos nyelapkeun unsur énggal. Kuring moal masihan téori ngeunaan kumaha carana nyaimbangkeun tangkal. Kodeu sumber nyadiakeun fungsi balancing.

Kode pikeun ngarobah beurat kana jero.

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

hasil

• sisipan unsur anyar lumangsung dina O (lebet n)
• mupus unsur ku nomer serial lumangsung dina O (lebet n)
• meunangkeun unsur ku nomer serial lumangsung dina O (lebet n)

Laju O (lebet n) Kami mayar kanyataan yén sadaya data disimpen dina bentuk anu diurutkeun.

Kuring henteu terang dimana struktur sapertos kitu tiasa mangpaat. Ngan tatarucingan pikeun sakali deui ngartos kumaha tatangkalan jalan. Nuhun kana perhatosanana.

rujukan

• Kodeu sumber tangkal

Proyék ngandung data tés pikeun mariksa laju operasi. Tangkal nyuuh 1000000 elemen. Tur aya hiji ngahapus sequential, sisipan jeung dimeunangkeun elemen 1000000 sakali. nyaeta 3000000 operasi. Hasilna tétéla lumayan saé ~ 8 detik.

sumber: www.habr.com