Pohon biner yang diindeks

Saya menemukan jenis masalah berikut. Penting untuk mengimplementasikan wadah penyimpanan data yang menyediakan fungsionalitas berikut:

• masukkan elemen baru
• hapus elemen dengan nomor seri
• dapatkan elemen dengan nomor urut
• data disimpan dalam bentuk terurut

Data terus-menerus ditambahkan dan dihapus, struktur harus memastikan kecepatan operasi yang cepat. Pada awalnya saya mencoba menerapkan hal seperti itu menggunakan wadah standar dari std. Jalan ini tidak dimahkotai dengan kesuksesan dan muncul pemahaman bahwa saya sendiri perlu menerapkan sesuatu. Satu-satunya hal yang terlintas dalam pikiran adalah menggunakan pohon pencarian biner. Karena memenuhi persyaratan penyisipan, penghapusan, dan penyimpanan data yang cepat dalam bentuk terurut. Yang tersisa hanyalah mencari cara untuk mengindeks semua elemen dan menghitung ulang indeks ketika pohon berubah.

struct node_s {    
    data_t data;

    uint64_t weight; // вес узла

    node_t *left;
    node_t *right;

    node_t *parent;
};

Artikel ini akan berisi lebih banyak gambar dan teori daripada kode. Kodenya dapat dilihat pada link dibawah ini.

Berat

Untuk mencapai hal ini, pohon mengalami sedikit modifikasi, informasi tambahan ditambahkan berat simpul. Berat simpulnya adalah jumlah keturunan dari node ini + 1 (berat satu elemen).

Fungsi untuk mendapatkan bobot node:

uint64_t bntree::get_child_weight(node_t *node) {
    if (node) {
        return node->weight;
    }

    return 0;
}

Berat lembaran juga sama 0.

Selanjutnya, mari kita beralih ke representasi visual dari contoh pohon tersebut. Hitam kunci simpul akan ditampilkan dalam warna (nilainya tidak akan ditampilkan, karena ini tidak perlu), merah — berat simpul, hijau — indeks simpul.

Saat pohon kita kosong, bobotnya adalah 0. Mari tambahkan elemen akar ke dalamnya:

Bobot pohon menjadi 1, bobot elemen akar menjadi 1. Bobot elemen akar adalah bobot pohon.

Mari tambahkan beberapa elemen lagi:

Setiap kali elemen baru ditambahkan, kami menurunkan node dan menambah penghitung bobot setiap node yang dilewati. Ketika node baru dibuat, maka node tersebut diberi bobot 1. Jika node dengan kunci seperti itu sudah ada, maka kita akan menimpa nilainya dan kembali ke root, membatalkan perubahan bobot semua node yang telah kita lewati.
Jika sebuah node sedang dihapus, maka kita turun dan mengurangi bobot dari node yang dilewati.

Indeks

Sekarang mari beralih ke cara mengindeks node. Node tidak menyimpan indeksnya secara eksplisit, ini dihitung berdasarkan bobot node. Jika mereka menyimpan indeksnya, maka itu diperlukan O (n) waktu untuk memperbarui indeks semua node setelah setiap perubahan pada pohon.
Mari beralih ke representasi visual. Pohon kita kosong, mari tambahkan node pertama ke dalamnya:

Node pertama memiliki indeks 0, dan sekarang 2 kasus mungkin terjadi. Yang pertama, indeks elemen root akan berubah, yang kedua tidak akan berubah.

Di akar, subpohon kiri berbobot 1.

Kasus kedua:

Indeks akar tidak berubah karena bobot subpohon kirinya tetap 0.

Indeks suatu simpul dihitung sebagai bobot subpohon kirinya + angka yang diteruskan dari induknya. Angka berapa ini?, Ini penghitung indeksnya, awalnya sama dengan 0, Karena akarnya tidak mempunyai induk. Lalu semua tergantung kita turun ke anak kiri atau ke kanan. Jika ke kiri, maka tidak ada yang ditambahkan ke penghitung. Jika kita menambahkan indeks node saat ini ke node kanan.

Misalnya, bagaimana indeks suatu elemen dengan kunci 8 (anak kanan dari root) dihitung. Ini adalah "Indeks Akar" + "bobot subpohon kiri dari simpul dengan kunci 8" + "1" == 3 + 2 + 1 == 6
Indeks elemen dengan kunci 6 akan menjadi "Indeks Akar" + 1 == 3 + 1 == 4

Oleh karena itu, diperlukan waktu untuk mendapatkan dan menghapus elemen berdasarkan indeks O (log n), karena untuk mendapatkan elemen yang diinginkan kita harus menemukannya terlebih dahulu (turun dari akar ke elemen ini).

Kedalaman

Berdasarkan beratnya, Anda juga bisa menghitung kedalaman pohon. Diperlukan untuk menyeimbangkan.
Untuk melakukan ini, bobot node saat ini harus dibulatkan ke angka pertama pangkat 2 yang lebih besar atau sama dengan bobot yang diberikan dan ambil logaritma biner darinya. Ini akan memberi kita kedalaman pohon, dengan asumsi pohon itu seimbang. Pohonnya seimbang setelah memasukkan elemen baru. Saya tidak akan memberikan teori tentang bagaimana menyeimbangkan pohon. Kode sumber menyediakan fungsi penyeimbang.

Kode untuk mengubah berat menjadi 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));
}

Hasil

• penyisipan elemen baru terjadi di O (log n)
• penghapusan elemen berdasarkan nomor seri terjadi di O (log n)
• memperoleh elemen dengan nomor seri terjadi di O (log n)

kecepatan O (log n) Kami membayar fakta bahwa semua data disimpan dalam bentuk yang diurutkan.

Saya tidak tahu di mana struktur seperti itu berguna. Hanya sebuah teka-teki untuk sekali lagi memahami cara kerja pohon. Terima kasih atas perhatian Anda.

referensi

• Kode sumber pohon

Proyek ini berisi data pengujian untuk memeriksa kecepatan operasi. Pohon itu mulai terisi 1000000 elemen. Dan ada penghapusan, penyisipan, dan pengambilan elemen secara berurutan 1000000 sekali. Itu adalah 3000000 operasi. Hasilnya ternyata cukup bagus ~ 8 detik.

Sumber: www.habr.com