Индекстелген бинардык дарак

Мен көйгөйдүн төмөнкү түрүнө туш болдум. Төмөнкү функцияларды камсыз кылган маалыматтарды сактоочу контейнерди ишке ашыруу зарыл:

• жаңы элементти киргизүү
• сериялык номери боюнча элементти алып салуу
• элементти иреттик сан боюнча алуу
• маалыматтар сорттолгон түрдө сакталат

Маалыматтар тынымсыз кошулуп жана алынып турат, структура тез иштөө ылдамдыгын камсыз кылышы керек. Башында мен стандарттуу контейнерлерди колдонуп, мындай нерсени ишке ашырууга аракет кылдым саат. Бул жол ийгиликтүү болгон жок жана мен өзүм бир нерсени ишке ашыруу керек экенин түшүндүм. Бир гана нерсе экилик издөө дарагын колдонуу эле. Анткени ал иргелген түрдө маалыматтарды тез киргизүү, жок кылуу жана сактоо талабына жооп берет. Бардык элементтерди индекстөө жана дарак өзгөргөндө индекстерди кайра эсептөөнү аныктоо гана калды.

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 (log 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 (log n)
• сериялык номери боюнча элементти жок кылуу O (log n)
• сериялык номери боюнча элементти алуу жылы болот O (log n)

Ылдамдык O (log n) Биз бардык маалыматтар иреттелген түрдө сакталганы үчүн төлөйбүз.

Мындай структура пайдалуу болушу мүмкүн экенин билбейм. Жөн гана баш катырма дарактардын кантип иштээрин дагы бир жолу түшүнүү. Конул бурганын учун рахмат.

шилтемелер

• Дарак булак коду

Долбоор иштөө ылдамдыгын текшерүү үчүн тесттик маалыматтарды камтыйт. Дарак толуп жатат 1000000 элементтер. Жана элементтерди ырааттуу өчүрүү, киргизүү жана алуу бар 1000000 бир жолу. Башкача айтканда 3000000 операциялар. Натыйжа абдан жакшы болду ~ 8 секунд.

Source: www.habr.com