🥇Wit binar sing bisa diindeks

Aku nemoni jinis masalah ing ngisor iki. Sampeyan kudu ngetrapake wadhah panyimpenan data sing nyedhiyakake fungsi ing ngisor iki:

masang unsur anyar
mbusak unsur dening nomer serial
entuk unsur kanthi nomer ordinal
data disimpen ing wangun diurutake

Data terus ditambah lan dicopot, struktur kasebut kudu njamin kacepetan operasi sing cepet. Ing kawitan aku nyoba kanggo ngleksanakake bab kuwi nggunakake kontaner standar saka STD. Path iki ora makutha karo sukses lan pangerten teka aku kudu ngleksanakake soko dhewe. Siji-sijine sing dipikirake yaiku nggunakake wit telusuran binar. Amarga meets requirement selipan cepet, pambusakan lan panyimpenan saka data ing wangun diurutake. Kabeh sing isih ana yaiku kanggo nemtokake cara ngindeks kabeh unsur lan ngitung maneh indeks nalika wit kasebut owah.

struct node_s {    
    data_t data;

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

    node_t *left;
    node_t *right;

    node_t *parent;
};

Artikel kasebut bakal ngemot luwih akeh gambar lan teori tinimbang kode. Kode kasebut bisa dideleng ing tautan ing ngisor iki.

Bobot

Kanggo entuk iki, wit kasebut ngalami modifikasi tipis, informasi tambahan ditambahake bobot simpul. Bobot simpul yaiku jumlah keturunan simpul iki + 1 (bobot siji unsur).

Fungsi kanggo njupuk bobot simpul:

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

    return 0;
}

Bobot lembaran kasebut cocog karo 0.

Sabanjure, ayo pindhah menyang representasi visual saka conto wit kasebut. ireng tombol simpul bakal ditampilake ing werna (nilai ora bakal ditampilake, amarga iki ora perlu), abang - bobot simpul, ijo - indeks node.

Nalika wit kita kosong, bobote 0. Ayo ditambahake unsur ROOT:

Bobot wit dadi 1, bobot unsur oyod dadi 1. Bobot unsur oyot yaiku bobot wit.

Ayo nambah sawetara unsur liyane:

Saben unsur anyar ditambahake, kita mudhun kelenjar lan nambah bobot counter saben simpul liwati. Nalika simpul anyar digawe, bobot ditugasake 1. Yen simpul kanthi kunci kasebut wis ana, mula kita bakal nimpa nilai kasebut lan bali menyang oyod, mbatalake owah-owahan bobot kabeh kelenjar sing wis dilewati.
Yen simpul lagi dibusak, banjur kita mudhun lan ngurangi bobot saka kelenjar liwati.

Indeks

Saiki ayo pindhah menyang carane ngindeks node. Node ora nyimpen indeks kanthi jelas, diwilang adhedhasar bobot simpul. Yen padha nyimpen indeks, banjur bakal dibutuhake O (n) wektu kanggo nganyari indeks kabeh kelenjar sawise saben owah-owahan ing wit.
Ayo pindhah menyang representasi visual. Wit kita kosong, ayo tambahake simpul 1:

Node pisanan duwe indeks 0, lan saiki 2 kasus bisa uga. Ing pisanan, indeks saka unsur ROOT bakal diganti, ing kaloro ora bakal ngganti.

Ing oyod, subtree kiwa bobote 1.

Kasus kapindho:

Indeks oyod ora owah amarga bobot subtree kiwa tetep 0.

Indeks simpul diitung minangka bobot subtree kiwa + nomer sing dilewati saka wong tuwa. Apa nomer iki?, Iki counter indeks, wiwitane padha karo 0, amarga oyod ora ana wong tuwa. Banjur kabeh gumantung ing ngendi kita mudhun menyang anak kiwa utawa tengen. Yen ing sisih kiwa, banjur ora ana sing ditambahake ing counter. Yen kita nambah indeks simpul saiki ing sisih tengen.

Contone, carane indeks saka unsur karo tombol 8 (anak tengen ROOT) wis diwilang. Iki minangka "Indeks Root" + "bobot subtree kiwa saka simpul kanthi kunci 8" + "1" == 3 + 2 + 1 == 6
Indeks saka unsur karo tombol 6 bakal "Indeks ROOT" + 1 == 3 + 1 == 4

Mulane, butuh wektu kanggo njaluk lan mbusak unsur kanthi indeks O (mlebu n), amarga kanggo entuk unsur sing dikarepake kudu ditemokake dhisik (mudhun saka oyod menyang unsur iki).

Ambane

Adhedhasar bobot, sampeyan uga bisa ngetung ambane wit. Perlu kanggo imbangan.
Kanggo nindakake iki, bobot simpul saiki kudu dibunderaké menyang nomer pisanan kanggo daya 2 kang luwih saka utawa padha karo bobot diwenehi lan njupuk logaritma binar saka iku. Iki bakal menehi kita ambane wit, assuming iku imbang. Wit kasebut imbang sawise nglebokake unsur anyar. Aku ora bakal menehi teori babagan carane ngimbangi wit. Kode sumber nyedhiyakake fungsi imbangan.

Kode kanggo ngowahi bobot menyang ambane.

/*
 * Возвращает первое число в степени 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 dumadi ing O (mlebu n)
mbusak unsur kanthi nomer seri dumadi ing O (mlebu n)
entuk unsur kanthi nomer seri dumadi ing O (mlebu n)

Kacepetan O (mlebu n) We mbayar kanggo kasunyatan sing kabeh data disimpen ing wangun diurutake.

Aku ora ngerti ngendi struktur kuwi bisa migunani. Mung teka-teki sepisan maneh ngerti carane wit bisa. Matur nuwun kawigatosanipun.

referensi

Kode sumber wit

Proyek kasebut ngemot data tes kanggo mriksa kacepetan operasi. Wit iku ngisi 1000000 unsur. Lan ana pambusakan, penyisipan lan pengangkatan unsur 1000000 sapisan. Iku 3000000 operasi. Hasile ternyata cukup apik ~ 8 detik.

Source: www.habr.com

Wit binar sing diindeks

Bobot

Indeks

Ambane

Hasil

referensi

Add a comment Отменить ответ