Индексжүүлсэн хоёртын мод

Би дараах төрлийн асуудалтай тулгарсан. Дараах функцуудыг хангасан өгөгдөл хадгалах савыг хэрэгжүүлэх шаардлагатай.

• шинэ элемент оруулах
• элементийг серийн дугаараар устгах
• элементийг дарааллын дугаараар авна
• өгөгдлийг эрэмбэлсэн хэлбэрээр хадгалдаг

Өгөгдлийг байнга нэмж, устгаж байгаа тул бүтэц нь хурдан ажиллах хурдыг хангах ёстой. Эхлээд би стандарт савыг ашиглан ийм зүйлийг хэрэгжүүлэх гэж оролдсон цаг. Энэ зам амжилтанд хүрч чадаагүй бөгөөд би өөрөө ямар нэг зүйлийг хэрэгжүүлэх хэрэгтэй гэсэн ойлголттой болсон. Хоёртын хайлтын модыг ашиглах л санаанд орж ирсэн. Учир нь энэ нь өгөгдлийг эрэмбэлэгдсэн хэлбэрээр хурдан оруулах, устгах, хадгалах шаардлагыг хангадаг. Бүх элементүүдийг хэрхэн индексжүүлж, мод өөрчлөгдөх үед индексийг дахин тооцоолоход л үлддэг.

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-р түлхүүр бүхий элементийн индекс нь "Root Index" + 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