ProHoster > Blog > Pangangasiwa > Naka-index na binary tree

Naka-index na binary tree

Naka-index na binary tree

Dumating ako sa sumusunod na uri ng problema. Kinakailangang magpatupad ng lalagyan ng imbakan ng data na nagbibigay ng sumusunod na pagpapagana:

  • magpasok ng bagong elemento
  • alisin ang elemento sa pamamagitan ng serial number
  • kumuha ng elemento sa pamamagitan ng ordinal na numero
  • ang data ay nakaimbak sa pinagsunod-sunod na anyo

Ang data ay patuloy na idinaragdag at inaalis, dapat tiyakin ng istraktura ang mabilis na bilis ng operasyon. Sa una sinubukan kong ipatupad ang ganoong bagay gamit ang mga karaniwang lalagyan mula sa std. Ang landas na ito ay hindi nakoronahan ng tagumpay at dumating ang pag-unawa na kailangan kong ipatupad ang isang bagay sa aking sarili. Ang tanging naisip ay ang paggamit ng binary search tree. Dahil natutugunan nito ang pangangailangan ng mabilis na pagpasok, pagtanggal at pag-iimbak ng data sa pinagsunod-sunod na anyo. Ang natitira lamang ay upang malaman kung paano i-index ang lahat ng mga elemento at muling kalkulahin ang mga indeks kapag nagbago ang puno.

struct node_s {    
    data_t data;

    uint64_t weight; // вСс ΡƒΠ·Π»Π°

    node_t *left;
    node_t *right;

    node_t *parent;
};

Ang artikulo ay maglalaman ng mas maraming larawan at teorya kaysa sa code. Maaaring matingnan ang code sa link sa ibaba.

Timbang

Upang makamit ito, ang puno ay sumailalim sa isang bahagyang pagbabago, ang karagdagang impormasyon ay idinagdag tungkol sa timbang node. Ang bigat ng node ay bilang ng mga inapo ng node na ito + 1 (bigat ng isang elemento).

Function para sa pagkuha ng node weight:

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

    return 0;
}

Ang bigat ng sheet ay katumbas ng katumbas ng 0.

Susunod, lumipat tayo sa isang visual na representasyon ng isang halimbawa ng naturang puno. Itim ang node key ay ipapakita sa kulay (ang halaga ay hindi ipapakita, dahil ito ay hindi kinakailangan), pula - bigat ng buhol, berde - index ng node.

Kapag ang ating puno ay walang laman, ang bigat nito ay 0. Magdagdag tayo ng elementong ugat dito:

Naka-index na binary tree

Ang bigat ng puno ay nagiging 1, ang bigat ng elemento ng ugat ay nagiging 1. Ang bigat ng elemento ng ugat ay ang bigat ng puno.

Magdagdag pa tayo ng ilang elemento:

Naka-index na binary tree
Naka-index na binary tree
Naka-index na binary tree
Naka-index na binary tree

Sa bawat oras na magdaragdag ng bagong elemento, bumababa kami sa mga node at tinataasan ang weight counter ng bawat node na naipasa. Kapag ang isang bagong node ay nilikha, isang timbang ay itinalaga dito 1. Kung mayroon nang node na may ganoong key, i-overwrite namin ang value at babalik sa root, na kanselahin ang mga pagbabago sa mga timbang ng lahat ng node na naipasa namin.
Kung ang isang node ay inaalis, pagkatapos ay bumaba tayo at binabawasan ang mga timbang ng mga naipasa na node.

Mga Index

Ngayon ay lumipat tayo sa kung paano mag-index ng mga node. Ang mga node ay hindi tahasang iniimbak ang kanilang index, ito ay kinakalkula batay sa bigat ng mga node. Kung inimbak nila ang kanilang index, kakailanganin ito O (n) oras na upang i-update ang mga index ng lahat ng mga node pagkatapos ng bawat pagbabago sa puno.
Lumipat tayo sa isang visual na representasyon. Walang laman ang puno natin, idagdag natin ang 1st node dito:

