Subrange dari Pohon Merah dan Hitam

Ketika mencoba memperbaiki bug di perpustakaan, saya mencari makalah tentang menemukan subranges di pohon merah dan hitam tanpa hasil. Saya sedang mempertimbangkan solusi menggunakan ritsleting dan sesuatu yang mirip dengan operasi append yang biasa digunakan pada algoritma penghapusan untuk struktur data yang tidak dapat diubah, tetapi saya masih bertanya-tanya apakah ada pendekatan yang lebih baik yang tidak dapat saya temukan, atau bahkan batas kompleksitas minimum pada operasi seperti itu?

Untuk lebih jelasnya, saya berbicara tentang algoritma yang, mengingat pohon merah & hitam dan dua batas, akan menghasilkan pohon merah & hitam baru dengan semua elemen pohon pertama yang termasuk dalam batas-batas itu.

Tentu saja, batas atas kompleksitas adalah kompleksitas melintasi satu pohon dan membangun yang lain dengan menambahkan elemen.

Jawaban ini menggabungkan beberapa komentar saya dengan pertanyaan dan mengembangkannya.

Operasi subrange pada pohon merah-hitam dapat dilakukan dalam kasus O (log n) terburuk, di mana n adalah jumlah elemen dalam pohon asli. Karena pohon yang dihasilkan akan berbagi beberapa node dengan pohon asli, pendekatan ini hanya cocok jika pohon tidak dapat diubah (atau pohon bisa berubah tetapi pohon asli tidak lagi diperlukan).

Pemberitahuan pertama bahwa operasi subrange dapat diimplementasikan oleh dua operasi terpisah. Di sini operasi pemisahan mengambil pohon T hitam merah dan kunci x dan menghasilkan dua pohon L dan R sedemikian rupa sehingga L terdiri dari semua elemen T kurang dari x dan R elemen T lebih besar dari x. Oleh karena itu, tujuan kami sekarang adalah untuk mengimplementasikan operasi pemisahan pada pohon merah-hitam pada kasus O (log n) terburuk.

Bagaimana kita melakukan operasi split pada pohon merah-hitam dalam waktu O (log n)? Ya, ternyata ada metode yang terkenal. (Saya tidak tahu, tapi saya bukan ahli struktur data.) Pertimbangkan operasi gabungan , yang mengambil dua pohon L dan R sehingga setiap nilai dalam L kurang dari setiap nilai dalam R dan menghasilkan pohon yang terdiri dari semua nilai-nilai dalam L dan R. bergabung operasi dapat diterapkan dalam kasus terburuk waktu O (| r _L r _R | 1), di mana r _L dan r _Radalah jajaran L dan R, masing-masing (yaitu, jumlah simpul hitam di jalur dari akar ke setiap daun). Operasi pemisahan dapat diimplementasikan dengan menggunakan operasi gabungan O (log n) kali, dan total waktu terburuk masih O (log n) dengan mempertimbangkan jumlah telescoping.

Bagian 4.1 dan 4.2 dari sebuah buku [Tar83] oleh Tarjan menjelaskan bagaimana mengimplementasikan operasi join dan split pada pohon merah-hitam dalam waktu kasus terburuk O (log n). Implementasi ini menghancurkan pohon asli, tetapi mudah untuk mengubahnya menjadi implementasi fungsional yang tidak dapat diubah dengan menyalin node alih-alih memodifikasi mereka.

Sebagai catatan tambahan, modul Set dan Map Objective Caml menyediakan operasi pemisahan serta operasi standar lainnya pada pohon pencarian biner seimbang (tidak dapat diubah). Meskipun mereka tidak menggunakan pohon merah-hitam (mereka menggunakan pohon pencarian biner seimbang dengan batasan bahwa tinggi kiri dan tinggi kanan berbeda paling banyak 2), melihat implementasi mereka mungkin berguna juga. Berikut ini adalah implementasi dari modul Set .

Referensi

[Tar83] Robert Endre Tarjan. Struktur Data dan Algoritma Jaringan . Volume 44 Seri Konferensi Regional CBMS-NSF dalam Matematika Terapan , SIAM, 1983.

Solusinya adalah jangan menggunakan pohon merah-hitam. Dalam pohon splay dan pohon AVL kode untuk memisahkan dan bergabung sangat sederhana. Saya merujuk Anda ke URL berikut dengan kode java untuk pohon splay dan pohon AVL yang mendukung ini. Buka URL berikut dan periksa Set.java (avl trees) dan SplayTree.java (splay trees).

ftp://ftp.cs.cmu.edu/usr/ftp/usr/sleator/splaying/

--- Danny Sleator

(Ini dimaksudkan sebagai komentar tetapi saya terlalu baru untuk meninggalkan komentar.)

Saya hanya ingin mencatat bahwa Anda mungkin juga tertarik dengan operasi "eksisi", yang mengembalikan subrange sebagai pohon baru dan pohon input tanpa subrange yang lain. Anda perlu memiliki kontrol pada representasi yang mendasari pohon karena metode yang dikenal bergantung pada tautan level. Eksisi berjalan dalam waktu logaritmik dengan ukuran lebih kecil pohon yang , meskipun dalam arti diamortisasi ("diamortisasi" adalah iirc, karena saya tidak memiliki akses ke kertas lagi) Lihat:

K. Hoffman, K. Mehlhorn, P. Rosenstiehl, dan RE Tarjan, menyortir urutan Jordan dalam waktu linier menggunakan pohon pencarian level linked, Information and Control, 68 (1986), 170-1-184

PS Kutipan di atas berasal dari penulisan treap Seidel. Treaps juga mendukung eksisi.

$n$$m$$[a,b]$

1. $O(\lg n)$$\ge a$$a$ 's pengganti).
2. $O(m)$
3. $O(m)$

$O(m+\lg n)$$O(n+m\lg m)$

$o(m)$$\Omega(\lg m)$$k$$\lg m$

Saya tidak mengetahui detailnya, jadi saya tidak yakin bagaimana pembukuan tambahan memengaruhi waktu berjalan.

$O(1)$$\Omega(\lg m)$