Red–black tree

Red-Black Tree

Red-Black Tree (RBT) adalah pohon pencarian biner yang menyeimbangkan diri yang ditemukan pada tahun 1972 oleh Rudolf Bayer yang menyebutnya "pohon-biner simetris B-tree".

- Meskipun Red-Black Tree itu kompleks, ia memiliki waktu berjalan paling buruk untuk operasinya dan efisien untuk digunakan sebagai pencarian, penyisipan, dan penghapusan semua.

Binary Search Tree dikatakan Red-Black Tree jika:

1. Setiap node memiliki warna, baik merah atau hitam.
2. Rootnya hitam secara default.
3. Semua node eksternal berwarna hitam.
4. Jika node berwarna merah, maka kedua anaknya berwarna hitam, dapat dikatakan tidak ada nodemerah yang memiliki parent merah.
5. Setiap jalur sederhana dari node yang diberikan ke salah satu node eksternal turunannya mengandung jumlah yang sama dari node hitam.

Contoh Red-Black Tree sederhana.

Pengaplikasian / penggunan Red-Black Tree adalah:

• Red Black Trees menawarkan jaminan waktu terburuk untuk operasi penyisipan, penghapusan, dan pencarian.
• Red-Black Trees tidak hanya berharga dalam aplikasi yang sensitif terhadap waktu seperti aplikasi real-time.
• Pohon Merah-Hitam lebih disukai untuk digunakan sebagai blok bangunan dalam struktur data lain yang memberikan jaminan kasus terburuk.

RBT Operations: Insertion

Penyisipan dimulai dengan menambahkan simpul dengan cara yang sangat mirip dengan penyisipan pohon pencarian biner standar dan simpul yang baru disisipkan berwarna merah. Perbedaan besar adalah bahwa dalam pohon pencarian biner simpul baru ditambahkan sebagai daun, sedangkan daun tidak mengandung informasi di Red Black Tree, jadi alih-alih simpul baru menggantikan daun yang ada dan kemudian memiliki dua daun hitam yang ditambahkan sendiri.

Contoh Insertion:

RBT Operations: Deletion

Menghapus node pada Red-Black Tree sama seperti menghapus di binary search tree (jika itu adalah node dengan dua child, temukan elemen maksimum di sub-tree kirinya atau elemen minimum di sub-tree kanannya).

Biarkan simpul yang akan dihapus menjadi M, dan anaknya adalah C.

• Jika M berwarna merah, maka cukup ganti dengan C
• Jika M berwarna hitam dan C berwarna merah, gantilah dengan C dan warnai kembali C dengan hitam.

Jika M dan C berwarna hitam, ganti M dengan C. C diyatakan dalam posisi barunya menjadi N (itu juga disebut hitam ganda), induknya adalah P, saudara kandungnya adalah S, SL adalah child kiri S dan SR menjadi child kanan S.

• Jika S berwarna merah, balikkan warna N dan P, dan putar pada P.
• Jika S, SL, dan SR berwarna hitam, maka warnai ulang S sebagai merah.
• Jika S berwarna hitam dan SL atau SR berwarna merah, maka rotate tunggal atau rotate ganda.

Contoh deletion