Naka-index na binary tree

Ang unang node ay may index 0, at ngayon 2 kaso ang posible. Sa una, ang index ng elemento ng ugat ay magbabago, sa pangalawa ay hindi ito magbabago.

Naka-index na binary tree

Sa ugat, ang kaliwang subtree ay tumitimbang ng 1.

Pangalawang kaso:

Naka-index na binary tree

Ang index ng ugat ay hindi nagbago dahil ang bigat ng kaliwang subtree nito ay nanatiling 0.

Ang index ng isang node ay kinakalkula bilang ang bigat ng kaliwang subtree nito + ang numerong ipinasa mula sa magulang. Ano ang numerong ito?, Ito ang index counter, sa una ito ay katumbas ng 0, dahil walang magulang ang ugat. Kung gayon ang lahat ay nakasalalay sa kung saan tayo bababa sa kaliwang bata o sa kanan. Kung sa kaliwa, pagkatapos ay walang idinagdag sa counter. Kung idaragdag namin ang index ng kasalukuyang node sa kanan.

Naka-index na binary tree

Halimbawa, kung paano kinakalkula ang index ng isang elemento na may key 8 (ang kanang anak ng ugat). Ito ay "Root Index" + "bigat ng kaliwang subtree ng node na may key 8" + "1" == 3 + 2 + 1 == 6
Ang index ng elementong may key 6 ay magiging "Root Index" + 1 == 3 + 1 == 4

Alinsunod dito, nangangailangan ng oras upang makuha at tanggalin ang isang elemento sa pamamagitan ng index O (mag-log n), dahil para makuha ang ninanais na elemento kailangan muna nating hanapin ito (bumaba mula sa ugat hanggang sa elementong ito).

Lalim

Batay sa bigat, maaari mo ring kalkulahin ang lalim ng puno. Kailangan para sa pagbabalanse.
Upang gawin ito, ang bigat ng kasalukuyang node ay dapat na bilugan sa unang numero sa kapangyarihan ng 2 na mas malaki kaysa o katumbas ng ibinigay na timbang at kunin ang binary logarithm mula dito. Bibigyan tayo nito ng lalim ng puno, sa pag-aakalang ito ay balanse. Ang puno ay balanse pagkatapos magpasok ng isang bagong elemento. Hindi ako magbibigay ng teorya tungkol sa kung paano balansehin ang mga puno. Ang mga source code ay nagbibigay ng function ng pagbabalanse.

Code para sa pag-convert ng timbang sa lalim.

/*
 * Π’ΠΎΠ·Π²Ρ€Π°Ρ‰Π°Π΅Ρ‚ ΠΏΠ΅Ρ€Π²ΠΎΠ΅ число Π² стСпСни 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));
}

Mga resulta ng

  • Ang pagpasok ng isang bagong elemento ay nangyayari sa O (mag-log n)
  • ang pagtanggal ng isang elemento sa pamamagitan ng serial number ay nangyayari sa O (mag-log n)
  • ang pagkuha ng isang elemento sa pamamagitan ng serial number ay nangyayari sa O (mag-log n)

Bilis O (mag-log n) Nagbabayad kami para sa katotohanan na ang lahat ng data ay naka-imbak sa pinagsunod-sunod na anyo.

Hindi ko alam kung saan maaaring maging kapaki-pakinabang ang gayong istraktura. Isang palaisipan lamang upang maunawaan muli kung paano gumagana ang mga puno. Salamat sa iyong atensyon.

sanggunian

Ang proyekto ay naglalaman ng data ng pagsubok upang suriin ang bilis ng operasyon. Ang puno ay napupuno 1000000 mga elemento. At mayroong sunud-sunod na pagtanggal, pagpasok at pagkuha ng mga elemento 1000000 minsan. Yan ay 3000000 mga operasyon. Ang resulta ay naging medyo maganda ~ 8 segundo.

Pinagmulan: www.habr.com

Magdagdag ng komento