Menghapus node dari pohon merah-hitam bukanlah tugas yang mudah, jadi masuk akal untuk membaginya menjadi beberapa bagian dan mempertimbangkan setiap kasus secara terpisah.
cartoonbank.ru
Di artikel terakhir, kami memeriksa aturan untuk membentuk pohon pencarian merah-hitam dan mempertimbangkan kasus penyeimbangan saat menambahkan elemen.
Sekarang mari kita bicara tentang menghapus item.
Ambil contoh, pohon merah-hitam ini:
Ingatlah bahwa properti utama pohon merah-hitam adalah ketinggian hitam yang sama di kiri dan kanan setiap simpul. Oleh karena itu, pada gambar, di samping setiap node, kami akan menunjukkan nilai ketinggian hitam, sehingga pada setiap tahap kami dapat memeriksa stabilitasnya.
Bagilah dan kuasai
Menghapus elemen dari pohon merah-hitam bukanlah tugas yang mudah seperti yang terlihat pada pandangan pertama, jadi saya mengusulkan untuk membaginya menjadi beberapa bagian dan mempertimbangkan masing-masing secara terpisah.
Pertama, mari bagi tugas menjadi dua kategori:
- warna node yang dihapus: K atau H.
- jumlah node anak: 2, 1 atau 0
Hasilnya, kami mendapatkan matriks 6 opsi: K2, Ch2, K1, Ch1, K0, Ch0.
Untuk setiap opsi, simpul yang sesuai dari pohon kami ditunjukkan.
Mari pertimbangkan proses penghapusan untuk setiap opsi.
K2 - simpul merah dengan dua anak
Tugas menghapus simpul dengan dua anak direduksi menjadi tugas menghapus simpul dengan satu atau nol anak.
Untuk melakukan ini, Anda perlu menemukan elemen terdekat yang kurang atau lebih dari yang dihapus dan menukarnya.
Harap dicatat bahwa saat menukar elemen, Anda hanya perlu mengubah nilai di node, dan membiarkan warnanya tetap sama, agar tidak merusak struktur pohon dan tidak mengubah ketinggian hitam.
Setelah pertukaran, Anda perlu menghapus item dari lokasi barunya. Ini akan menjadi elemen paling kanan di cabang kiri (maksimum di kiri), atau paling kiri di kanan (minimum di kanan), dalam hal apa pun itu tidak akan memiliki satu anak di kiri atau kanan. Dengan demikian, tugas menghapus node dengan 2 turunan direduksi menjadi tugas menghapus elemen dengan 1 atau 0 turunan:
- K2 => K1 atau K0
Ch2 - simpul hitam dengan dua anak
Mirip dengan kasus sebelumnya, kami akan memberikan contoh menghapus simpul hitam 16.
Seperti yang Anda lihat, setelah pertukaran, tugas dikurangi menjadi menghapus elemen dengan satu anak:
- Ch2 => Ch1 atau Ch0
K1 - simpul merah dengan satu anak
Jika simpul merah tidak memiliki satu anak, maka sebagai gantinya ada elemen NIL hitam dan tinggi simpul merah hitam adalah 1. Oleh karena itu, di sisi lain, tinggi hitam juga harus 1. Tetapi karena simpul merah tidak bisa memiliki anak merah warna, maka anaknya yang lain harus hitam. Karena tinggi hitam harus 1, itu hanya dapat berupa elemen NIL hitam, karena dalam kasus elemen hitam normal, tingginya akan lebih tinggi.
Dengan demikian, kasus K1 tidak terjadi.
Ch1 - simpul hitam dengan satu anak
Jika elemen hitam tidak memiliki satu anak, maka yang ada adalah elemen hitam NIL dengan tinggi 1. hitam, sehingga di sisi lain harus ada simpul merah tanpa anak. Untuk menghapus elemen seperti itu, cukup dengan mentransfer nilai elemen merah ke simpul hitam, sedangkan tinggi hitam akan dipertahankan.
K0 - simpul merah tanpa anak
Kasus paling sederhana. Kami hanya menghapus elemen, menggantinya dengan referensi NIL:
Menghapus elemen merah tidak mengubah tinggi hitam.
CH0 - simpul hitam tanpa anak
Menghapus simpul hitam tanpa anak juga sangat sederhana: kami menggantinya dengan referensi ke NIL.
Apakah menurut Anda ini hampir semuanya? Haha, enam kali.
Setelah menghilangkan elemen hitam, tinggi hitam subpohon berubah dan Anda perlu menyeimbangkannya untuk induknya.
Elemen yang dihapus pada gambar dilambangkan dengan x, tingginya - h. Saat kita baru mulai menyeimbangkan, h = 1, tetapi dengan panggilan rekursif dapat meningkat.
Untuk kepastian, mari kita tentukan bahwa elemen yang dihapus adalah anak yang tepat. Setelah diangkat, tingginya menurun dan menjadi h. Artinya tinggi anak kiri tetap h + 1. Kita perlu menyelaraskan ketinggian subpohon kiri dan kanan dan membuatnya sama dengan h + 1.
Saya sarankan untuk membagi tugas menjadi beberapa bagian lagi. Pilihan apa yang kita punya?
Induk bisa merah atau hitam. Putra kiri juga bisa berkulit hitam atau merah. Dan putra yang tepat selalu berkulit hitam - dari sanalah kami mencapai keseimbangan setelah pemindahan.
Ada 6 kasus berbeda untuk dipertimbangkan:
- KCH1 dan KCH2 - orang tua berwarna merah, anak kiri berwarna hitam.
- CHK3 dan CHK4 - orang tua berwarna hitam, anak kiri berwarna merah.
- HH5 dan HH6 - orang tua hitam, anak kiri hitam.
Kami akan menyimpan kesabaran dan popcorn, yang paling menarik dan misterius ada di depan.
1 - orang tua merah, anak kiri hitam dengan cucu hitam
Selama kita memiliki node merah, kita dapat memindahkan dan / atau mewarnai ulang mereka untuk mengembalikan keseimbangan ketinggian hitam. Dalam hal ini, kita dapat menurunkan warna merah dari induk ke anak kiri, sehingga menyelaraskan tinggi hitam induk:
Pastikan untuk memeriksa ulang dari gambar bahwa tinggi hitam dari simpul a dan b dipertahankan, dan tinggi dari seluruh pohon telah menjadi sama dan sama dengan h + 1.
KCH2 - orang tua berwarna merah, anak kiri berwarna hitam dengan cucu merah kiri.
Dalam hal ini, mengecat ulang saja tidak cukup. Kita perlu berbelok kecil ke kanan antara node 3-7. Hasilnya, kita akan bisa menambah tinggi subpohon kanan hingga h + 1:
Node hijau berarti bisa hitam atau merah.
Catatan. Jika node "1" berwarna hitam, dan "c" berwarna merah, maka masalahnya dapat dikurangi menjadi varian HH5.
CHK3 - orang tua berkulit hitam, putra kiri merah, cucu laki-laki kanan memiliki cicit berkulit hitam
Memiliki cicit berkulit hitam memungkinkan Anda mengecat ulang cucu menjadi merah dan mengirimkannya ke subtree kanan dengan membuat belokan kecil ke kanan 3-7, dan jangan tanya mengapa, cukup percaya dan periksa apakah ketinggian hitam telah stabil:
Perhatikan bahwa simpul merah 5 tidak menambah warna hitam tinggi.
CHK4 - orang tua berkulit hitam, putra kiri berwarna merah, cucu laki-laki kanan memiliki cicit merah
Lebih jauh ke dalam hutan merah, ada lebih banyak kayu bakar hitam, dan ada lebih sedikit yang merah, yaitu, dengan mewarnai ulang simpul merah, adalah mungkin untuk menstabilkan ketinggian hitam.
Dalam hal ini, Anda perlu melakukan belokan kiri yang besar, yang terdiri dari dua belokan kecil 5-3 dan 5-7. Node b berubah warna dari merah menjadi hitam dan dengan demikian menambah tingginya sebanyak 1. Pastikan bahwa tinggi hitam telah stabil.
HCH5 - orang tua berkulit hitam, putra kiri berkulit hitam dengan cucu merah kanan.
Lebih sedikit dan lebih sedikit elemen merah di subtree kita, cat ulang cucu merah terakhir hitam dan belok kiri besar, seperti pada kasus sebelumnya.
Periksa apakah ketinggian hitam subpohon telah stabil.
HCH6 - orang tua berkulit hitam, putra kiri berkulit hitam, cucunya juga berkulit hitam
Dan kemudian tibalah saat ketika kayu merah habis. Tidak ada yang bisa dilakukan, Anda harus mengecat simpul hitam dengan merah dan dengan demikian menyamakan tinggi hitam pada simpul 7, tetapi tidak dengan meningkatkan tinggi hitam pada sub-pohon kanan, tetapi dengan mengurangi tinggi hitam pada sub-pohon kiri. Akibatnya, ketinggian hitam seluruh struktur kita akan berkurang 1 dan kita harus secara rekursif memanggil balancing ke nenek moyang.
Contoh penghapusan dengan balancing dan rekursi
Kami melihat semua 6 kasus penyeimbangan tinggi hitam setelah menghapus elemen dari pohon merah-hitam. Untuk mendapatkan perasaan yang lebih baik tentang bagaimana ini semua bekerja, mari lanjutkan menghapus simpul 30 dari pohon aslinya.
Langkah pertama adalah menghapus node 30. Langkah
kedua adalah meluncurkan balancing pada node induknya - node 25.
Ada kasus HH6: Kami telah
menstabilkan ketinggian node 25 dengan kesedihan di setengahnya.
Langkah ketiga adalah menyeimbangkan di level kakek - untuk node 20.
Agar lebih menyenangkan dan lebih jelas , mari menggambar seluruh pohon sebelum dan sesudah penyeimbangan. Ini adalah kasus untuk HK4:
Perhatikan bagaimana pohon merah-hitam berubah setelah penyeimbangan, beberapa elemen dari subpohon kiri dipindahkan ke kanan, ketinggian distabilkan, elemen telah dihapus, semua orang senang!
Menghapus item dari pohon merah-hitam adalah salah satu operasi tersulit saat bekerja dengan pohon pencarian biner. Dalam kursus " Algoritma dan Struktur Data " kami mempertimbangkan tidak hanya pohon pencarian biner, tetapi juga banyak algoritma menarik lainnya, untuk lebih jelasnya lihat program kursus.
