Saya terjumpa jenis masalah berikut. Adalah perlu untuk melaksanakan bekas storan data yang menyediakan fungsi berikut:
- masukkan elemen baharu
- alih keluar elemen mengikut nombor siri
- dapatkan elemen dengan nombor ordinal
- data disimpan dalam bentuk disusun
Data sentiasa ditambah dan dialih keluar, struktur mesti memastikan kelajuan operasi yang pantas. Pada mulanya saya cuba melaksanakan perkara sedemikian menggunakan bekas standard dari std. Jalan ini tidak dinobatkan dengan kejayaan dan datang kefahaman bahawa saya perlu melaksanakan sesuatu sendiri. Satu-satunya perkara yang terlintas di fikiran ialah menggunakan pepohon carian binari. Kerana ia memenuhi keperluan penyisipan cepat, pemadaman dan penyimpanan data dalam bentuk disusun. Apa yang tinggal ialah memikirkan cara mengindeks semua elemen dan mengira semula indeks apabila pokok berubah.
struct node_s {
data_t data;
uint64_t weight; // Π²Π΅Ρ ΡΠ·Π»Π°
node_t *left;
node_t *right;
node_t *parent;
};Artikel akan mengandungi lebih banyak gambar dan teori daripada kod. Kod boleh dilihat di pautan di bawah.
Berat
Untuk mencapai matlamat ini, pokok itu mengalami sedikit pengubahsuaian, maklumat tambahan telah ditambahkan tentang berat badan nod. Berat nod ialah bilangan keturunan nod ini + 1 (berat unsur tunggal).
Fungsi untuk mendapatkan berat nod:
uint64_t bntree::get_child_weight(node_t *node) {
if (node) {
return node->weight;
}
return 0;
}Berat helaian adalah sama dengan 0.
Seterusnya, mari kita beralih kepada perwakilan visual contoh pokok sedemikian. Hitam kunci nod akan ditunjukkan dalam warna (nilai tidak akan ditunjukkan, kerana ini tidak perlu), merah - berat simpulan, hijau β indeks nod.
Apabila pokok kita kosong, beratnya ialah 0. Mari tambahkan elemen akar padanya:
Berat pokok menjadi 1, berat unsur akar menjadi 1. Berat unsur akar ialah berat pokok.
Mari tambah beberapa lagi elemen:
Setiap kali elemen baharu ditambah, kami turun ke nod dan menambah pembilang berat setiap nod yang dilalui. Apabila nod baharu dicipta, pemberat diberikan kepadanya 1. Jika nod dengan kunci sedemikian sudah wujud, maka kami akan menulis ganti nilai dan kembali ke akar, membatalkan perubahan dalam pemberat semua nod yang telah kami lalui.
Jika nod sedang dialih keluar, maka kami turun dan mengurangkan berat nod yang diluluskan.
Indeks
Sekarang mari kita beralih kepada cara mengindeks nod. Nod tidak menyimpan indeksnya secara eksplisit, ia dikira berdasarkan berat nod. Jika mereka menyimpan indeks mereka, maka ia akan diperlukan O (n) masa untuk mengemas kini indeks semua nod selepas setiap perubahan dalam pepohon.
Mari kita beralih kepada perwakilan visual. Pokok kami kosong, mari tambahkan nod pertama padanya:
Nod pertama mempunyai indeks 0, dan kini 2 kes mungkin. Pada yang pertama, indeks unsur akar akan berubah, pada yang kedua ia tidak akan berubah.
Pada akarnya, subpokok kiri mempunyai berat 1.
Kes kedua:
Indeks akar tidak berubah kerana berat subpokok kirinya kekal 0.
Indeks nod dikira sebagai berat subpokok kiri + nombor yang diluluskan daripada induk. Apakah nombor ini?, Ini adalah kaunter indeks, pada mulanya ia sama dengan 0, kerana akar tidak mempunyai induk. Kemudian semuanya bergantung kepada mana kita turun ke anak kiri atau kanan. Jika ke kiri, maka tiada apa yang ditambahkan ke kaunter. Jika kita menambah indeks nod semasa ke kanan.
Sebagai contoh, bagaimana indeks unsur dengan kunci 8 (anak kanan akar) dikira. Ini ialah "Indeks Akar" + "berat subpokok kiri nod dengan kunci 8" + "1" == 3 + 2 + 1 == 6
Indeks elemen dengan kunci 6 akan menjadi "Indeks Root" + 1 == 3 + 1 == 4
Sehubungan itu, ia mengambil masa untuk mendapatkan dan memadam elemen mengikut indeks O (log n), kerana untuk mendapatkan elemen yang dikehendaki kita mesti mencarinya dahulu (turun dari akar ke elemen ini).
Kedalaman
Berdasarkan berat, anda juga boleh mengira kedalaman pokok. Perlu untuk mengimbangi.
Untuk melakukan ini, berat nod semasa mesti dibundarkan kepada nombor pertama kepada kuasa 2 yang lebih besar daripada atau sama dengan berat yang diberikan dan mengambil logaritma binari daripadanya. Ini akan memberi kita kedalaman pokok, dengan mengandaikan ia seimbang. Pokok itu seimbang selepas memasukkan elemen baru. Saya tidak akan memberikan teori tentang cara mengimbangi pokok. Kod sumber menyediakan fungsi pengimbangan.
Kod untuk menukar berat kepada kedalaman.
/*
* ΠΠΎΠ·Π²ΡΠ°ΡΠ°Π΅Ρ ΠΏΠ΅ΡΠ²ΠΎΠ΅ ΡΠΈΡΠ»ΠΎ Π² ΡΡΠ΅ΠΏΠ΅Π½ΠΈ 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));
}Keputusan
- penyisipan unsur baru berlaku dalam O (log n)
- memadam elemen dengan nombor siri berlaku dalam O (log n)
- mendapatkan elemen dengan nombor siri berlaku dalam O (log n)
Kelajuan O (log n) Kami membayar untuk fakta bahawa semua data disimpan dalam bentuk yang diisih.
Saya tidak tahu di mana struktur sedemikian mungkin berguna. Hanya teka-teki untuk sekali lagi memahami cara pokok berfungsi. Terima kasih kerana memberi perhatian.
rujukan
Projek ini mengandungi data ujian untuk menyemak kelajuan operasi. Pokok itu penuh 1000000 elemen. Dan terdapat pemadaman berurutan, penyisipan dan pengambilan semula elemen 1000000 sekali. Itu dia 3000000 operasi. Hasilnya ternyata agak baik ~ 8 saat.
Sumber: www.habr.com