Pohon pencarian biner adalah struktur data untuk menyimpan item dengan kemampuan pencarian cepat. Idenya sederhana dan cerdik: "semakin sedikit yang tersisa, semakin banyak yang benar." Di sinilah kesederhanaan berakhir dan pertanyaan rumit tentang keseimbangan pohon dimulai sehingga tidak berubah menjadi cabang yang panjang.
Pada artikel ini, kami akan memberikan definisi, daftar aturan untuk menempatkan elemen dalam pohon merah-hitam, mempertimbangkan algoritma balancing, dan mengkonsolidasikan apa yang dikatakan pada contoh. Kami mempelajari topik ini secara lebih rinci, serta jenis pohon pencarian biner lainnya dalam kursus "Algoritma untuk Pengembang" .
Pohon merah-hitam adalah
pohon pencarian biner yang menyeimbangkan diri sendiri yang menjamin pertumbuhan logaritmik ketinggian pohon dari jumlah node dan eksekusi cepat operasi dasar dari pohon pencarian: menambah, menghapus, dan mencari node.
Pohon merah-hitam tidak sepenuhnya seimbang, di beberapa tempat tingginya dapat bervariasi hampir dua kali lipat. Asumsi seperti itu tidak secara asimptotik mempengaruhi kecepatan pencarian elemen, tetapi secara signifikan mempercepat penempatan elemen baru, karena Anda tidak perlu "mengguncang" pohon setiap kali Anda menambahkan elemen, kadang-kadang cukup untuk menambahkan elemen merah tanpa menyentuh yang lain dan tanpa mengubah "ketinggian hitam" .
Aturan untuk menempatkan elemen di pohon merah-hitam
- Setiap node berwarna merah atau hitam, daun NIL selalu hitam.
- Akar pohon selalu hitam
- Kedua keturunan dari setiap simpul merah berwarna hitam
- Jalur turun dari sembarang simpul ke sembarang daun berisi jumlah simpul hitam yang sama.
Ketika Anda memasukkan elemen baru, itu diberikan warna merah. Untuk memenuhi dua aturan pertama, cukup cat ulang simpul baru dengan warna yang diinginkan.
Pertimbangkan aturan keseimbangan untuk implementasi 3 dan 4 poin.
Pada setiap gambar, diasumsikan bahwa kita telah menambahkan elemen X yang melanggar 3 aturan, kita perlu mengubah struktur pohon sehingga 3 aturan dieksekusi, dan 4 tidak dilanggar.
Legenda simpul:
- X - elemen tambahan yang melanggar 3 paragraf aturan.
- P - ayah item X
- G - kakek dari elemen X, ayah dari elemen P
- U adalah paman dari elemen X, saudara dari elemen P, putra kedua dari elemen G.
Kasus Satu - Paman Merah
Jika ayah dan pamannya berwarna merah, maka kita dapat "menurunkan" warna hitam dari tingkat kakek ke tingkat ayah dan mengecat kembali simpul-simpulnya, seperti yang ditunjukkan pada gambar. Dalam hal ini, "ketinggian hitam" akan tetap sama, namun, pelanggaran aturan 3 untuk elemen G adalah mungkin, oleh karena itu, perlu untuk secara rekursif memanggil penyeimbangan lebih lanjut untuk simpul ini.
Kasus kedua - paman hitam - ayah dan kakek dari arah yang berbeda.
Struktur ini harus dibawa ke kasus ketiga, ketika ayah dan kakek pergi ke arah yang sama. Untuk melakukan ini, Anda perlu melakukan belokan kecil dari anak X ke ayahnya (aturan belokan tidak dipertimbangkan dalam artikel ini) dan memanggil 3 kasus untuk elemen R.
Kasus Tiga - Paman Hitam - Ayah dan Kakek di Sisi yang Sama
Dalam hal ini, kita sudah dapat membuat perubahan besar dari ayah melalui kakek ke paman hitam dan mengecat ulang P menjadi hitam dan G menjadi merah. Sebagai hasil dari rotasi ini, 3-rule akan terpenuhi.
Pastikan aturan ke-4 juga dipenuhi. Misalkan sebelum belokan besar, ketinggian hitam elemen G adalah N + 2. Maka ketinggian elemen "yang ditangguhkan" adalah sebagai berikut:
A = N + 1,
B = N + 1,
C = N + 1,
D = N
E = N.
Lihat sendiri bahwa setelah memutar 4-aturan berlaku untuk semua elemen.
Contoh nyata
Sekarang kita akan mempertimbangkan proses pembentukan pohon merah-hitam dengan penyisipan berurutan elemen 1, 2, 3, 4, 5, dan 6.
Karena elemen 1 adalah root, kita cukup mengecatnya untuk memenuhi aturan 1.
Setelah menambahkan elemen 2, semua aturan dijalankan.
Saat menambahkan elemen 3, kami melanggar aturan 3. Karena kami memiliki paman hitam, dan kakek dan ayah di satu sisi, kami menggunakan kasus ketiga - kami berbelok dan mengecat ulang.
Saat menambahkan elemen 4, kami kembali melanggar aturan 3. Kali ini paman kami merah, jadi kami menerapkan pengecatan pertama - ketinggian hitam pohon akan bertambah 1. Harap diperhatikan. bahwa algoritma balancing diluncurkan tambahan untuk kakek - elemen 2, yang, seperti root, hanya dicat ulang dalam warna hitam.
Saat memasukkan elemen 5, kami kembali menerapkan 3 case - kami membuat belokan besar dan mengecat kembali simpul. Perhatikan bahwa ketinggian hitam tidak berubah.
Saat menambahkan elemen 6, kami kembali melanggar aturan 3. Karena paman kami merah, kami menerapkan pengecatan pertama, ketinggian hitam tidak berubah. Panggilan balancing untuk 4 elemen tidak mengubah apa pun di pohon, karena elemen ini tidak melanggar aturan.
Jadi, kami berkenalan dengan masalah keseimbangan pohon merah-hitam, lebih detail dan dengan contoh algoritma topik ini, serta varietas pohon pencarian biner lainnya, kami mempertimbangkan dalam kursus
"Algoritma untuk Pengembang" .