Saya memimpikan struktur data, apakah itu ada?

Saya belum berhasil menemukan struktur data ini, tetapi saya bukan ahli di bidang ini.

Struktur mengimplementasikan himpunan, dan pada dasarnya adalah array elemen yang sebanding dengan invarian. Yang invarian adalah sebagai berikut (didefinisikan secara rekursif):

Array dengan panjang 1 adalah gabungan-array.

Array dengan panjang 2 ^ n (untuk n> 0) adalah array-iff gabungan:

• bagian pertama adalah gabungan-array dan bagian kedua kosong atau
• array pertama penuh dan diurutkan, dan bagian kedua adalah gabungan-array.

Perhatikan bahwa jika array penuh, itu diurutkan.

Untuk menyisipkan elemen, kami memiliki dua kasus:

• Jika paruh pertama tidak penuh, masukkan secara rekursif di babak pertama.
• Jika paruh pertama penuh, masukkan secara rekursif di babak kedua.
• Setelah langkah rekursif, jika seluruh array penuh, gabungkan bagian (yang diurutkan), dan ubah ukurannya menjadi dua kali lipat dari panjang aslinya.

Untuk menemukan elemen, ulangi di kedua bagian, menggunakan pencarian biner ketika array penuh. (Ini harus efisien karena paling banyak fragmen naik).$O(\log(n))$

Struktur dapat dianggap sebagai versi statis dari mergesort.

Tidak jelas apa yang harus dilakukan seseorang untuk menghapus suatu elemen.

Sunting: setelah meningkatkan pemahaman saya tentang struktur.

$A\cup B$$A$$B$$O(\log n)$$n$), tetapi menambah ruang hanya dengan faktor konstan. Ya, itu bisa dideamortisasi, terima kasih kepada Overmars dan van Leeuwen, tetapi Anda benar-benar tidak ingin melakukan itu jika Anda tidak harus melakukannya.

Catatan ini mencakup dasar-dasarnya.

Array lookahead yang tidak sadar cache adalah keturunan mutan dari pohon Bentley-Saxe dan van Emde Boas dengan steroid.

Ini mirip dengan pohon gabungan terstruktur log atau cache array lookahead yang tidak diketahui (atau COLA).

$2^k-1$$2^i$$0 \leq i < k$

$2^0$$2^1$

$O(\lg n)$$O(n)$$O(\lg^2 n)$