Bayangkan sebuah pohon merah-hitam. Apakah selalu ada urutan penyisipan dan penghapusan yang membuatnya?

Mari kita asumsikan definisi pohon merah-hitam berikut:

Ini adalah pohon pencarian biner.
Setiap node berwarna merah atau hitam. Akar hitam.
Dua node yang dihubungkan oleh sebuah edge tidak bisa berwarna merah pada saat bersamaan.
Ini seharusnya definisi yang bagus untuk daun NIL, seperti pada wiki. Daun NIL berwarna hitam.
Jalur dari root ke sembarang daun NIL berisi jumlah simpul hitam yang sama.

Pertanyaan

Misalkan Anda telah menerapkan insertdan deleteoperasi untuk pohon merah-hitam. Sekarang, jika Anda diberi pohon merah-hitam yang valid, apakah selalu ada urutan insertdan deleteoperasi yang membangunnya?

Motivasi

Pertanyaan ini dimotivasi oleh pertanyaan ini dan oleh diskusi dari pertanyaan ini .

Secara pribadi, saya percaya bahwa jika Anda membayangkan pohon merah-hitam yang valid yang hanya terdiri dari simpul hitam (yang menyiratkan bahwa Anda membayangkan pohon yang seimbang sempurna), ada urutan insertdan deleteoperasi yang membangunnya. Namun,

Saya tidak tahu bagaimana membuktikannya secara akurat
Saya juga tertarik pada kasus yang lebih umum

data-structures search-trees balanced-search-trees alisianoi
sumber

Pertanyaan Anda terdengar agak melingkar ... setiap rangkaian operasi sisipan dan penghapusan akan membuat pohon merah-hitam ... secara harfiah apa saja, karena merah-hitam hanyalah sebuah definisi. Apakah pertanyaan Anda terbatas pada pohon yang murni hitam?

JOX

Tidak, saya pikir Anda salah paham. Tentu saja, setiap rangkaian sisipan dan penghapusan membangun beberapa pohon merah-hitam. Pertanyaannya adalah ini: apakah ada pohon yang sesuai dengan definisi yang dapat dibangun oleh beberapa urutan sisipan dan penghapusan? Jika Anda diberi beberapa pohon, dapatkah Anda membuat ulang urutan sisipan dan penghapusan?

alisianoi

@ all3fox Ya, Anda benar. Ada algoritma yang menggunakan operasi insertdan deleteuntuk membangun pohon merah-hitam yang valid yang hanya terdiri dari simpul hitam . Menggunakan

penyisipan / penghapusan untuk membuat pohon tinggi

. Pertama, kita dapat membuat pohon merah-hitam yang seimbang sempurna dengan cara pertama-lebar menggunakan

penyisipan, kemudian menggunakan

(h + 2) \cdot 2^{h} - 1

$(h + 2) \cdot 2^h - 1$

h

$h$

2^{h + 1} - 1

$2^{h+1} - 1$

h * 2^{h - 1}

$h * 2^{h-1}$ insersi dan jumlah penghapusan yang sama mengecatnya menjadi pohon yang benar-benar hitam. Kuncinya di sini adalah untuk naik

kali lapisan merah terendah naik pohon sampai mencapai akar.

h

$h$

Anton Trunov

@AntonTrunov terima kasih, saya agak mengerti itu. Bagaimana dengan kasus Red-Black Tree umum? Bagaimana menurut Anda, apakah mungkin untuk membangun Pohon Merah-Hitam dengan insertdan deleteoperasi tertentu?

alisianoi

a) Jawabannya akan tergantung pada implementasi yang tepat dari insertdan delete; mungkin ada beberapa cara untuk melakukan operasi ini. b) Karena pohon RB pada dasarnya adalah pohon B dari orde 4, orang dapat mencari inspirasi di sana. Detail mungkin terbukti sulit karena pemetaan dari RB ke B (dan / atau mundur) tidak unik.

Raphael

Jawaban:

Operasi menyisipkan dan menghapus di pohon merah-hitam mencakup penyeimbangan yang diperlukan untuk mempertahankan properti merah-hitam.

Masalah dengan pohon merah-hitam bersandar non (kiri atau kanan) adalah bahwa ada beberapa cara untuk mengembalikan merah-hitam setelah penghapusan atau penyisipan dasar.
Bukan sisipan atau penghapusan yang mentransformasikan pohon, tetapi penyeimbangan kembali dan rotasi yang terjadi setelahnya untuk menjaga / mengembalikan merah kehitaman pohon.

Deskripsi dasar pohon merah-hitam tidak menentukan rute mana yang mungkin diambil.
Mungkin tidak mungkin untuk mencari tahu bagaimana tepatnya merekonstruksi pohon hitam merah diberikan, karena rebalancing tidak perlu deterministik.

Ini telah 'diselesaikan' dengan pohon-pohon merah hitam yang condong ke kiri.
Hanya ada satu cara penyeimbangan dilakukan. Jadi setiap pohon merah hitam yang bersandar dapat direkonstruksi menggunakan sisipan dan penghapusan, karena penyeimbangan / rotasi dilakukan dengan cara deterministik tertentu.

Ini tidak berarti bahwa pohon RB yang condong ke kiri lebih baik atau lebih efisien, apa yang mereka dapatkan di satu sisi dengan menggunakan aturan balancing deterministik, mereka kalah di sisi lain oleh kode balancing yang lebih kompleks.

$(h+2)⋅2^{h}−1$ $h$ $2^{h+1}−1$ $h∗2^{h-1}$ $h$ kali lapisan merah terendah sampai pohon itu mencapai akar.

Saya pikir algoritma penyeimbang lengkap seperti Day-Stout-Warren akan lebih efisien.

Johan
sumber

Menggunakan operasi insertdan deletedari buku CLRS Anda dapat membangun pohon RB yang valid yang hanya terdiri dari node hitam . Caranya adalah dengan memasukkan lebih banyak node dari yang dibutuhkan dan kemudian menghapus yang berlebihan. Algoritma akan menghilangkan node merah.

Anton Trunov

@AntonTrunov, apakah Anda memiliki tautan untuk algoritme itu, akan lebih baik untuk memasukkannya dalam jawaban. Saya tidak dapat menemukannya menggunakan google-fu saya.

Johan

Sayangnya saya tidak punya tautan. Saya mencoba menjawab pertanyaan pada saat itu, dan muncul dengan algoritma untuk kasus khusus semua pohon RB hitam. Saya semacam menggambarkannya dalam komentar itu, tetapi tidak memberikan bukti.

Anton Trunov

Apa yang Anda maksud dengan "Ini telah 'diselesaikan' dengan pohon-pohon hitam merah bersandar kiri.". Bahkan pohon hitam merah yang condong ke kiri memiliki banyak cara untuk menyimpan barang yang sama.

user239558