Индекстелген екілік ағаш

Мен келесі типтегі мәселеге тап болдым. Келесі функцияларды қамтамасыз ететін деректерді сақтау контейнерін енгізу қажет:

• жаңа элементті енгізу
• сериялық нөмір бойынша элементті алып тастаңыз
• элементті реттік санмен алу
• деректер сұрыпталған түрде сақталады

Деректер үнемі қосылады және жойылады, құрылым жұмыстың жылдам жылдамдығын қамтамасыз етуі керек. Алдымен мен стандартты контейнерлерді пайдаланып осындай нәрсені жүзеге асыруға тырыстым std. Бұл жол сәтті болмады және маған бір нәрсені өзім жүзеге асыру керек екенін түсіндім. Ойға келген жалғыз нәрсе - екілік іздеу ағашын пайдалану. Өйткені ол сұрыпталған түрде деректерді жылдам енгізу, жою және сақтау талаптарына жауап береді. Барлық элементтерді қалай индекстеу керектігін анықтау және ағаш өзгерген кезде индекстерді қайта есептеу ғана қалады.

struct node_s {    
    data_t data;

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

    node_t *left;
    node_t *right;

    node_t *parent;
};

Мақалада кодқа қарағанда көбірек суреттер мен теория болады. Кодты төмендегі сілтемеден көруге болады.

салмақ

Бұған қол жеткізу үшін ағаш аздап модификациядан өтті, қосымша ақпарат қосылды салмақ түйін. Түйіннің салмағы осы түйіннің ұрпақтарының саны + 1 (бір элементтің салмағы).

Түйіннің салмағын алу функциясы:

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

    return 0;
}

Парақтың салмағы сәйкесінше тең 0.

Әрі қарай, осындай ағаштың мысалының көрнекі көрінісіне көшейік. Қара түйін кілті түсті түрде көрсетіледі (мән көрсетілмейді, себебі бұл қажет емес), қызыл - түйін салмағы, жасыл — түйін индексі.

Ағашымыз бос болған кезде оның салмағы 0 болады. Оған түбір элементін қосайық:

Ағаштың салмағы 1-ге, тамыр элементінің салмағы 1-ге айналады. Түбір элементінің салмағы - ағаштың салмағы.

Тағы бірнеше элементтерді қосамыз:

Жаңа элемент қосылған сайын біз түйіндерді төмен түсіреміз және әрбір өткен түйіннің салмақ санауышын көбейтеміз. Жаңа түйін жасалғанда, оған салмақ тағайындалады 1. Егер мұндай кілті бар түйін бұрыннан бар болса, онда біз өткен барлық түйіндердің салмақтарындағы өзгерістерді болдырмай, мәнді қайта жазып, түбірге қайта ораламыз.
Егер түйін жойылса, біз төмен түсіп, өткен түйіндердің салмағын азайтамыз.

Көрсеткіштер

Енді түйіндерді индекстеу әдісіне көшейік. Түйіндер өздерінің индексін анық сақтамайды, ол түйіндердің салмағына қарай есептеледі. Егер олар индексін сақтаған болса, онда бұл қажет болады O (N) ағаштағы әрбір өзгерістен кейін барлық түйіндердің индекстерін жаңарту уақыты.
Көрнекі көрініске көшейік. Біздің ағаш бос, оған 1-ші түйінді қосайық:

Бірінші түйінде индекс бар 0, ал қазір 2 жағдай мүмкін. Біріншісінде түбір элементінің индексі өзгереді, екіншісінде ол өзгермейді.

Түбірде сол жақ ішкі ағаштың салмағы 1.

Екінші жағдай:

Түбірдің индексі өзгермеді, себебі оның сол жақ ішкі ағашының салмағы 0 болып қалды.

Түйіннің индексі оның сол жақ ішкі ағашының салмағы + ата-анадан өткен сан ретінде есептеледі. Бұл қандай сан?, Бұл индекс санауышы, бастапқыда ол тең 0, өйткені түбірдің ата-анасы жоқ. Содан кейін бәрі сол балаға немесе оң жаққа қайда түсетінімізге байланысты. Егер сол жақта болса, онда есептегішке ештеңе қосылмайды. Оң жаққа ағымдағы түйіннің индексін қоссақ.

Мысалы, 8 пернесі бар элементтің индексі (түбірдің оң жақ еншілес бөлігі) қалай есептеледі. Бұл "Түбір индексі" + "8 пернесі бар түйіннің сол жақ ішкі ағашының салмағы" + "1" == 3 + 2 + 1 == 6
6 кілті бар элементтің индексі "Түбірлік индекс" + 1 == 3 + 1 == болады. 4

Тиісінше, индекс бойынша элементті алу және жою үшін уақыт қажет O (журнал n), өйткені қажетті элементті алу үшін алдымен оны табу керек (түбірден осы элементке дейін төмен түсу).

Тереңдігі

Салмағы негізінде ағаштың тереңдігін де есептеуге болады. Теңдестіру үшін қажет.
Ол үшін ағымдағы түйіннің салмағы берілген салмақтан үлкен немесе оған тең 2 дәрежесіне дейінгі бірінші санға дейін дөңгелектеніп, одан екілік логарифмді алу керек. Бұл теңдестірілген деп есептесек, ағаштың тереңдігін береді. Ағаш жаңа элементті енгізгеннен кейін теңдестірілген. Мен ағаштарды қалай теңестіру керектігі туралы теория бермеймін. Бастапқы кодтар теңгерім функциясын қамтамасыз етеді.

Салмақты тереңдікке түрлендіруге арналған код.

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

Нәтижелері

• ішінде жаңа элементті енгізу орын алады O (журнал n)
• сериялық нөмір бойынша элементті жою ішінде орын алады O (журнал n)
• реттік нөмірі бойынша элементті алу орын алады O (журнал n)

Жылдамдық O (журнал n) Біз барлық деректер сұрыпталған түрде сақталғаны үшін төлейміз.

Мен мұндай құрылымның қай жерде пайдалы болуы мүмкін екенін білмеймін. Ағаштардың қалай жұмыс істейтінін тағы бір рет түсіну үшін жай ғана басқатырғыш. Назарларыңызға рахмет.

сілтемелер

• Ағаштың бастапқы коды

Жобада жұмыс жылдамдығын тексеруге арналған сынақ деректері бар. Ағаш толып жатыр 1000000 элементтері. Және элементтерді дәйекті жою, кірістіру және алу бар 1000000 бір рет. Яғни 3000000 операциялар. Нәтиже өте жақсы болды ~ 8 секунд.

Ақпарат көзі: www.habr.com