Saya mendapat masalah berikut. Hal ini diperlukan untuk mengimplementasikan wadah penyimpanan data yang menyediakan fungsionalitas berikut:
- masukkan item baru
- hapus item dengan nomor seri
- dapatkan item dengan nomor seri
- data disimpan dalam bentuk yang diurutkan
Data terus ditambahkan dan dihapus, struktur harus memberikan kecepatan cepat. Awalnya saya mencoba menerapkan hal seperti itu menggunakan kontainer standar dari std . Jalan ini tidak berhasil dan pemahaman datang bahwa Anda perlu mengimplementasikan sesuatu sendiri. Satu-satunya hal yang terlintas dalam pikiran adalah menggunakan pohon pencarian biner. Karena memenuhi persyaratan penyisipan cepat, penghapusan, dan penyimpanan data dalam bentuk diurutkan. Tinggal mencari tahu bagaimana mengindeks semua elemen dan menghitung ulang indeks ketika pohon berubah.
struct node_s { data_t data; uint64_t weight;
Artikel akan memiliki lebih banyak gambar dan teori daripada kode. Kode dapat dilihat di tautan di bawah ini.
Berat
Untuk ini, pohon mengalami sedikit modifikasi, informasi tambahan tentang berat node ditambahkan. Berat suatu simpul adalah jumlah keturunan dari simpul ini + 1 (berat elemen tunggal).
Berfungsi untuk mendapatkan bobot node
uint64_t bntree::get_child_weight(node_t *node) { if (node) { return node->weight; } return 0; }
Lembar, masing-masing, memiliki bobot 0 .
Selanjutnya, kita beralih ke representasi visual dari contoh pohon seperti itu. Kunci simpul akan ditampilkan dalam warna hitam di dalamnya (nilainya tidak akan ditampilkan, karena ini tidak perlu), merah - berat node, hijau - indeks dari node.
Ketika pohon itu kosong, maka beratnya adalah 0. Tambahkan elemen root ke sana:
Berat pohon menjadi 1, berat elemen akar 1. Berat elemen akar adalah berat pohon.
Tambahkan beberapa elemen lagi:
Setiap kali item baru ditambahkan, kita turun node ke bawah dan meningkatkan penghitung berat setiap node yang dilewati. Saat membuat simpul baru, ini diatur ke bobot 1 . Jika sebuah simpul dengan kunci semacam itu sudah ada, maka tulis ulang nilainya dan kembali ke root, batalkan perubahan bobot semua simpul yang kami lewati.
Jika node sedang dihapus, maka kita turun dan mengurangi bobot dari node yang lewat.
Indeks
Sekarang mari kita beralih ke cara mengindeks node. Node tidak secara eksplisit menyimpan indeks mereka, itu dihitung berdasarkan berat node. Jika mereka menyimpan indeks mereka, maka O (n) waktu akan diperlukan untuk memperbarui indeks semua node setelah setiap perubahan pohon.
Mari kita beralih ke representasi visual. Pohon kami kosong, tambahkan simpul 1 ke sana:
Node pertama memiliki indeks 0 , dan sekarang 2 kasus dimungkinkan. Dalam yang pertama, indeks elemen root akan berubah, yang kedua, itu tidak akan berubah.
Pada root, subtree kiri beratnya 1.
Kasus kedua:
Indeks root tidak berubah karena berat subtree kirinya tetap 0.
Karena indeks simpul dipertimbangkan, ini adalah bobot subtree kirinya + angka yang dilewati dari induknya. Berapa nomor ini?, Ini adalah penghitung indeks, awalnya 0 , karena root tidak memiliki orangtua. Maka itu semua tergantung di mana kita turun ke anak kiri atau ke kanan. Jika ke kiri, maka tidak ada yang ditambahkan ke konter. Jika ke kanan lalu tambahkan indeks node saat ini.
Misalnya, cara menghitung indeks elemen dengan kunci 8 (anak kanan dari root). Ini adalah "Root Index" + "bobot subtree kiri dari simpul dengan kunci 8" + "1" == 3 + 2 + 1 == 6
Indeks item dengan kunci 6 adalah "Root Index" + 1 == 3 + 1 == 4
Oleh karena itu, akan butuh O (log n) waktu untuk mendapatkan dan menghapus elemen dengan indeks, karena untuk mendapatkan elemen kita harus terlebih dahulu menemukannya (turun dari root ke elemen ini).
Kedalaman
Berdasarkan beratnya, Anda juga dapat menghitung kedalaman pohon. Diperlukan untuk keseimbangan.
Untuk melakukan ini, berat node saat ini harus dibulatkan ke angka pertama dalam derajat 2 yang lebih besar dari atau sama dengan berat yang diberikan dan mengambil logaritma biner darinya. Jadi, kita mendapatkan kedalaman pohon, asalkan seimbang. Pohon seimbang setelah memasukkan elemen baru. Teori tentang bagaimana menyeimbangkan pohon tidak akan mengarah. Kode sumber menyediakan fungsi penyeimbangan.
Kode untuk membawa bobot ke kedalaman.
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)); }
Ringkasan
- penyisipan elemen baru terjadi di O (log n)
- penghapusan elemen dengan nomor urut terjadi dalam O (log n)
- mendapatkan elemen dengan nomor seri terjadi di O (log n)
Dengan kecepatan O (log n) kami membayar fakta bahwa semua data disimpan dalam bentuk yang diurutkan.
Di mana struktur seperti itu bisa berguna, saya tidak tahu. Hanya tugas untuk sekali lagi memahami cara kerja pohon. Terima kasih atas perhatian anda
Referensi
Proyek ini berisi data uji untuk memverifikasi kecepatan kerja. Pohon itu diisi dengan 1.000.000 elemen. Dan ada penghapusan berurutan, penyisipan dan penerimaan elemen 1.000.000 kali. Itu adalah 3.000.000 operasi. Hasilnya cukup bagus ~ 8 detik.