Red black tree merupakan salah satu tipe self balancing Binary Search Tree yang juga disebut sebagai simetris binary B-tree. Meskipun red black tree rumit, namun memiliki waktu terburuk yang efisien untuk digunakan pada saat melakukan search, insert dan delete dalam waktu .

Dalam artikel ini akan dibahas tentang operasi insert pada red black tree. Sebelum membahas tentang operasi insert pada red black tree perlu diketahui karakteristik red black tree :

Karakteristik red black tree :

  1. Setiap node memiliki warna red (merah) atau black (hitam).
  2. Warna node root selalu berwarna hitam.
  3. Semua node leaf berwarna hitam.
  4. Setiap node berwarna merah memiliki dua anak yang berwarna hitam.
  5. Setiap jalur dari root ke semua leaf harus memiliki jumlah node black yang sama.

Berikut ini adalah contoh dari red black tree :

Gambar 1 Red Black Tree

Keterangan : box kuning merupakan karakteristik red black tree yang telah dijelaskan di atas.

Pada operasi insert ada 3 hal yang perlu diperhatikan :

  1. Pada saat melakukan insert node baru, aturannya sama dengan seperti melakukan insert node baru pada binary search tree.
  2. Setiap node baru yang di insert berwarna merah.
  3. Perbaiki pelanggaran red black tree yang terjadi pada saat operasi insert.

Misalkan :

Q = node baru yang di insert

P = parent dari Q

S = sibling dari P (uncle dari Q)

  • Adapun kondisi yang terjadi pada saat insert adalah sebagai berikut :Jika Q = root maka warna Q = hitam.
Gambar 2 Insert Q kondisi A

  • Jika warna P = hitam maka warna Q tidak berubah.
Gambar 3 Insert Q kondisi B

  • Jika warna P = merah dan warna S = merah maka ubah warna P dan S menjadi hitam dan parent dari P menjadi merah.
Gambar 4 Insert Q kondisi C1

Atau

Gambar 5 Insert Q kondisi C2

Catatan : Jika GP merupakan root maka warnanya menjadi hitam sesuai dengan karakteristik 2.

  • Jika warna P = merah dan warna S = hitam lakukan rotasi (single atau double) kemudian dari hasil akhir rotasi tersebut ubah warna P yang baru menjadi hitam dan anak (child) yang baru menjadi merah. Jika S tidak ada atau P tidak memiliki sibling maka S dianggap berwarna hitam (setiap eksternal node berwarna hitam) dan aturan pada point D ini berlaku.
    1. Rotasi single (single rotation) :
Gambar 6 Insert Q kondisi D1.1.

atau

Gambar 7 Insert Q kondisi D1.2.

atau

Gambar 8 Insert Q kondisi D1.3.

atau

Gambar 9 Insert Q kondisi D1.4.

  • Rotasi double (double rotation)
Gambar 10 Insert Q kondisi D2.1.

atau

Gambar 11 Insert Q kondisi D2.2

atau

Gambar 12 Insert Q dengan kondisi D2.3.

atau

Gambar 13 Insert Q kondisi D2.4.

Referensi :

  1. Reema Thareja. (2014). Data Structure Using C. 02. OXFOR. New Delhi. ISBN : 9780198099307