Struktur data untuk pencarian yang efisien, ketika penyisipan dan pemindahan hanya satu sisi

Saya membutuhkan struktur data untuk menyimpan nomor $n$elemen, masing-masing terkait dengan waktu berbeda  .  bervariasi dan walaupun memiliki batas atas teoretis, ini banyak urutan besarnya lebih besar dari apa yang biasanya digunakan.$t_i$$n$

Melalui aplikasi saya, saya dapat memastikan bahwa:

• Elemen yang dimasukkan selalu lebih baru dari semua elemen yang ada, yaitu, jika elemen yang terkait dengan waktu dimasukkan, maka . Elemen dimasukkan satu per satu.$\check{t}$$\check{t}>t_i ∀ i ∈ {1,…,n}$

• Hanya elemen tertua yang dihapus, yaitu, jika elemen dihapus, maka . Penghapusan sebagian besar terjadi satu per satu, tetapi tidak ada salahnya langsung jika penghapusan elemen ditunda, selama fraksi elemen yang disimpan palsu tetap lebih kecil dari 1.$j$$t_j < t_i ~∀ i ∈ \lbrace 1,…,n \rbrace \setminus \lbrace j \rbrace$

• Selain memasukkan dan menghapus, satu-satunya hal yang perlu saya lakukan adalah menemukan dua elemen tetangga untuk beberapa waktu dengan . Dengan kata lain saya perlu menemukan dua elemen j  dan  k sedemikian sehingga t_j <\ tilde {t} <t_k dan ∄ l ∈ \ {1,…, n \}: t_j <t_l <t_k .$\tilde{t}$$\min\limits_i t_i < \tilde{t} < \max\limits_{i} t_i$$j$$k$$t_j<\tilde{t}<t_k$$∄ l ∈ \{1,…,n\}: t_j<t_l<t_k$

Kriteria saya untuk struktur data adalah:

1. Elemen penemuan seperti dijelaskan di atas harus secepat mungkin.
2. Memasukkan dan menghapus harus cepat.
3. Struktur data relatif mudah diterapkan.

Selama kita tidak berbicara tentang offset runtime kecil, setiap kriteria memiliki prioritas di atas yang berikutnya.

Penelitian saya sejauh ini telah menghasilkan bahwa jawabannya kemungkinan adalah semacam pohon pencarian self-balancing, tetapi saya gagal menemukan informasi mana dari mereka yang terbaik untuk kasus memasukkan atau menghapus satu sisi, dan mungkin akan dikenakan biaya waktu yang cukup untuk mencari tahu sendiri. Juga, saya hanya menemukan informasi yang tidak lengkap tentang seberapa baik pohon mengatur diri sendiri dan seberapa cepat (misalnya, pohon AVL mengatur diri lebih kaku dari pohon merah-hitam), apalagi bagaimana ini dipengaruhi oleh penyisipan atau penghapusan satu sisi.

Simpan elemen sebagai urutan, diurutkan dengan menambah stempel waktu. Gunakan pencarian biner untuk menemukan lokasi di mana akan terjadi jika berada dalam array; maka Anda dapat dengan mudah menemukan dua elemen tetangga. Menemukan dua elemen tetangga dapat dilakukan dalam waktu .$\tilde{t}$$O(\lg n)$

Anda juga harus dapat menambahkan ke akhir urutan dan menghapus dari awal. Jadi, pada dasarnya Anda perlu antrian.

Ada konstruksi standar untuk antrian. Misalnya, Anda dapat menyimpannya dalam larik, dengan operasi diamortisasi dan amortisasi waktu. Pada dasarnya, Anda memiliki larik untuk elemen-elemen urutan, dan indeks awal (untuk awal urutan) dan indeks akhir (untuk akhir urutan). Untuk menghapus dari awal, tambahkan indeks awal. Untuk menambah sampai akhir, tambahkan indeks akhir; jika ini berjalan melewati akhir array yang ada, alokasikan array baru dengan ukuran dua kali lipat dan salin ke array baru.$O(1)$

Atau: Anda dapat menyimpan elemen dalam pohon biner seimbang. Ini akan mencapai waktu terburuk -waktu untuk semua operasi.$O(\lg n)$