Men quyidagi turdagi muammoga duch keldim. Quyidagi funksiyalarni ta'minlaydigan ma'lumotlarni saqlash konteynerini joriy qilish kerak:
- yangi elementni kiriting
- elementni seriya raqami bo'yicha olib tashlang
- tartib raqami bo'yicha elementni oling
- ma'lumotlar tartiblangan shaklda saqlanadi
Ma'lumotlar doimiy ravishda qo'shiladi va o'chiriladi, struktura tez ishlash tezligini ta'minlashi kerak. Avvaliga men standart konteynerlardan foydalangan holda bunday narsani amalga oshirishga harakat qildim std. Bu yo'l muvaffaqiyatga erishmadi va men o'zim nimanidir amalga oshirishim kerakligini angladim. Aqlga kelgan yagona narsa ikkilik qidiruv daraxtidan foydalanish edi. Chunki u ma'lumotlarni saralangan holda tez kiritish, o'chirish va saqlash talablariga javob beradi. Qolgan narsa - daraxt o'zgarganda barcha elementlarni qanday indekslashni aniqlash va indekslarni qayta hisoblash.
struct node_s {
data_t data;
uint64_t weight; // вес узла
node_t *left;
node_t *right;
node_t *parent;
};Maqolada koddan ko'ra ko'proq rasm va nazariya mavjud. Kodni quyidagi havolada ko'rish mumkin.
Og'irligi
Bunga erishish uchun daraxt biroz o'zgartirildi, qo'shimcha ma'lumotlar qo'shildi vazn tugun. Tugunning og'irligi bu tugunning avlodlari soni + 1 (bitta elementning og'irligi).
Tugun og'irligini olish funktsiyasi:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}Varaqning og'irligi mos ravishda teng 0.
Keyin, keling, bunday daraxtning misolini vizual tasvirlashga o'taylik. Qora tugun kaliti rangda ko'rsatiladi (qiymat ko'rsatilmaydi, chunki bu shart emas), qizil rangda - tugun og'irligi, yashil rangda - tugun indeksi.
Daraxtimiz bo'sh bo'lsa, uning og'irligi 0 ga teng. Keling, unga ildiz elementini qo'shamiz:
Daraxtning og'irligi 1 ga, ildiz elementining og'irligi 1 ga aylanadi. Ildiz elementining vazni daraxtning og'irligi.
Keling, yana bir nechta elementlarni qo'shamiz:
Har safar yangi element qo'shilganda, biz tugunlardan pastga tushamiz va o'tgan har bir tugunning vazn hisoblagichini oshiramiz. Yangi tugun yaratilganda, unga og'irlik beriladi 1. Agar bunday kalitga ega tugun allaqachon mavjud bo'lsa, biz qiymatni qayta yozamiz va biz o'tgan barcha tugunlarning og'irliklaridagi o'zgarishlarni bekor qilib, ildizga qaytamiz.
Agar tugun olib tashlansa, biz pastga tushamiz va o'tgan tugunlarning og'irligini kamaytiramiz.
Ko'rsatkichlar
Endi tugunlarni indekslash usuliga o'tamiz. Tugunlar o'zlarining indekslarini aniq saqlamaydilar, u tugunlarning og'irligiga qarab hisoblanadi. Agar ular indekslarini saqlagan bo'lsa, unda bu talab qilinadi O (n) daraxtdagi har bir o'zgarishdan keyin barcha tugunlarning indekslarini yangilash vaqti.
Keling, vizual tasvirga o'tamiz. Bizning daraxtimiz bo'sh, keling, unga 1-tugunni qo'shamiz:
Birinchi tugun indeksga ega 0, va endi 2 ta holat mumkin. Birinchisida, ildiz elementining indeksi o'zgaradi, ikkinchisida u o'zgarmaydi.
Ildizda chap pastki daraxtning og'irligi 1 ga teng.
Ikkinchi holat:
Ildiz indeksi o'zgarmadi, chunki uning chap pastki daraxtining og'irligi 0 bo'lib qoldi.
Tugun indeksi uning chap pastki daraxtining og'irligi + ota-onadan o'tgan raqam sifatida hisoblanadi. Bu raqam nima?, Bu indeks hisoblagichi, dastlab u teng 0, chunki ildizning ota-onasi yo'q. Keyin hamma narsa chap bolaga yoki o'ngga qaerga tushishimizga bog'liq. Agar chap tomonda bo'lsa, u holda hisoblagichga hech narsa qo'shilmaydi. Agar joriy tugun indeksini o'ngga qo'shsak.
Masalan, 8-kalitli element indeksi (ildizning o'ng bolasi) qanday hisoblanadi. Bu "Ildiz indeksi" + "8-kalitli tugunning chap pastki daraxtining og'irligi" + "1" == 3 + 2 + 1 == 6
6-kalitli element indeksi "Ildiz indeksi" + 1 == 3 + 1 == bo'ladi. 4
Shunga ko'ra, elementni indeks bo'yicha olish va o'chirish uchun vaqt kerak bo'ladi O (log n), chunki kerakli elementni olish uchun birinchi navbatda uni topishimiz kerak (ildizdan bu elementga tushish).
Chuqurlik
Og'irligi asosida siz daraxtning chuqurligini ham hisoblashingiz mumkin. Balanslash uchun zarur.
Buning uchun joriy tugunning og'irligi berilgan og'irlikdan katta yoki unga teng bo'lgan 2 ning kuchiga birinchi raqamga yaxlitlash va undan ikkilik logarifmni olish kerak. Bu bizga daraxtning chuqurligini beradi, agar u muvozanatli bo'lsa. Daraxt yangi elementni kiritgandan so'ng muvozanatlanadi. Men daraxtlarni qanday muvozanatlash haqida nazariya bermayman. Manba kodlari muvozanat funktsiyasini ta'minlaydi.
Og'irlikni chuqurlikka aylantirish uchun kod.
/*
* Возвращает первое число в степени 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));
}natijalar
- yangi elementning kiritilishi sodir bo'ladi O (log n)
- elementni seriya raqami bo'yicha o'chirish da sodir bo'ladi O (log n)
- elementni seriya raqami bo'yicha olish yilda sodir bo'ladi O (log n)
Tezlik O (log n) Biz barcha ma'lumotlar tartiblangan shaklda saqlanganligi uchun to'laymiz.
Bunday tuzilma qayerda foydali bo'lishi mumkinligini bilmayman. Daraxtlar qanday ishlashini yana bir bor tushunish uchun faqat jumboq. E'tiboringiz uchun rahmat.
Manbalar
Loyihada ishlash tezligini tekshirish uchun test ma'lumotlari mavjud. Daraxt to'ldiriladi 1000000 elementlar. Va elementlarni ketma-ket o'chirish, kiritish va olish mavjud 1000000 bir marta. Ya'ni 3000000 operatsiyalar. Natija juda yaxshi bo'ldi ~ 8 soniya.
Manba: www.habr.com